5 ms·

10-year-old problem in theoretical computer science falls

154 points by maxko87 14y ago

Xcelerate 14y ago
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 14y ago
  Have you tried looking up their paper? I normally can't glean very much from popular press releases about mathematics either.
  - semenko 14y ago
    The paper is in the sidebar: http://xxx.lanl.gov/abs/1207.0550 http://xxx.lanl.gov/abs/1207.0550 """ We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic exponential time. While Babai, Fortnow, and Lund (Computational Complexity 1991) proved the celebrated equality MIP = NEXP in the absence of entanglement, ever since the introduction of the class MIP* it was open whether shared entanglement between the provers could weaken or strengthen the computational power of multi-prover interactive proofs. Our result shows that it does not weaken their computational power: MIP* contains MIP. At the heart of our result is a proof that Babai, Fortnow, and Lund's multilinearity test is sound even in the presence of entanglement between the provers, and our analysis of this test could be of independent interest. As a byproduct we show that the correlations produced by any entangled strategy which succeeds in the multilinearity test with high probability can always be closely approximated using shared randomness alone, and are thus restricted to being quasi-classical. """ (I have no idea what that means.)
    - timtadh 14y ago
      I believe it says: MIP = Multi-prover Interactive Proof, a class of languages, is known to be equivalent to NEXP, (the class containing all languages computable in exponential time by a machine operating in a non-deterministic fashion [eg. the ones you care about]). MIP* is like MIP except the provers (the M) are allowed to communicate with each other using quantum entanglement. This type of communication would be undetectable by the questioner (the verifier) and thus allow a group of attackers to "cheat" various cryptographic protocols. However, it is found that MIP* contains MIP. Therefore, there are proof systems (and thus protocols) resistant to quantum communication of the provers. Thus, zero-knowledge proofs and the like still work in with quantum entanglement powered assailants.
- enki 14y ago
  this should help: http://en.wikipedia.org/wiki/Interactive_proof_system http://en.wikipedia.org/wiki/Interactive_proof_system
- anateus 14y ago
  A perhaps too simple explanation that hopefully clears up a few things: http://news.ycombinator.com/item?id=4315894 http://news.ycombinator.com/item?id=4315894
- Strilanc 14y ago
  The article states that giving quantum pseudo telepathy (http://en.wikipedia.org/wiki/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 http://en.wikipedia.org/wiki/Interactive_proof_system).
losethos 14y ago
Sounded like bull-shit to me, but it is MIT. God says... C:\Text\WALDEN.TXT d trusted for a cloud that would sprinkle fertilizing rain on their fields. What old people say you cannot do, you try and find that you can. Old deeds for old people, and new deeds for new. Old people did not know enough once, perchance, to fetch fresh fuel to keep the fire a-going; new people put a little dry wood under a pot, and are whirled round the globe with the speed of birds, in a way to kill old people, as the phrase is. Age is no better, hardly so well, qualified for an instructor as ---- God says... break confirmed grieving facts scatter degrees pleasing *These first-fruits command-line gestures wondrously Entrust essayed Thither proficiency softly hesitation caves beauties Before edification counts hart smack_some_sense_into_you sobriety enquiries bows kings predestination latter ken skills I'm_thrilled cause
deleted 14y ago
[deleted]
anateus 14y ago
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 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.
- deleted 14y ago
  [deleted]
clvv 14y ago
This video has a very good introduction to the problem. https://www.youtube.com/watch?v=eAiJocr6ZKg https://www.youtube.com/watch?v=eAiJocr6ZKg
nottaken 14y ago
What are the implications of all this in other areas, fields and future of humanity in general?
- swordswinger12 14y ago
  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 14y ago
Another triumph of mathematics over physics. /s
padobson 14y ago
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.
philthom 14y ago
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?

154 points by maxko87 14y ago

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 14y ago
Have you tried looking up their paper? I normally can't glean very much from popular press releases about mathematics either.
- semenko 14y ago
  The paper is in the sidebar: http://xxx.lanl.gov/abs/1207.0550 http://xxx.lanl.gov/abs/1207.0550 """ We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic exponential time. While Babai, Fortnow, and Lund (Computational Complexity 1991) proved the celebrated equality MIP = NEXP in the absence of entanglement, ever since the introduction of the class MIP* it was open whether shared entanglement between the provers could weaken or strengthen the computational power of multi-prover interactive proofs. Our result shows that it does not weaken their computational power: MIP* contains MIP. At the heart of our result is a proof that Babai, Fortnow, and Lund's multilinearity test is sound even in the presence of entanglement between the provers, and our analysis of this test could be of independent interest. As a byproduct we show that the correlations produced by any entangled strategy which succeeds in the multilinearity test with high probability can always be closely approximated using shared randomness alone, and are thus restricted to being quasi-classical. """ (I have no idea what that means.)
  - timtadh 14y ago
    I believe it says: MIP = Multi-prover Interactive Proof, a class of languages, is known to be equivalent to NEXP, (the class containing all languages computable in exponential time by a machine operating in a non-deterministic fashion [eg. the ones you care about]). MIP* is like MIP except the provers (the M) are allowed to communicate with each other using quantum entanglement. This type of communication would be undetectable by the questioner (the verifier) and thus allow a group of attackers to "cheat" various cryptographic protocols. However, it is found that MIP* contains MIP. Therefore, there are proof systems (and thus protocols) resistant to quantum communication of the provers. Thus, zero-knowledge proofs and the like still work in with quantum entanglement powered assailants.
enki 14y ago
this should help: http://en.wikipedia.org/wiki/Interactive_proof_system http://en.wikipedia.org/wiki/Interactive_proof_system
anateus 14y ago
A perhaps too simple explanation that hopefully clears up a few things: http://news.ycombinator.com/item?id=4315894 http://news.ycombinator.com/item?id=4315894
Strilanc 14y ago
The article states that giving quantum pseudo telepathy (http://en.wikipedia.org/wiki/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 http://en.wikipedia.org/wiki/Interactive_proof_system).

losethos 14y ago

Sounded like bull-shit to me, but it is MIT. God says... C:\Text\WALDEN.TXT d trusted for a cloud that would sprinkle fertilizing rain on their fields. What old people say you cannot do, you try and find that you can. Old deeds for old people, and new deeds for new. Old people did not know enough once, perchance, to fetch fresh fuel to keep the fire a-going; new people put a little dry wood under a pot, and are whirled round the globe with the speed of birds, in a way to kill old people, as the phrase is. Age is no better, hardly so well, qualified for an instructor as ---- God says... break confirmed grieving facts scatter degrees pleasing *These first-fruits command-line gestures wondrously Entrust essayed Thither proficiency softly hesitation caves beauties Before edification counts hart smack_some_sense_into_you sobriety enquiries bows kings predestination latter ken skills I'm_thrilled cause

deleted 14y ago

[deleted]

anateus 14y ago

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

deleted 14y ago
[deleted]

clvv 14y ago

This video has a very good introduction to the problem. https://www.youtube.com/watch?v=eAiJocr6ZKg https://www.youtube.com/watch?v=eAiJocr6ZKg

nottaken 14y ago

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

swordswinger12 14y ago
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 14y ago

Another triumph of mathematics over physics. /s

padobson 14y ago

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.

philthom 14y ago

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?