MIT News - Interactive proofs
http://news.mit.edu/topic/mitinteractive-proofs-rss.xml
MIT News is dedicated to communicating to the media and the public the news and achievements of the students, faculty, staff and the greater MIT community.enTue, 31 Jul 2012 04:00:00 -040010-year-old problem in theoretical computer science falls
http://news.mit.edu/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731
Interactive proofs — mathematical games that underlie much modern cryptography — work even if players try to use quantum information to cheat.Tue, 31 Jul 2012 04:00:00 -0400Larry Hardesty, MIT News Officehttp://news.mit.edu/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731<div class="video_captions"><img src="/newsoffice/sites/mit.edu.newsoffice/files/images/vidick.jpg" border="0" /><br /><strong>Thomas Vidick</strong><br /><i>Photo: M. Scott Brauer</i><br /><br /></div>
<div class="video_captions" style="float: left; padding: 10px 10px 10px 0px; width: 150px;"><img src="/newsoffice/sites/mit.edu.newsoffice/files/images/best-of-2012.jpg" border="0" alt="Best of 2012" /></div>
Interactive proofs, which MIT researchers helped pioneer, have emerged as one of the major research topics in theoretical computer science. In the classic interactive proof, a questioner with limited computational power tries to extract reliable information from a computationally powerful but unreliable respondent. Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they’re just as important for the insight they provide into the complexity of computational problems.<br /><br />Twenty years ago, researchers showed that if the questioner in an interactive proof is able to query multiple omniscient respondents — which are unable to communicate with each other — it can extract information much more efficiently than it could from a single respondent. As <a href="http://www.technologyreview.com/mitnews/424362/the-quantum-frontier/" target="_blank">quantum computing</a> became a more popular research topic, however, computer scientists began to wonder whether such multiple-respondent — or “multiprover” — systems would still work if the respondents were able to perform measurements on physical particles that were “entangled,” meaning that their quantum properties were dependent on each other.<br /><br />At the IEEE Symposium on Foundations of Computer Science in October, Thomas Vidick, a postdoc at MIT’s Computer Science and Artificial Intelligence Laboratory, and Tsuyoshi Ito, a researcher at NEC Labs in Princeton, N.J., <a href="http://xxx.lanl.gov/abs/1207.0550" target="_blank">finally answer that question</a>: Yes, there are multiprover interactive proofs that hold up against entangled respondents. That answer is good news for cryptographers, but it’s bad news for quantum physicists, because it proves that there’s no easy way to devise experiments that illustrate the differences between classical and quantum physical systems.<br /><br />It’s also something of a surprise, because when the question was first posed, it was immediately clear that some multiprover proofs were not resilient against entanglement. Vidick and Ito didn’t devise the proof whose resilience they prove, but they did develop new tools for analyzing it.<br /><br /><strong>Boxed in</strong><br /><br />In an interactive proof, a questioner asks a series of questions, each of which constrains the range of possible answers to the next question. The questioner doesn’t have the power to compute valid answers itself, but it does have the power to determine whether each new answer meets the constraints imposed by the previous ones. After enough questions, the questioner will either expose a contradiction or reduce the probability that the respondent is cheating to near zero.<br /><br />Multiprover proofs are so much more efficient than single-respondent proofs because none of the respondents knows the constraints imposed by the others’ answers. Consequently, contradictions are much more likely if any respondent tries to cheat.<br /><br />But if the respondents have access to particles that are entangled with each other — say, electrons that were orbiting the same atom but were subsequently separated — they can perform measurements — of, say, the spins of select electrons — that will enable them to coordinate their answers. That’s enough to thwart some interactive proofs.<br /><br />The proof that Vidick and Ito analyzed is designed to make cheating difficult by disguising the questioner’s intent. To get a sense of how it works, imagine a graph that in some sense plots questions against answers, and suppose that the questioner is interested in two answers, which would be depicted on the graph as two points. Instead of asking the two questions of interest, however, the questioner asks at least three different questions. If the answers to those questions fall on a single line, then so do the answers that the questioner really cares about, which can now be calculated. If the answers don’t fall on a line, then at least one of the respondents is trying to cheat.<br /><br />“That’s basically the idea, except that you do it in a much more high-dimensional way,” Vidick says. “Instead of having two dimensions, you have ‘N’ dimensions, and you think of all the questions and answers as being a small, N-dimensional cube.”<br /><strong><br />Gaining perspective</strong><br /><br />This type of proof turns out to be immune to quantum entanglement. But demonstrating that required Vidick and Ito to develop a new analytic framework for multiprover proofs. <br /><br />According to the weird rules of quantum mechanics, until a measurement is performed on a quantum particle, the property being measured has no definite value; measuring snaps the particle into a definite state, but that state is drawn randomly from a probability distribution of possible states.<br /><br />The problem is that, when particles are entangled, their probability distributions can’t be treated separately: They’re really part of a single big distribution. But any mathematical description of that distribution supposes a bird’s-eye perspective that no respondent in a multiprover proof would have. Finding a way to do justice to both the connection between the measurements and the separation of the measurers proved enormously difficult. “It took Tsuyoshi and me about a year and a half,” Vidick says. “But in fact, one could say I’ve been working on this since 2006. My very first paper was on exactly the same topic.”<br /><br />Dorit Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito’s paper is the quantum analogue of an earlier paper on multiprover interactive proofs that “basically led to the PCP theorem, and the PCP theorem is no doubt the most important result of complexity in the past 20 years.” Similarly, she says, the new paper “could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory.”<br /><br />The paper could also have implications for physics, Aharonov adds. “This is a step toward deepening our understanding of the notion of entanglement, and of things that happen in quantum systems — correlations in quantum systems, and efficient descriptions of quantum systems, et cetera,” she says. “But it’s very indirect. This looks like an important step, but it’s a long journey.”<br />Thomas VidickPhoto: M. Scott BrauerComputational complexity theory, Cryptography, Encryption, Interactive proofs, Quantum computing, Theoretical computer scienceAlgorithmic incentives
http://news.mit.edu/2012/algorithmic-incentives-0425
A new twist on pioneering work done by MIT cryptographers almost 30 years ago could lead to better ways of structuring contracts.Wed, 25 Apr 2012 04:00:00 -0400Larry Hardesty, MIT News Officehttp://news.mit.edu/2012/algorithmic-incentives-0425<div class="video_captions"><img src="/newsoffice/sites/mit.edu.newsoffice/files/images/algoincent.jpg" border="0" /><br /><strong>Interactive proofs are a type of mathematical game, pioneered at MIT, in which one player — often called Arthur — tries to extract reliable information from an unreliable interlocutor — Merlin. In a new variation known as a rational proof, Merlin is still untrustworthy, but he's a rational actor, in the economic sense.</strong><br /> <i>Image: Howard Pyle</i><br /><br /></div>
In 1993, MIT cryptography researchers Shafi Goldwasser and Silvio Micali shared in the first <a href="http://www.sigact.org/Prizes/Godel/" target="_blank">Gödel Prize</a> for theoretical computer science for their work on interactive proofs — a type of mathematical game in which a player attempts to extract reliable information from an unreliable interlocutor. <br /><br />In their groundbreaking 1985 paper on the topic, Goldwasser, Micali and the University of Toronto’s Charles Rackoff ’72, SM ’72, PhD ’74 proposed a particular kind of interactive proof, called a zero-knowledge proof, in which a player can establish that he or she knows some secret information without actually revealing it. Today, zero-knowledge proofs are used to secure transactions between financial institutions, and several startups have been founded to commercialize them.<br /><br />At the Association for Computing Machinery’s Symposium on Theory of Computing in May, Micali, the Ford Professor of Engineering at MIT, and graduate student Pablo Azar will present a new type of mathematical game that they’re calling a rational proof; it varies interactive proofs by giving them an economic component. Like interactive proofs, rational proofs may have implications for cryptography, but they could also suggest new ways to structure incentives in contracts.<br /><br />“What this work is about is asymmetry of information,” Micali says. “In computer science, we think that valuable information is the output of a long computation, a computation I cannot do myself.” But economists, Micali says, model knowledge as a probability distribution that accurately describes a state of nature. “It was very clear to me that both things had to converge,” he says.<br /><br />A classical interactive proof involves two players, sometimes designated Arthur and Merlin. Arthur has a complex problem he needs to solve, but his computational resources are limited; Merlin, on the other hand, has unlimited computational resources but is not trustworthy. An interactive proof is a procedure whereby Arthur asks Merlin a series of questions. At the end, even though Arthur can’t solve his problem himself, he can tell whether the solution Merlin has given him is valid.<br /><br />In a rational proof, Merlin is still untrustworthy, but he’s a rational actor in the economic sense: When faced with a decision, he will always choose the option that maximizes his economic reward. “In the classical interactive proof, if you cheat, you get caught,” Azar explains. “In this model, if you cheat, you get less money.”<br /><br /><strong>Complexity connection</strong><br /><br />Research on both interactive proofs and rational proofs falls under the rubric of computational-complexity theory, which classifies computational problems according to how hard they are to solve. The two best-known complexity classes are <a href="/newsoffice/2009/explainer-pnp.html" target="_blank">P and NP</a>. Roughly speaking, P is a set of relatively easy problems, while NP contains some problems that, as far as anyone can tell, are very, very hard. <br /><br />Problems in NP include the factoring of large numbers, the selection of an optimal route for a traveling salesman, and so-called satisfiability problems, in which one must find conditions that satisfy sets of logical restrictions. For instance, is it possible to contrive an attendance list for a party that satisfies the logical expression (Alice OR Bob AND Carol) AND (David AND Ernie AND NOT Alice)? (Yes: Bob, Carol, David and Ernie go to the party, but Alice doesn’t.) In fact, the vast majority of the hard problems in NP can be recast as satisfiability problems. <br /><br />To get a sense of how rational proofs work, consider the question of how many solutions a satisfiability problem has — an even harder problem than finding a single solution. Suppose that the satisfiability problem is a more complicated version of the party-list problem, one involving 20 invitees. With 20 invitees, there are 1,048,576 possibilities for the final composition of the party. How many of those satisfy the logical expression? Arthur doesn’t have nearly enough time to test them all.<br /><br />But what if Arthur instead auctions off a ticket in a lottery? He’ll write down one perfectly random list of party attendees — Alice yes, Bob no, Carol yes and so on — and if it satisfies the expression, he’ll give the ticketholder $1,048,576. How much will Merlin bid for the ticket?<br /><br />Suppose that Merlin knows that there are exactly 300 solutions to the satisfiability problem. The chances that Arthur’s party list is one of them are thus 300 in 1,048,576. According to standard econometric analysis, a 300-in-1,048,576 shot at $1,048,576 is worth exactly $300. So if Merlin is a rational actor, he’ll bid $300 for the ticket. From that information, Arthur can deduce the number of solutions.<br /><br /><strong>First-round knockout</strong><br /><br />The details are more complicated than that, and of course, with <a href="http://www.claymath.org/millennium/" target="_blank">very few exceptions</a>, no one in the real world wants to be on the hook for a million dollars in order to learn the answer to a math problem. But the upshot of the researchers’ paper is that with rational proofs, they can establish in one round of questioning — “What do you bid?” — what might require millions of rounds using classical interactive proofs. “Interaction, in practice, is costly,” Azar says. “It’s costly to send messages over a network. Reducing the interaction from a million rounds to one provides a significant savings in time.”<strong></strong><br /><br />“I think it’s yet another case where we think we understand what’s a proof, and there is a twist, and we get some unexpected results,” says <a href="http://www.wisdom.weizmann.ac.il/~naor/" target="_blank">Moni Naor</a>, the Judith Kleeman Professorial Chair in the Department of Computer Science and Applied Mathematics at Israel’s Weizmann Institute of Science. “We’ve seen it in the past with interactive proofs, which turned out to be pretty powerful, much more powerful than you normally think of proofs that you write down and verify as being.” With rational proofs, Naor says, “we have yet another twist, where, if you assign some game-theoretical rationality to the prover, then the proof is yet another thing that we didn’t think of in the past.”<br /><br />Naor cautions that the work is “just at the beginning,” and that it’s hard to say when it will yield practical results, and what they might be. But “clearly, it’s worth looking into,” he says. “In general, the merging of the research in complexity, cryptography and game theory is a promising one.”<br /><br />Micali agrees. “I think of this as a good basis for further explorations,” he says. “Right now, we’ve developed it for problems that are very, very hard. But how about problems that are very, very simple?” Rational-proof systems that describe simple interactions could have an application in crowdsourcing, a technique whereby computational tasks that are easy for humans but hard for computers are farmed out over the Internet to armies of volunteers who receive small financial rewards for each task they complete. Micali imagines that they might even be used to characterize biological systems, in which individual organisms — or even cells — can be thought of as producers and consumers.<br />Computational complexity theory, Computer science and technology, Crowdsourcing, Cryptography, Electrical engineering and electronics, Mathematics, Interactive proofs, Zero-knowledge proofs