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 24, 2008 Lecture 19 Lecturer: Scott Aaronson Scribe: Michael Fitzgerald 1 Recap And Discussion Of Previous Lecture In the previous lecture, we discussed different cryptographic protocols. People asked: “In the RSA cryptosystem, why do people raise to a powe r greater than three?” Raising to a power greater than three is an extra precaution; it’s like adding a second lock on your door. If everything has been implemented correctly, the RSA we discussed (cubing the message (mod n)) should be fine. This assumes that your message has been padded appropriately, however. If your message hasn’t been padded, “small-exponent attacks” can be successful at breaking RSA; sending the message to a bunch of different recipients with different public keys can let the attacker take advantage of the small exponent. Raising to a power greater than three mitigates this risk. There are a couple of other attacks that can be success ful. “Timing attacks” look at the length of time the computer takes to generate numbers to get hints as to what those numbers are. Other attacks can look at the electromagnetic waves coming from the computer to try and get hints about the number. Then there are attacks that abuse the cryptosystem with constructed inputs and try to determine some information about the system based on the error messages they receive. In general, modern cryptosystems are most often defeated when attackers find bugs in the implementations of the systems, not in the systems themselves. Social engineering remains the most successful way of breaching security; often just calling someone on the phone, pretending to be a company tech support person, and asking for their password will ge t you a res ponse. We also talked about zero-knowledge proofs and general interactive protocols in the last lecture. Twenty years ago, a revolution in the notion of “proof” drove home the point that a proof doesn’t have to be just a static set of symbols that someone checks for accuracy. For example, a proof can be an interactive process that ends with you being convinced of a statement’s truth, without learning much of anything else. We gave two examples of so-called zero-knowledge protocols: one that convinces a verifier that two graphs are not isomorphic, and another that proves any statement with a short conve ntional proof, assuming the existence of one-way functions. 2 More Interactive Proofs It turns out that this notion of an interactive proof is good for more than just cryptography. It was discovered in the early 1990s that interactive proofs can convince you of solutions to problems that we think are much harder than N P -complete ones. As an analogy, it’s hard to tell that an author of a research paper knows what he’s talking about just from reading his paper. If you get a chance to ask him questions off the cuff and he’s able to respond correctly, it’s much more convincing. Similarly, if you can send messages back and forth with a prover, can you use that to c onvince yourself of more than just the solution to an NP -complete problem? To study this in the 1980s, people defined a complexity class called IP , which stands for “interactive proof.” The details of this story are beyond the scope of the class, but it’s being mentioned because it’s important. Consider the following scenario. Merlin and Arthur are communicating. Merlin has infinite computational power, but he is not trustworthy. Arthur is a P P T (probabilistic polynomial time) 19-13 king; he can flip coins, generate random numbers, send messages back and forth with Merlin, etc. What we want from a good protocol is this: if Merlin is telling the truth, then there should be some strategy for Merlin that cause s Arthur to accept with probability 1. On the other hand, if Merlin is lying, then Arthur should reject with probability greater than 1/2, regardless of Merlin’s strategy. These correspond to the properties of completeness and soundness that we discussed a while ago. How big is the class IP , then? It ce rtainly contains N P , as Merlin’s strategy could just be to send a solution over to Arthur for the latter to check and approve. Is IP bigger than N P , though? Does interaction let you verify more statements than just a normal proof would? In 1990, Lund, Fortnow, Karloff, and Nisan showed that IP contains coNP as well. This isn’t obvious; the key idea in the proof involves how polynomials over finite fields can be judged as equal by testing them at random points. This theorem takes advantage of that fact, along with the fact that you can reinterpret a Boolean formula as a polynomial over a finite field. An even bigger bombshell came a month later, when Shamir showed that IP contains the entire class P SP ACE, of problems solvable with polynomial memory. Since it was known that IP is contained in P SP ACE, this yields the famous result IP = P SP ACE. What does this result mean, in intuitive terms? Suppose an alien comes to earth and says, “I can play perfect chess.” You play the alien and it wins. But this isn’t too surprising, since you’re not very good at chess (for the purposes of this example, at least). The alien then plays again your local champion, then Kasparov, then Deep Blue, etc., and it beats them all. But just because the alien can beat anyone on earth, doesn’t mean that it can beat anything in the universe! Is there any way for the alien to prove the stronger claim? Well, remember that earlier we mentioned that a generalized n×n version of chess is a P SP ACE problem. Because of that, we can transform chess to a game about polynomials over finite fields. In this transformed game, the best strategy for one of the players is going to be to move randomly. Thus, if you play randomly against the alien in this transformed game and it wins, you can be certain (with only an exponentially small probability of error) that it has an optimal strategy, and could beat anyone. You should be aware of this result, as well as the zero-knowledge protocol for the 3-Coloring, since they’re two of the only