Suramya's Blog : Welcome to my crazy life…

October 15, 2019

Theoretical paper speculates breaking 2048-bit RSA in eight hours using a Quantum Computer with 20 million Qubits

Filed under: Computer Security,My Thoughts — Suramya @ 12:05 PM

If we manage to get a fully functional Quantum Computer with about 20 million Qubits in the near future then according to this theoretical paper we would be able to factor 2048-bit RSA moduli in approximately eight hours. The paper is quite interesting, although the math in did give me a headache. However this is all still purely theoretical as we only have 50-60 qBit computers right now and are a long way away from general purpose Quantum computers. That being said I anticipate that we would be seeing this technology being available in our lifetime.

We significantly reduce the cost of factoring integers and computing discrete logarithms over finite fields on a quantum computer by combining techniques from Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of 10−3, a surface code cycle time of 1 microsecond, and a reaction time of 10 micro-seconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction’s spacetime volume is a hundredfold less than comparable estimates from earlier works (Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3n+0.002nlgn logical qubits, 0.3n3+0.0005n3lgn Toffolis, and 500n2+n2lgn measurement depth to factor n-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.

Bruce Schneier talks about how Quantum computing will affect cryptography in his essay Cryptography after the Aliens Land. In summary “Our work on quantum-resistant algorithms is outpacing our work on quantum computers, so we’ll be fine in the short run. But future theoretical work on quantum computing could easily change what “quantum resistant” means, so it’s possible that public-key cryptography will simply not be possible in the long run.”

Well this is all for now will post more later

– Suramya

No Comments »

No comments yet.

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress