5 ms·
Grad Student Solved a Fundamental Quantum Computing Problem
- aportnoy 8y agoessentially a dupe of https://news.ycombinator.com/item?id=18167690 https://news.ycombinator.com/item?id=18167690
- deleted 8y ago[deleted]
- throwawaymath 8y agoMahadev's result is excellent by any standard and remarkable for a graduate student. It's both impressively creative and technically novel. But quantum verification has not been solved, and the headline is wrong. In essence, Mahadev developed a quantum verification protocol that relies on a post-quantum secure cryptosystem. She used an encryption scheme based on the the Learning With Errors (LWE) problem, which is one of the foremost intractability assumptions in post-quantum cryptography research. It's a great idea and a novel approach based on the marriage of two related fields of research. But the jury is still out on whether or not the LWE is actually post-quantum secure (likewise with other intractability assumptions). It probably is, but there are reasonable and credible arguments against lattice-based problems generally and the LWE family of problems in particular (which is one reason proposals based on isogenies, error correcting codes, hash-based signatures and multivariate polynomials are also under active research). Mahadev's real achievement is not solving quantum verification - but it's possible this will lead to that result. Rather as a direct result of her work we can now conclude one of the following must be true: 1. the LWE problem is not post-quantum secure, or 2. we can verify quantum computation. That's a win-win for both the quantum computing and theoretical cryptography research communities. I have suggested elsewhere that a logical next step in this research is to take Mahadev's framework and "port" it to another theorized post-quantum secure intractability assumption. My reading of Mahadev's paper is that her methodology is probably modular enough to support swapping out the LWE with any other family of post-quantum secure assumptions, not just lattice-based ones. She does highlight a few parameter choices taken from one of Gentry's lattice schemes for fully homomorphic encryption (FHE), but I don't think that should pose a significant obstacle to changing the intractability protocol. This would be very interesting because it might result in nontrivial changes to the speed or efficiency of the quantum verification system. Post-quantum cryptographic systems have different trade-offs depending on their underlying intractability assumptions; I'm interested in whether and how that would surface in quantum verification as well. Another very interesting route for further research is seeing where else cryptographic protocols can be used for creatively solving open problems in verification more generally. But that's already an active area of investigation.
- deleted 8y ago[deleted]
- killjoywashere 8y agoThe lack of inspectability, it seems to me, would make quantum computing flat-out unacceptable in a variety of problem domains, including pretty much any decision support system. Not theoretically, so much as socially. In the way nuclear reactors are unacceptably risky to many who accept a far higher death toll associated with roofers falling to their deaths installing solar. Sure nuclear saves lives, but my aunt doesn't understand it and she finds it scary.
- Schiphol 8y agoI have a B. Eng. in chemical engineering, unlike "your auntie" I understand nuclear plenty, and still think, with most everyone else educated and uneducated alike, it's MUCH more dangerous than solar.
- demygale 8y agoI’m a big proponent of nuclear energy. The benefits far outweigh the risks. But solar power has never rendered an area of the planet uninhabitable, so I understand the concern.
- Fuzzy_Logic 8y agoSolar panels do come at an environmental cost, particularly in developing economies with little environmental regulation. https://sinosphere.blogs.nytimes.com/2014/06/02/chinas-solar-panel-production-comes-at-a-dirty-cost/ https://sinosphere.blogs.nytimes.com/2014/06/02/chinas-solar...
- killjoywashere 8y agoI have a degree in physics, am now a doctor studying cancer, lived on a nuclear aircraft carrier, and was sent to Japan to help with the Fukushima response. I'm not sure I agree about the danger of nuclear, but the lower energy levels involved in solar make it so much more politically attractive, there's not much sense in pursuing new civil nuclear production.
- chasingthewind 8y ago
- jackemupguy2 8y agoBut does it fly?
- d3andj 8y agoI sincerely believe we should treat quantum computing discoveries as (long term) major 0-days, as in they should sent in confidentiality to sensitive sectors's actors, those that depend heavily on classic encryption.
- zamadatix 8y agoOr perhaps if it is believed we are close to making a quantum computer that can easily break classic cryptography we simply assume it's broken instead of waiting for the first person who wants to tell us publicly? I don't see why quantum research should be held up more than any other area when it comes to zero days. If we are going to trust people to be forthcoming I think we can trust them to decide if it should be sensitively announced.
- 3pt14159 8y agoIf you listen to natsec or intelligence Podcasts you'll hear these people stressing over quantum. We need quantum proof algorithms today, not ten years from now. For symmetric encryption this is easy, unfortunately the vast majority of our encryption protocols bootstrap with PKI. I've come to the view that because we have a physical safety problem with cyber now (cars, drones, etc) we should be shipping devices with hardware enforced one time pads and the update procedure should incorporate them with a layered approach (ie, encryption + OTP). Yes physical security is hard and OTPs shouldn't be used most places, but if the factories or update servers for Tesla are physically owned we're fucked anyway so we already have a physical security problem. Why solely trust in cryptographers that have routinely underestimated the risk of algorithmic or side-channel breach? I really want my mind to be changed here, because I don't like having opinions that are way outside the mainstream, but no matter how I dice it I don't see why we shouldn't be employing OTPs.
- rocqua 8y agoPresuming you mean One Time Pads, they are an exagerated solution. If I want to send you 1GB of data, we should not require 1GB of shared secret random data. A setup where you have e.g. 4kb of shared secret data, and use that to communicate fully randomly generated keys. Then those keys are used with symmetric encryption for the full transaction. The main issue with this is the 'shared secret' part. How would you do 'code signing' with an OTP? You'd need a shared secret with the developer. The developer can't possibly have a different shared secret with each user, and even if they could, it would mean that every user would need a different signature on their binary. So instead, there is one secret shared with everyone. But if Alice, Bob, and the Dev all have access to the shared secret, then Alice doesn't know whether Bob or the Dev made the signature. This can partially be solved by secure enclaves, but if you have the same secret on a million secure enclaves, it becomes feasible to extract that secret. Besides, it seems quite probably that secure enclaves also have side-channels. Asymmetric cryptography doesn't have this issue, because you don't rely on a user having only partial access to some data. For many interactive things, a 'chain' of shared secrets could probably be used to set up a secure channel. But for off-line usage such as attestations or proofs of authorization, that isn't possible. PKI does suck, but the biggest issue is authenticating keys, not the use of weak algorithms.