MIT OpenCourseWare http://ocw.mit.edu 6.080 / 6.089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.1 6.080/6.089 GITCS April 17, 2008 Lecture 18 Lecturer: Scott Aaronson Scribe: Hristo Paskov Recap Last time we talked about public key cryptography which falls in the realm of accomplishing bizarre social goals using number theory. Our first example of a public-key cryptosystem, in which two people exchanging messages did not have to meet beforehand, was Diffie-Hellman. We then talked about the RSA cryptosystem, which is probably the most widely used today. Here are the basics of how it works: The first step is taken by the recipient of the message, by generating two giant prime numbers p and q and setting N = pq. Note that p and q must be chosen such that p − 1 and q − 1 are not divisible by 3. The recipient keeps p and q a closely-guarded secret, but gives out N to anyone who asks. Suppose a sender has a secret message x that she wants to send to the recipient. The sender calculates x3 mod N and sends it to the recipient. Now it’s the recipient’s turn to recover the message. He can use some number theory together with the fact that he knows p and q, the factors of N . The recipient first finds an integer k such that 3k = 1 mod (p − 1)(q − 1), which can be done in polynomial time via Euclid’s algorithm, and then takes (x3)k mod N = x3k mod N = x. The exponentiation can be done in polynomial time by using the trick of repeated squaring. Voila! When you look at this procedure, you might wonder why are we cubing as opposed to raising to another power; is there anything sp ec ial about 3? As it turns out, 3 is just the first choice that’s convenient. Squaring would lead to a ciphertext that had multiple decryptions (corres ponding to the multiple square roots mod N ), while we want the decryption to be unique. Indeed, if we wanted the square root to be unique, then we’d need p−1 and q −1 to not divisible by 2, which is a problem since p and q (being large prime numbers) are odd! You could, however, raise to a power higher than 3, and in fact that’s what people usually do. If the other components of the cryptosystem—such as the padding out of mess ages with random garbage—aren’t implemented properly, then there’s a class of attacks called “small-exponent at-tacks” which break RSA with small exponents though not with large ones. On the other hand, if everything else is implemented properly, then as far as we know x3 mod N is already secure. 18-1(Just like in biology, everything in cryptography is always more complicated than what you said, whatever you said. In particular, as soon as you leave a clean mathematical model and enter the real world, where code is buggy, hardware inadvertently leaks information, etc. etc., there’s always further scope for paranoia. And cryptographers are extremely paranoid people.) As mentioned in the last lecture, we know that a fast factoring algorithm would lead to a break of RSA. However, we don’t know the opposite direction: could you break RSA without factoring? In 1979, Rabin showed that if you squared the plaintext x instead of cubing it, then recovering x would be as hard as factoring. But as discussed earlier, in that case you’d lose the prop erty that every decryption is unique. This problem is what’s prevented widespread adoption of Rabin’s variant of RSA. 2 Trapdoor One-Way Functions The operation x3 mod N in RSA is an example of what’s called trapdoor one way function, or TDOWF. A trapdoor one-way function is a one-way function with the additional property that if you know some secret “trapdo or” information then you can efficie ntly invert it. So for example, the function f(x) = x3 mod N is believed to be a one-way function, yet is easy to inve rt by someone who knows the prime factors of N. 2.1 Different Classes of TDOWF’s Question from the floor: Are there any candidate TDOWF’s not based on m odular arithmetic (like RSA is)? Answer: One c lass that’s been the subject of much recent research is based on lattices. (Strictly speaking, the objects in this class are not TDOWF’s, but something called lossy TDOWF’s, but they still suffice for public-key encryption.) Part of the motivation for studying this class is that the cryptosystems based on modular arithmetic could all be broken by a quantum computer, if we had one. By contrast, even with a quantum computer we don’t yet know how to break lattice cryptosystems. Right now, however, lattice cryptosystems are not used much. Part of the problem is that, while the message and key lengths are polynomial in n, there are large polynomial blowups. Thus, these cryptosystems aren’t considered to be as practical as RSA. On the other hand, in recent years people have come up with better constructions, so it’s becoming more practical. There’s also a third class of public-key cryptosystems base d on elliptic curves, and elliptic-curve cryptography is currently practical. Like RSA, elliptic-curve cryptography is based on abelian groups, and like RSA it can be broken by a quantum computer. However, e lliptic-curve cryptogra-phy has ce rtain nice properties that are not known to be shared by RSA. In summary, we only know of a few classes of candidate TDOWF’s, and all of them are based on some sort of interesting math. When you ask for a trapdoor that makes your one-way function easy to invert again, you’re really asking for something mathematically special. It almost seems like an accident that plausible candidates exist at all! By contrast, if you just want an ordinary, non-trapdo or OWF, then as far as we know, all sorts of “generic” computational proc es ses that scramble up the input will work. 3 NP-completeness and Cryptography An open problem for decades has been to base cryptography on an NP-complete problem. There are strong heuristic arguments, however, that suggest that if this is possible, it’ll require very 18-2different ideas from what we know today. One reason (discussed last time) is that cryptography requires average-case hardness rather than worst-case. A second reason is that many problems in cryptography actually belong to the class NP ∩ coNP .