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 4th 2008 Lecture 16 Lecturer Scott Aaronson Scribe Jason Furtado Private Key Cryptography 1 Recap 1 1 Derandomization In the last six years there have been some spectacular discoveries of deterministic algorithms for problems for which the only similarly e cient solutions that were known previously required randomness The two most famous examples are the Agrawal Kayal Saxena AKS algorithm for determining if a number is prime or composite in deterministic polynomial time and the algorithm of Reingold for getting out of a maze that is solving the undirected s t con nectivity problem in deterministic LOGSPACE Beyond these speci c examples mounting evidence has convinced almost all theoretical com puter scientists of the following Conjecture Every randomized algorithm can be simulated by a deterministic algorithm with at most polynomial slowdown Formally P BP P 1 2 1 2 1 Cryptographic Codes Caesar Cipher In this method a plaintext message is converted to a ciphertext by simply adding 3 to each letter wrapping around to A after you reach Z This method is breakable by hand 1 2 2 One Time Pad The one time pad uses a random key that must be as long as the message we want to en crypt The exclusive or operation is performed on each bit of the message and key M sg Key EncryptedM sg to end up with an encrypted message The encrypted message can be decrypted by performing the same operation on the encrypted message and the key to retrieve the message EncryptedM sg Key M sg An adversary that intercepts the encrypted message will be unable to decrypt it as long as the key is truly random The one time pad was the rst example of a cryptographic code that can proven to be secure even if the adversary has all the computation time in the universe The main drawback of this method is that keys can never be reused and the key must be the same size as the message to encrypt If you were to use the same key twice an eavesdropper could compute Enc M sg1 Enc M sg2 M sg1 M sg2 This would leak information about M sg1 and M sg2 16 1 Example Suppose M sg1 and M sg2 were bitmaps and M sg1 had sections that were all the same say a plain white background For simplicity assume M sg1 is all zeros at bit positions 251 855 Then M sg2 will show through in those bit positions During the Cold War spies were actually caught using this sort of technique Also note that the sender and the recipient must agree on the key in advance Having shared random keys available for every possible message size is often not practical Can we create encryp tion methods that are secure with smaller keys by assuming our adversary doesn t have unlimited computing power say is restricted to running polynomial time algorithms 2 Pseudorandom Generators A pseudorandom generator PRG is a function that takes as input a short truly random string called the seed and produces as output a long seemingly random string 2 1 Seed Generation A seed is a truly random string used as input to a PRG How do you get truly random numbers Some seeds used are generated from the system time typing on a keyboard randomly the last digits of stock prices or mouse movements There are subtle correlations in these sources so they aren t completely random but there are ways of extracting randomness from weak random sources For example according to some powerful recent results nearly pure randomness can often be extracted from two or more weak random sources that are assumed to be uncorrelated with each other How do you prove that a sequence of numbers is random Well it s much easier to give overwhelming evidence that a sequence is not random In general one does this by nding a pattern in the sequence i e a computable description with fewer bits than the sequence itself In other words by showing that the sequence has less than maximal Kolmogorov complexity In this lecture we ll simply assume that we have a short random seed and consider the problem of how to expand it into a long random looking sequence 2 2 2 2 1 How to Expand Random Numbers Linear Congruential Generator In most programming languages if you ask for random numbers what you get will be something like the following starting from integers a b and N x1 ax0 b mod N x2 ax1 b mod N xn axn 1 b mod N This process is good enough for many non cryptographic applications but an adversary could easily distinguish the sequence x0 x1 from random by solving a small system of equations mod N For cryptography applications it must not be possible for an adversary to gure out a pattern in the output of the generator in polynomial time Otherwise the system is not secure 2 2 2 Cryptographic Pseudorandom Generator CPRG De nition Yao 1982 16 2 A cryptographic pseudorandom generator CPRG is a function f 0 1 n 0 1 n 1 such that 1 f is computable in polynomial time 2 For all polynomial time algorithms A adversaries P ry 0 1 n 1 A y accepts P rx 0 1 n A f x accepts the advantage is negligibly small In other words the output of the CPRG must look random to any polynomial time algorithm In the above de nition negligibly small means less than 1 p n for all polynomials p This is a minimal requirement since if the advantage of the adversary were 1 p n then in polynomial time the adversary could amplify the advantage to a constant see Lecture 14 Of course it s even better if the adversary s advantage decreases exponentially The de nition above only requires f to stretch an n bit seed into a random looking n 1 bit string Could we use such an f to stretch an n bit seed into say a random looking n2 bit string It turns out that the answer is yes basically we feed f its own output n2 times See Lecture 17 for more details 2 2 3 Enhanced One Time Pad Using such a CPRG f 0 1 n 0 1 p n we can make our one time pad work for messages polynomially larger than the original key s k f s e x k x e k Claim With this construction no polynomial time adversary can recover the plaintext from the ciphertext Proof Assume for simplicity that the plaintext consists of just a single repeated random bit i e is either 00 0 or 11 1 both with equal probability Also suppose by way of contradiction that a polynomial time adversary could guess the plaintext given the ciphertext with probability non negligibly greater than 1 2 We know that if …