10-year-old problem in theoretical computer science falls

[anateus]

To vastly (over?) simplify:

Interactive proofs can be used to prove you have a secret without divulging it (http://en.wikipedia.org/wiki/Zero_knowledge_proofs) hence their mentioning of crypto.

These systems can be attacked in various ways, one of which is to use quantum entanglement. Edited to add: since the interactive proofs rely on probabilistically estimating the likelihood respondents can still be lying, quantum effects can be used to reduce the accuracy of these estimates. In this case, entanglement is used as a means of collusion between supposedly independent respondents.

What these researchers did was take an interactive proof that was already created to be resilient against these quantum attacks , and have demonstrated that it is in fact resilient against them.

[padobson]

So me and my partner bust these two guys on a B&E on the wrong side of the train tracks and haul their butts downtown to get confessions.

We separate 'em into to different rooms and really put the screws to 'em. We musta questioned 'em for hours because the sludge coming out of the coffee pot started to taste more like 10w30 than Folgers.

So these perps have all the answers, and we can't figure out how, because we got a strong hunch we got these guys cold. So we figure they're using quantum entanglement to keep their answers lined up. Each perp has his entangled electron, spin it right for yes, left for no, and up for maybe. So we turn up the heat and drop a Multi-prover interactive proof in their laps, and all of a sudden their stories don't line up so well anymore.

Another hour of good-cop, bad-cop, and we get one perp to roll on the other. Wasn't long till they were both singing like canaries and my partner and I had a couple of fat collars.

A job well done.

[Xcelerate]

If someone could translate that into English, that'd be great. I know a lot about quantum physics, and a lot about computer science, but I still didn't really understand what that was about. Although I did get excited.

[thebooktocome]

Have you tried looking up their paper? I normally can't glean very much from popular press releases about mathematics either.

[Strilanc]

The article states that giving quantum pseudo telepathy (http://en.wikipedia.org/wiki/Quantum_pseudo-telepathy) to provers who have been otherwise separated isn't disastrous to all interactive proof systems (http://en.wikipedia.org/wiki/Interactive_proof_system).

[anateus]

A perhaps too simple explanation that hopefully clears up a few things: http://news.ycombinator.com/item?id=4315894

[enki]

this should help: http://en.wikipedia.org/wiki/Interactive_proof_system

[clvv]

This video has a very good introduction to the problem.

https://www.youtube.com/watch?v=eAiJocr6ZKg

[philthom]

I've studied computer science, but I don't recall this theoretical problem. Perhaps its just not as popular or well known as things like P vs NP?

[nottaken]

What are the implications of all this in other areas, fields and future of humanity in general?

[swordswinger12]

It's an important result for post-quantum cryptography. If (when?) quantum computers are ever generally deployable, existing ZK protocols with multiple provers will need to be modified using this result. Besides, a theoretical result doesn't need immediate applicability to be important to humanity. The study of quadratic residues in Euler's time was a sort of mathematical recreation, but 300 years later it gave us the QR hardness assumption and the Goldwasser-Micali scheme and its derivatives.

[polynomial]

Another triumph of mathematics over physics. /s