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 Apr 15 2008 Lecture 17 Lecturer Scott Aaronson 1 Scribe Adam Rogal Recap 1 1 Pseudorandom Generators We will begin with a recap of pseudorandom generators PRGs As we discussed before a pseudorandom generator is a function that takes as input a short truly random input string and produces an output of a seemingly random string Formally a PRG is a polytime computable function f 0 1 n 0 1 n 1 such that for all deterministic polynomialtime algorithms A Pr A y accepts Pr A f x accepts y 0 1 n 1 x 0 1 n is negligible Given a PRG that stretches n bits to n 1 bits we can create a PRG that stretches n bits to p n bits for any polynomial p To do so we repeatedly break o a single bit of the PRG s output and feeding the remaining n bits back into the PRG to get another n 1 pseudorandom bits This process is shown in gure 1 To prove that it works one needs to show that could we distinguish the p n bit output from random we could also distinguish the original n 1 bit output from random thereby violating the assumption that we started with a PRG Formalizing this intuition is somewhat tricky and will not be done here n n 1 p n n 1 n 1 n 1 Figure 1 A seemingly random string of size p n is gener ated from an n bit seed using the feed and repeat method 1 2 Cryptographic Codes Using pseudorandom generators it s possible to create secure cryptographic codes with small key sizes The details of this are complicated if you want to protect against realistic attacks for example so called chosen message attacks But at the simplest level the intuition is the following we should be able to simulate a one time pad which is provably unbreakable when used correctly by 1 taking a small random key 2 stretching it to a longer key using a PRG and then 3 treating that longer key as the one time pad If a polynomial time adversary could break such a system that would mean that the adversary was distinguishing the PRG s output from a truly random string contrary to assumption 1 3 One Way Functions In addition to PRGs we ll be interested in a closely related class of objects called OWFs or one way functions An OWF is a polytime computable function f 0 1 n 0 1 p n such that for all deterministic polynomial time algorithms A Pr x 0 1 n f A f x f x is negligible Or in plainer language an OWF is a function that s easy to compute but hard to invert 1 4 Yao s Minimax Principle As a side note you might wonder why we assumed the adversary A was determinisic rather than probabilistic The answer is that it makes no di erence If you re playing rock paper scissors and you know the probability distribution over your opponent s move then there s always some xed move you can make that does as well as any randomized strategy Similarly one you x the probability distribution over inputs as we do with PRGs and OWFs there s always a deterministic algorithm whose success probability is as large as any randomized algorithm s This is the easy part of Yao s Minimax Principle one of the most useful facts in theoretical computer science 1 5 Relation Between PRGs and OWFs Claim Every PRG is also an OWF Why Because if we could invert a PRG then it wouldn t be pseudorandom We d learn that there was some seed that generated the output string which would be true for a random string with probability at most 1 2 In 1997 Ha stad et al proved the opposite direction if OWFs exist then so do PRGs This direction was much much harder note that transformations of the OWF are neces sary since it s easy to give examples of OWFs that are not PRGs Because of this result we now know that the possibility of private key encryption with small keys is essentially equivalent to the existence of OWFs 2 2 1 Public Key Cryptography Abstract Problem Suppose Alice is trying to send Bob a package so that no third party can open it en route We ll assume that boxes can be locked in such a way that you can only open a box if you have the right key If Alice and Bob share duplicates of the same key then this problem is trivial Alice locks the box with her key and sends it to Bob who then opens it with his key But what if Alice and Bob don t share a key Obviously we don t want Alice to send the package in a locked box and the key that opens the lock in an unlocked box We seem to be faced with an in nite regress Fortunately there s a simple solution As shown in Figure 2 rst Alice puts the package in a box locks it and sends it to Bob Then Bob puts a second lock on the box and sends it back to Alice Then Alice removes her lock and sends the box back to Bob Finally Bob removes his lock and opens the box Bob Alice A A A B A B B B Figure 2 The smarter approach has Alice and Bob passing the package with at least one form of protection at all times This ensures that only Alice and Bob will be able to open the package 2 2 Di e Hellman How could we simulate the above protocol in the situation where Alice and Bob are sending bits of information rather than physical boxes The rst serious proposal in the open literature for how to do this was given by Di e and Hellman in 1976 Alice Bob mod mod mod mod mod mod mod mod mod mod Figure 3 The Di e Hellman protocol for creating a shared secret key K between Alice and Bob The process shown in gure 3 begins by Alice choosing a large prime number p a base g and a secret integer a Alice will calculate a public number A g a mod p She will then send p g and A to Bob Bob will then pick his own secret b and send B g b mod p back to Alice Finally Alice calculates the secret key K as K B a mod p and Bob calculates it as K Ab mod p They both now have the same key with which to encode messages to each other We ve seen that Di e Hellman is a simple way to exchange a key yet but it s a bit cumbersome in practice What we d really like is a …