10 ms·
Quantum Computer Comes Closer to Cracking RSA Encryption
- jcr 11y agoSomehow the submitted link got mangled: http://spectrum.ieee.org/tech-talk/computing/hardware/encryptionbusting-quantum-computer-practices-factoring-in-scalable-fiveatom-experiment http://spectrum.ieee.org/tech-talk/computing/hardware/encryp... The article has a broken link to the paper abstract, which is "Realization of a scalable Shor algorithm" available here: http://science.sciencemag.org/content/351/6277/1068 http://science.sciencemag.org/content/351/6277/1068 And I'm yet to find a full copy of the paper anywhere, but it sure looks interesting... Edit: Ah, here it is: http://arxiv.org/abs/1507.08852 http://arxiv.org/abs/1507.08852 There's also "Compiling quantum algorithms for architectures with multi-qubit gates" which cites the above: http://arxiv.org/abs/1601.06819 http://arxiv.org/abs/1601.06819
- xyzzy123 11y agoThe title is also a bit clickbaity. Yes, QC are "closer" to breaking RSA... but... "Briefly, the new work uses Kitaev’s version of Shor’s factoring algorithm, running on an ion-trap quantum computer with five calcium ions, to prove that, with at least 90% confidence, 15 equals 3×5..... So, what’s new is that a QC has now factored 15 “scalably”: that is, with much less cheating than before." - (Scott Aaronson).
- dang 11y agoOk, we changed the URL from http://spectrum.ieee.org/tech-talk/computing/hardware/ http://spectrum.ieee.org/tech-talk/computing/hardware/. Thanks! Btw, http://www.scottaaronson.com/blog/?p=2673 http://www.scottaaronson.com/blog/?p=2673 (via https://news.ycombinator.com/item?id=11235186 https://news.ycombinator.com/item?id=11235186) is also about this.
- osterbit2 11y agoI'm familiar with the implications of quantum computing on factorization and thus DEcryption but have heard very little about about quantum computing enabling ENcryption until the last paragraph of this article ("...Chuang expects to see quantum encryption methods that will inscribe sensitive data into the very states of atoms") Very curious about current state of this research (relative to the current state of quantum decryption)--any experts in the room?
- ianopolous 11y agoNot an expert on Quantum cryptography, but an ex particle physicist here. The basic idea is that using a quantum channel (sadly means new hardware, so not over tcp), eavesdropping becomes impossible without destroying the quantum state of the signal (guaranteed by the laws of Quantum Mechanics). If an eavesdropper intercepted a message, that would be detectable and you can drop that packet. Wikipedia has a good intro: https://en.wikipedia.org/wiki/Quantum_cryptography https://en.wikipedia.org/wiki/Quantum_cryptography
- smaddox 11y agoAnd yet, isn't it true that MITM attacks still work, as long as the MITM has the same hardware?
- roywiggins 11y agoTheoretically, if you intercept in the middle, you destroy the pattern that you observe. This is a physical quantum effect, and will happen no matter what hardware you use Since the intended use is key distribution, a MITM is fine as long as you can detect it reliably: you can keep sending new keys until one isn't eavesdropped upon, and then use that key.
- AnthonyMouse 11y agoBut how do you detect it reliably?
- q4h555qh5 11y agoIf someone intercepts the quantum key, it will modify it 25% of the time. If you randomly measure (and verify publicly with the sender) a fraction of your total key and find it unmodified, it means the rest of the key probably is too, up to a certain security factor. By starting with a longer key and measuring more of it (or doing privacy amplification, for example xor-ing multiple keys together), you can get as much security as you want. It also means the security is everlasting, meaning someone cannot retroactively break your key in 100 years using some mega-computer.
- shireboy 11y agoThe irony that the SSL cert is invalid for the NSA FAQ linked to in the article... https://www.iad.gov:8443/iad/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/assets/public/upload/CNSA-Suite-and-Quantum-Computing-FAQ.pdf https://www.iad.gov:8443/iad/library/ia-guidance/ia-solution...
- rbut 11y agoNot entirely true. - Safari; Certificate is fine - Chrome; Certificate error due to SHA-1 signatures - Firefox; Unknown issuer Why is the DoD root certificate in OSX but not in Firefox?
- pmalynin 11y agoBecause Illuminati
- NeutronBoy 11y agoBecause someone would have filed a bug on Bugzilla arguing for it to be removed on moralistic grounds I bet. I'm all for having principles, but you have to accept that it'll break for your users.
- steve19 11y agoFrank Hecker : "Accepting this bug. My initial comments: The last time I dealt with the issue of the DoD PKI it was essentially a DoD-internal PKI for the use of U.S. military personnel (active or retired), DoD civilian employees, DoD contractors, and (maybe) allied forces (e.g., NATO). It was not intended for the use of the general public (whether U.S. citizens or not), and I'm not aware that members of the general public would ever be in a situation where they would encounter SSL-enabled web servers, S/MIME email, or signed code that used DoD-issued certificates. Based on that I would consider this an "intranet" CA (albeit for a very large intranet) and based on my previous "meta-policy" comments I would recommend not including this in Mozilla et.al. I'll leave this bug open for a period of public comments, and then I'll close it with "WONTFIX" unless someone can provide compelling reasons why I should do otherwise." Seems reasonable to me.
- baby 11y agoNice clickbait, Scott Aaronson on this: http://www.scottaaronson.com/blog/?p=2673 http://www.scottaaronson.com/blog/?p=2673
- kenny-log_ins 11y agoyep. whenever i read anything sensational about QC I immediately head over to his blog to read about what it actually means.
- semi-extrinsic 11y agoBest quote from the post you link to: "If one counts demonstrations not based on quantum computing, some people have claimed even earlier precedents for the 3 x 5 = 15 theorem."
- Yver 11y agoIf I understand correctly, this quantum computer came closer to cracking RSA the same way shifting in your chair gets you closer to Jupiter.
- lisper 11y agoA better analogy would be that it's the same way that building a glider got us closer to an A380.
- sp332 11y agoWerner von Braun oversaw development of some awfully small crummy rockets https://youtube.com/watch?v=Ii7uwp1SRIM https://youtube.com/watch?v=Ii7uwp1SRIM (imagine the ones even before these!) but also oversaw the Saturn 5 which lifted every person who walked on the moon. We understand the physics, now it's a matter of engineering and funding!
- marcosdumay 11y agoWell, "we" (I didn't I wasn't there) understand the physics since the 1920s.
- yxhuvud 11y agoExcept that a whole lot of basic research into stuff like viable rocket fuels etc simply didn't exist yet that early.
- 11y ago
- nickysielicki 11y agoI'm sure we'll be the first to hear when they actually do. /s
- warrenmar 11y agoIf you want to know more about Quantum Computation, there is an edX course (https://www.edx.org/course/quantum-mechanics-quantum-computation-uc-berkeleyx-cs-191x https://www.edx.org/course/quantum-mechanics-quantum-computa...). It goes over the Shor algorithm and the quantum Fourier Transform that leads up to the Shor algorithm.
- zer01 11y agoI have a feeling that we're going to wake up one day and there will be a legitimate breakthrough in quantum computing, leading to RSA no longer being a legitimate standard for security. My question to HN: Have any of you guys attempted to come up with a plan for if/when this happens? Are there any algorithms in suites like OpenSSL that are quantum-resistant? Is SSL/TLS even compatible with a post-quantum world?
- tptacek 11y agoThere are not, not in OpenSSL. Viable post-quantum encryption is a hot research area right now. There are a number of approaches that seem promising; some of them, like hash-based, lattice-based, and code-based crypto, are actually relatively old concepts that were pushed aside because RSA is more efficient, but which regain their edge if quantum computers become viable. https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography The trick with all of this is that there isn't all that much cryptanalysis work of some of the more promising PQ schemes, so trying to preemptively adopt them just in case quantum computers learn to factor numbers bigger than 15 is likely to do more harm, in the short term, than good.
- whitegrape 11y agoMy plan: don't rely on the secrecy of anything encrypted now with RSA to remain secret in 20 years, and never use it for encrypting data-at-rest. Hell, Schneier already increased his PGP key size to 4096 bits, I don't think it's a stretch to think 2048 could be broken classically by USA-level actors in the not-too-distant future. But since you're not using RSA for data-at-rest, more for transient "messages", hopefully the value of anything intercepted and stored for 20 years will be relatively low.
- deleted 11y ago[deleted]
- saittam 11y agoHere's good talk by djb covering the big picture and some options for alternatives that are thought to be quantum-resistant. https://media.ccc.de/v/32c3-7210-pqchacks https://media.ccc.de/v/32c3-7210-pqchacks
- Joof 11y agoCould anyone point me in the direction of how quantum hardware is currently designed? I'd love a technical explanation.
- scottlocklin 11y agoI love it when people tout a result as being "only 15-30 years away." Is there any large scale human technological research project in all of human history which lasted 20 years and actually produced what was promised? There is no incremental path here; any time someone says "20 years" it means they have no idea how to do this thing.
- whitegrape 11y agoThe human genome project. Their goal when starting was "this will take 15 years", they completed it in 13. The Apollo program: goal of less than 9 years (end of the decade) when it was proposed in 1961 to land a man on the moon and return him to Earth, completed in 1969. If you go back quite a ways, I'm willing to bet at least some of the innovation-required Castles and Cathedrals and Pyramids of history were completed "on schedule" with it known up front that they would take many years to finish. I suspect a lot of projects are accurately classified as 10-30 years away, given a certain level of funding and a dedicated team. Absent that, they may very well take twice as long or more. I always like to see what these long-term oriented institutions like SENS and MIRI say they would do if they had x times more money, to see that they've got a plan -- fortunately those ones do give that information.
- scottlocklin 11y agoNeither of these numbers is equal to or greater than 20. 20 is a "I don't know how to do this" number of years. 10 is building a dam. Quantum computing has already been "a thing" for longer than 20 years; careers have been made ... people have retired. Today we get news of 1 bit worth of progress made since 2001. Now we can factor 30 instead of 15....
- mattlutze 11y agohttps://en.wikipedia.org/wiki/Large_Hadron_Collider#Cost https://en.wikipedia.org/wiki/Large_Hadron_Collider#Cost The LHC was approved for construction start in 1995. The wiki article doesn't capture it but you can bet the science behind the design of the LHC wasn't all done the year before. It didn't achieve its first real goals until 2015. https://en.wikipedia.org/wiki/LIGO https://en.wikipedia.org/wiki/LIGO LIGO was dreamed up in the 1960's to detect gravitational waves. Took until 2002 to get the first one built big enough to theoretically detect them, and until 2015 to finally get measurements demonstrating the existence of waves. Real science is slow. This "20 years means I don't know" business is indicative of perhaps not appreciating the difference between basic science and applied science/engineering. I know we're used to engineering projects pumping out new awesome tech every couple years, but basic science is hard and takes a long time.
- IvanK_net 11y agoAfter reading "a quantum computer that could someday factor any number, and thereby crack the security of traditional encryption schemes." I understood, that author has no idea what he's talking about.
- kriro 11y agoI don't think this article implies we are anywhere close to feasible quantum computers but...if I worked on the assumption that sufficiently powerful quantum computers exist (thought experiment), what would be my available and usable options today? Encrypt everything I deem important enough with symmetric encryption? I have found this: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography But am not sure what is considered the state of the art. Stehle-Steinfeld seems like the most promising option from my very uninformed position. Supersingular elliptic curves also seem to have nice properties but I have to admit I don't even fully comprehend them. Would love for a crypto expert to chime in :)
- DropbearRob 11y agoI've always been confused by the claims of quantum computing, I'm hoping one of the clever folk here can steer me to an understanding. Doesn't the very nature of superposition and uncertainty make determining when the process has solved the problem impossible to determine? Its like, when you look at the data, you change it, and if it wasn't solved, you've already forced it into a state, and if it was solved, by observing it you may change it to something else. How are these problems solved with quantum computing?
- akarve 11y agothat is in part what this discovery is about: how to read out and disentangle the solution from superposition. the roots of the answer to your question are in "shor's algorithm," which is the original proposal for factoring integers in polynomial time with high probability.
- DropbearRob 11y agothanks akarve, I shall read abot "shor's algorithm"
- gt565k 11y agoAnyone know if this is the dwave quantum computer or a different one?