Papers of the day   All papers

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

Comments

Sep 28 2019 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


May 24 2019 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, 140 likes


May 27 2019 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


May 24 2019 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


May 24 2019 Quantum Bullshit Detector

Not Bullshit.
3 replies, 28 likes


May 24 2019 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


May 28 2019 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


May 24 2019 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


Jun 03 2019 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


May 24 2019 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


Aug 02 2019 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


May 24 2019 Noclone3

Added to the papers I must read #RSA #quantum #qubit
0 replies, 6 likes


Jul 06 2019 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


May 30 2019 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


May 28 2019 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


Jun 28 2019 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


May 26 2019 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


May 28 2019 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


Oct 03 2019 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


Jun 11 2019 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


Jun 03 2019 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


May 24 2019 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


Jun 16 2019 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


Oct 26 2019 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


Jun 11 2019 Noclone3

@duganist And here is a "practical" implementation that you may love too https://arxiv.org/abs/1905.09749
0 replies, 1 likes


Content