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 1 Scribe Michael Fitzgerald Recap And Discussion Of Previous Lecture In the previous lecture we discussed di erent cryptographic protocols People asked In the RSA cryptosystem why do people raise to a power 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 ne 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 di erent recipients with di erent 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 successful 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 nd 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 get you a response 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 veri er that two graphs are not isomorphic and another that proves any statement with a short conventional 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 o the cu 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 convince yourself of more than just the solution to an N P complete problem To study this in the 1980s people de ned 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 in nite computational power but he is not trustworthy Arthur is a P P T probabilistic polynomial time 19 1 king he can ip 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 causes 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 certainly 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 Karlo and Nisan showed that IP contains coN P as well This isn t obvious the key idea in the proof involves how polynomials over nite elds 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 nite eld 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 nite elds 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 examples we have in computational complexity theory where you take an N P complete or P SP ACE complete problem and do something with it that actually exploits its structure as opposed to just treating it as a generic search problem And it s known that exploiting structure in this sort of way no doubt at an astronomically more advanced level will someday be needed to solve the P N P problem 3 Machine Learning Up