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.17-1� � 6.080/6.089 GITCS Apr 15, 2008 Lecture 17 Lecturer: Scott Aaronson Scribe: Adam Rogal 1 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 rand om inp ut string and prod uces 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 polynomial-time algorithms A, � � � Pr [A(y) accepts] − Pr [A(f(x)) accepts] � � � y∈{0,1}n+1x∈{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 s o, we repeatedly break off 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 figure 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 n+1 n+1 … n+1 p(n) 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. Th e details of this are complicated if you want to protect against realistic17-2attacks (for example, s o-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 u sing 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 rand om string, contrary to assum ption. 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 [f(A(f(x))) = f (x)] x∈{0,1}n is negligible. Or in p lainer language, an OWF is a f unction 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 difference! If you’re playing rock-paper-scissors, and you know th e probability distribution over your opponent’s move, then there’s always some fixed move you can make that does as well as any randomized strategy. Similarly, one you fix the probability distribution over inputs – as we do with PRGs and OWFs – there’s always a deterministic algorithm whose su ccess probability is as large as any randomized algorithm’s. Th is 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 th at generated the output string, which would be true for a random string with probability at most 1/2. In 1997, H˚astad 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 Public-Key Cryptography 2.1 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 dup licates of the same key, then this pr oblem is trivial: Alice locks the box with her key and sends it to Bob, who then opens it with his key. But what17-3if 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 infinite regress. Fortunately, there’s a simple solution. As shown in Figure 2, first Alice puts the package in a box, locks it, and sends it to Bob. Then Bob p uts 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. Alice Bob $ $ $ 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.17-42.2 Diffie-Hellman How could we simulate the above pr otocol, in the situation where Alice and Bob are sending bits of in formation rather than physical boxes? The first serious pr oposal in the open literature for how to do this was given by Diffie and Hellman in 1976. Alice Bob mod mod mod mod mod mod mod mod mod mod Figure 3: The Diffie-Hellman protocol for creating a s hared secret key K between Alice and Bob. The process, shown in figure 3, begins by Alice