Featured Research

from universities, journals, and other organizations

Interactive proofs: Ten-year-old problem in theoretical computer science falls

Date:
July 30, 2012
Source:
Massachusetts Institute of Technology
Summary:
Interactive proofs -- mathematical games that underlie much modern cryptography -- work even if players try to use quantum information to cheat. Computer scientists show there are multiprover interactive proofs that hold up against entangled respondents.

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.

Related Articles


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 quantum computing 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.

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., finally answer that question: 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.

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.

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.

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.

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.

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.

"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."

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.

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.

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."


Story Source:

The above story is based on materials provided by Massachusetts Institute of Technology. The original article was written by Larry Hardesty. Note: Materials may be edited for content and length.


Cite This Page:

Massachusetts Institute of Technology. "Interactive proofs: Ten-year-old problem in theoretical computer science falls." ScienceDaily. ScienceDaily, 30 July 2012. <www.sciencedaily.com/releases/2012/07/120730124236.htm>.
Massachusetts Institute of Technology. (2012, July 30). Interactive proofs: Ten-year-old problem in theoretical computer science falls. ScienceDaily. Retrieved November 1, 2014 from www.sciencedaily.com/releases/2012/07/120730124236.htm
Massachusetts Institute of Technology. "Interactive proofs: Ten-year-old problem in theoretical computer science falls." ScienceDaily. www.sciencedaily.com/releases/2012/07/120730124236.htm (accessed November 1, 2014).

Share This



More Computers & Math News

Saturday, November 1, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Protests Stall Hungary's Internet Tax

Protests Stall Hungary's Internet Tax

Reuters - Business Video Online (Oct. 31, 2014) Hungary will shelve plans to introduce a tax on internet data traffic that has generated big protests over the past week. But as Amy Pollock reports the controversial issue hasn’t gone away entirely. Video provided by Reuters
Powered by NewsLook.com
Samsung's Incredible Shrinking Smartphone Profits

Samsung's Incredible Shrinking Smartphone Profits

Reuters - Business Video Online (Oct. 30, 2014) The world's top mobile maker is under severe pressure, delivering a 60 percent drop in Q3 profit as its handset business struggles. Turning it around may not prove easy, says Reuters' Jon Gordon. Video provided by Reuters
Powered by NewsLook.com
Ban On Wearable Cameras In Movie Theaters Surprises No One

Ban On Wearable Cameras In Movie Theaters Surprises No One

Newsy (Oct. 30, 2014) The Motion Picture Association of America and the National Association of Theatre Owners now prohibit wearable cameras such as Google Glass. Video provided by Newsy
Powered by NewsLook.com
Spain's New 'Google Tax' Makes News Feeds Pay For Links

Spain's New 'Google Tax' Makes News Feeds Pay For Links

Newsy (Oct. 30, 2014) Spanish lawmakers have passed new IP rules requiring aggregators to pay for linking to news sites, following a broader trend across the E.U. Video provided by Newsy
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:

Strange & Offbeat Stories


Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins