Papers of the day   All papers

How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

Comments

Conner Brown: If you’re worried about quantum cracking ECDSA after the Google announcement (like I was), here’s some perspective: State-of-the-art quantum computers are ~50 qubits. The amount required to derive your private key is ~20 million qubits. https://arxiv.org/pdf/1905.09749.pdf

2 replies, 158 likes


Craig Gidney: This is the paper that was split into four: https://arxiv.org/abs/1905.09749 "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits". Combines improvements from the other papers into >100x less spacetime. Previous comparable results took a billion qubits over a day. https://t.co/D6Iucp9bDE

12 replies, 135 likes


Binni Shah: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits : https://arxiv.org/pdf/1905.09749.pdf (pdf)

1 replies, 74 likes


Peter McMahon: "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://arxiv.org/abs/1905.09749 -- the perfect paper to send anyone who asks how far away we are from seeing a quantum computer break 2048-bit RSA

2 replies, 59 likes


Matt Turck: Quantum computers will be able to solve in 8 hours computational problems that would take regular computers 317... trillion years. But, using the history of flight as an analogy, right now we are in 1903 @cjsavoie, CEO @zapatacomputing #hardwiredNYC https://t.co/Rv6DpB1dFf

2 replies, 33 likes


Mercedes Gimeno-Segovia: .@preskill addresses the hype about code-breaking w/ quantum computers: “To reach scalability we must cross the daunting ‘quantum chasm’ from hundreds to millions of physical qubits. Recent work estimates that we need 20 million qubits to break RSA crypto system.” #Q2B19

0 replies, 29 likes


dabacon: A factor of a hundred here, a factor of a hundred there. Next thing you know we'll have factored faster.

0 replies, 28 likes


Quantum Bullshit Detector: Not Bullshit.

3 replies, 28 likes


Bharath Ramsundar: This paper is worth a close read for folks in the crypto community. It might be more feasible than previously anticipated to break RSA with noisy qubits. 20 million noisy qubits is a high bar still, but one that feels 10-20 years not 50 years out. https://twitter.com/CraigGidney/status/1131720243376558080

3 replies, 22 likes


mjos\dwez: Craig Gidney, Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits." Looks to me like their physical and algorithmic QC design is at pretty advanced state? https://arxiv.org/abs/1905.09749

3 replies, 17 likes


Alfonso Muñoz: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits - https://arxiv.org/abs/1905.09749

1 replies, 14 likes


Ion busters: The papers keep coming from @arXiv_quant_ph today! Next up @CraigGidney discusses how you can factor a 2048 bit RSA integer in 8 hours using 20 million noisy qubits. https://arxiv.org/pdf/1905.09749.pdf We always used to tell people it took billions and years from https://bit.ly/30PZ2v0 ! https://t.co/7DpobYw9ZC

0 replies, 7 likes


Noclone3: Added to the papers I must read #RSA #quantum #qubit

0 replies, 6 likes


Jacopo Bertolotti: "Although Shor’s algorithms run in polynomial time, the constant factors hidden by the asymptotic notation are substantial." (From: "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits": http://arxiv.org/abs/1905.09749 )

2 replies, 6 likes


Joeri Beerts: End of the password. By using quantumcomputing, a 2048bit RSA- encrypted password can be hacked in 8h. https://arxiv.org/pdf/1905.09749.pdf

0 replies, 5 likes


Physics arXiv Blog: How a quantum computer could break 2048-bit RSA encryption in 8 hours https://www.technologyreview.com/s/613596/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/ https://t.co/yZSZdEVW8j

0 replies, 4 likes


Guillaume Verdon: @jpdowling @MJBiercuk I would say we need 18±4 years at the current rate of qubit count exponential growth. https://arxiv.org/abs/1905.09749

1 replies, 3 likes


Arrigo Triulzi: C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits” […abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses 3n+0.002nlgn logical qubits…] https://arxiv.org/abs/1905.09749

0 replies, 3 likes


QRAvalanche: The #SecretaryOfQuantumComputers has been contacted again by the press, on the recent #quantumcomputing breakthrough: https://arxiv.org/abs/1905.09749 #QRL $QRL @QRLedger #quantum #bitcoin #ecdsa https://t.co/F9DeEcGB8a

0 replies, 2 likes


Noclone3: @APompliano This one by a Google researcher on an accelerated Shor algorithm for breaking RSA (with future quantum computers) https://twitter.com/CraigGidney/status/1131720243376558080

0 replies, 2 likes


Jacky Martin: A more efficient method for factoring 2048 bit RSA integers, interesting if you are into Quantum Physics: https://arxiv.org/abs/1905.09749 This will become more important for cryptographic codes protecting sensitive information. https://arxiv.org/abs/1008.2390

0 replies, 2 likes


Alan Woodward: Orders of magnitude improvement in factoring 2048 but it’s still 20million qubits (optimistically) so don’t panic just yet https://arxiv.org/pdf/1905.09749.pdf

0 replies, 2 likes


snannerb1: @Jason Just read through all these replies and not a single mention of the fact that quantum computers have and will continue to advance with time , https://mobile.twitter.com/peterlmcmahon/status/1131728997627203584 ... there is quantum resistant crypto out there and encryption is what holds this all together.

0 replies, 2 likes


Gavin Crooks: A superconducting qubit is about 1mm on a side. If you stacked them 3d they would be about 1mm apart. That's about 1 million qubits per liter. So factoring 2048 bit RSA will need about 20,000cc of qubits. We're going to need a bigger dilution refrigerator.

0 replies, 1 likes


Noclone3: @duganist And here is a "practical" implementation that you may love too https://arxiv.org/abs/1905.09749

0 replies, 1 likes


HotComputerScience: Most popular computer science paper of the day: "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://hotcomputerscience.com/paper/how-to-factor-2048-bit-rsa-integers-in-8-hours-using-20-million-noisy-qubits https://twitter.com/CraigGidney/status/1131720243376558080

0 replies, 1 likes


Andrei ILchenko: I like how Bruce Schneier put, “Our work on quantum-resistant algorithms is outpacing our work on quantum computers” https://www.schneier.com/blog/archives/2019/10/factoring_2048-.html in response to this paper: https://arxiv.org/abs/1905.09749 on factoring 2048 bit RSA moduli

0 replies, 1 likes


Content

Found on Sep 28 2019 at https://arxiv.org/pdf/1905.09749.pdf

PDF content of a computer science paper: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits