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 6 080 6 089 GITCS April 17 2008 Lecture 18 Lecturer Scott Aaronson 1 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 rst example of a public key cryptosystem in which two people exchanging messages did not have to meet beforehand was Di e 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 rst 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 rst nds 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 special about 3 As it turns out 3 is just the rst choice that s convenient Squaring would lead to a ciphertext that had multiple decryptions corresponding 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 messages 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 property 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 trapdoor information then you can e ciently invert it So for example the function f x x3 mod N is believed to be a one way function yet is easy to invert by someone who knows the prime factors of N 2 1 Di erent Classes of TDOWF s Question from the oor Are there any candidate TDOWF s not based on modular arithmetic like RSA is Answer One class 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 su ce 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 based 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 elliptic curve cryptogra phy has certain 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 trapdoor OWF then as far as we know all sorts of generic computational processes 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 2 di erent 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 N P coN P For example given an encrypted message we could ask if the rst bit of the plaintext is 1 If it is then a short proof is to decrypt the message If it s not then a short proof is also to decrypt the message However problems in N P coN P can t be NP complete under the most common reductions unless N P coN P 3 1 Impagliazzo s Five Worlds A famous paper …