8 ms·
How to factor 2048 bit RSA integers in 8 hours using 20M noisy qubits
- bscphil 7y agoI haven't finished reading the paper, but maybe my biggest immediate takeaway is that significantly increasing the number of bits doesn't really help. Using the methods discussed in the paper, 4096 bit integers can be factored in less than 4x the amount of time needed to factor 2048 bit integers. In other words, should this method become practical, cryptographers couldn't solve the problem by using integers we would ordinarily consider much harder to factor.
- Thorrez 7y ago4x the amount of time, but what x the amount of qbits? My very vague impression of quantum computing is that making a quantum computer with more qbits is quite hard.
- bscphil 7y agoGood question. It looks like the rate at which more qubits are needed is slightly less than that for the time requirements. (So still under 50M qubits total, vs 20M for 2048 bit integers.) They also say later on in the paper that, given certain constraints, it should be possible to use multiple quantum computers with fewer qubits per computer - at the cost of a slight increase in the total number of qubits.
- deleted 7y ago[deleted]
- Strilanc 7y agoYes, the time scales quadratically in the key size while the space scales linearly (times a bit of logarithmic overhead on both). I think of the space as the limiting factor, since an attack that takes months to run is still worrying to cryptographers.
- fhars 7y agoYes, that is why djb‘s post quantum RSA proposal uses public key sizes on the order of one terabyte (i.e. 8 trillion bits) instead of the more common 4096 bits. I have the slight suspicion that the proposal is slightly tounge in cheek, though. See https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf
- throwawaymath 7y agoYeah, that submission was absolutely a joke. It didn't get passed to round 2 of the NIST PQCrypto Standardization CFP. Bernstein and Lange intended that to be a bit of sardonic humor poking fun at the review panel.
- cyphar 7y agoThat proposal was meant to be taken as a joke. The other proposals by djb and Lange (or possibly CSIDH -- the closest proposal to a usable post-quantum Diffie-Hellman -- which didn't make the submission deadline) seem far more reasonable.
- kelnage 7y agoThis paper may be relevant to your interests: https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf TL;DR: yes, just moving from 2048 to 4096-bit keys will not suffice. But, if you make a composite key out of many 4096-bit keys (such that the key file is now ~1Tb) then then can achieve a reasonable level of security. And yes, I do think the paper is (at least in parts) somewhat tongue-in-cheek!
- cyphar 7y agoIt's been well-known for a long time that doubling the key bits doesn't help for current public-key cryptography because you end up only requiring (approximately) double the number of qubits and a sub-exponential time increase. After all, Shor's algorithm provides a polynomial-time algorithm to solve the problem so the worst case is that doubling n will cause a fixed-power-of-two increase in time (it turns out to 2^2 in this case). It's interesting to get estimates of difficulty given noisy qubits rather than the estimates given of running Shor's algorithm on perfect qubits. However, symmetric cryptography like AES or ChaCha20 (assuming that the best-case quantum attack is a brute-force search) only gets a square-root speed-up and thus doubling the key bits actually does alleviate the quantum threat.
- jonathanstrange 7y agoSo RSA should be considered broken?
- cyphar 7y agoRSA has known to be broken by Shor's algorithm since the 90s, as well as Diffie-Hellman and elliptic-curve Diffie-Hellman. The only question is how practical is an attack going to be, and how much time do we have to switch to post-quantum algorithms. NIST has been running a competition for post-quantum cryptosystems since 2017 (approximately 10 years late to the party) and we'll see where we end up.
- mmastrac 7y agoHow plausible is it that someone could acquire this many qubits? How many doublings away are we? EDIT: [1] suggests D-wave could be 5640 by 2020, doubling approx. every two years - 12 doublings = 24 years from now. [1] https://en.wikipedia.org/wiki/D-Wave_Systems#D-Wave_2X_and_D-Wave_2000Q https://en.wikipedia.org/wiki/D-Wave_Systems#D-Wave_2X_and_D...
- ggm 7y agoD-Wave is a highly specific form targetting narrow problems. Generalized qubits I thought were smaller. Interesting to see the doubling, I've been asking for the qubit size "moores law" projection for a while but people in the business keep pushing back saying its a bad measure, but even bad measures back in the MIPS and GIGAFLOPS days made some sense. Is it really nonsensical to measure how "fast" we're achieveing stable qubits? Feels like it should be a thing.
- throwawaymath 7y agoIf you assume a Moore's Law-like increase in physical qubit capacity each year, it will take slightly under 20 years. That also assumes the rate of decoherence decreases commensurately. The reason you get pushback is because Moore's Law exists within a historical context in which it was actually plausible for exponential increases to occur each year, year after year. The field of quantum computing is so nascent that such a context is utterly alien to it. We simply don't have the economies of scale, engineering capabilities nor even theoretical groundwork required to achieve and sustain those kinds of improvements. The other reason is because transistors and qubits are not directly comparable, and you shouldn't try to infer the growth trajectory of one from the other's. So to answer your question directly - it's not nonsensical at all to measure and forecast the rate of physical qubit capacity increase. The report I cited in another comment does exactly that, which is how you can derive that 20 year estimate I made. But we don't have any evidence those kinds of annual doublings will be achievable anytime soon, so most of it comes down to educated guessing.
- ChrisLomont 7y agoQubits have not doubled every 2 years historically; I see no reason they’ll suddenly do so ever. Computers did because process shrank. Most qubits are already 1 or a few subatomic particles. There’s zero feature shrinkage possible at those scales.
- kweks 7y agoRelevant presentation on real world cipher reversing with quantum computing: https://www.phdays.com/en/program/reports/reversing-cryptographic-primitives-using-quantum-computing/ https://www.phdays.com/en/program/reports/reversing-cryptogr... Slides: https://speakerdeck.com/rlifchitz/ordinateurs-quantiques-et-futur-de-la-securite https://speakerdeck.com/rlifchitz/ordinateurs-quantiques-et-...
- Strilanc 7y agoI'm one of the authors on this paper and can answer questions if people have some.
- agsamek 7y agoHi. I would like to take the opportunity to get your opinion on quantum computing. My understanding is that there is a significant work in theoretical quantum computing done by you and many people. Results presented by you seems impressive. Congratulations. On the other hand - everything I read, hear and try to interpret about D-wave seems like a nonsense. They show approximation computations and compare it to classical algorithms that provide exact results. But classical approximation algorithms work much better than their quantum computers. I do not see how scaling this approach could lead to anything that you describe in your paper. In this regard - is my understanding of D-wave correct or does it provide some value that is better than classical computers? Can d-wave or IBM's creation be used to do computations described in your paper? Is their approach worth anything? [edit] Of course I'm not asking about now - my question is whether there is anything connected to exact results (like factoring) and exponential speed-up in d-wave approach.
- Strilanc 7y agoI don't really know a lot about D-wave to be honest. I defer to Scott Aaronson's posts [1] and to the opinion that the main criteria for success is "solve hard problems" as opposed to "solve hard problems with a quantum computer" [2]. [1]: https://scottaaronson.com/blog/?s=dwave https://scottaaronson.com/blog/?s=dwave [2]: https://youtu.be/XbFoXT73xVQ?t=355 https://youtu.be/XbFoXT73xVQ?t=355
- scottlocklin 7y agoWithout hardware, you're not solving any problems. Glass bead game != solving problems. At no point in human history as this sort of "detailed theoretical wanking" turned into progress in science; the hardware comes first.
- 7y ago
- kristianp 7y agohttps://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749
- Tepix 7y agoSo, is there some alternative quantum-resistant cipher ready (i.e. with open source implementation, say on github) that we can use today to encrypt out long-term secrets?
- TheOperator 7y agoA one-time pass is still uncrackable. Take your secret. Write it on a piece of grid paper. Fill EVERY FIELD on another piece of grid paper with random data. Transform every character on the first piece of paper based on the corresponding characters on the second piece of paper and write the result on a third piece of grid paper. Then burn the first piece of paper. It's not possible to read the 3rd piece of paper without the 2nd now. You also obscure the length by filling the second piece of paper with data.
- throwawaymath 7y agoOne-time pads are extremely impractical and error-prone. You need: 1. A secret key as long as the plaintext. 2. A consistent source of true randomness and a way of sampling it such that your secret key is truly random. 3. To never reuse a key once it's been used once. Imagine the ramifications of retrofitting servers to use one-time pads for TLS. Moreover, essentially everything we take for granted in cryptography relies on constructions which use pseudorandom permutations and generators. Even if we resolved all these problems and forged ahead in a brave new world using stream cipher-like constructions based on one-time pads, we'd still have to rethink all of public-key cryptography. This impracticality is one of the major reasons we moved on from information theoretic security to complexity theoretic security by the mid 20th century.
- TheOperator 7y agoSure of course its incomprehensibly impractical.
- gpm 7y agoFor what it's worth, quantum computers might give a provably correct source of 2 (random numbers). The version I saw (requires 2 quantum devices): http://www.henryyuen.net/fall2018/scribe2.pdf http://www.henryyuen.net/fall2018/scribe2.pdf New paper that claims to do it with only one quantum device: https://arxiv.org/pdf/1804.00640.pdf https://arxiv.org/pdf/1804.00640.pdf
- NotTheFBI 7y agoIs this the long fabled quantum computing application that breaks asymmetric cryptography?
- 34r45sdg 7y agoIts the continued advancing of the craft. Some newer techniques but an evolution of the attack. Now all one needs is a 20 Million qubit QC..
- andr 7y agoSo RSA has some 10-20 years to go. Is there a quantum computing-proof encryption algorithm, or is it just a matter of increasing key lengths?
- ozchris 7y ago> Is there a quantum computing-proof encryption algorithm This is still an area of active research. For instance, there are learning-with-errors-based cryptosystems: https://en.wikipedia.org/wiki/Learning_with_errors#Use_in_cryptography https://en.wikipedia.org/wiki/Learning_with_errors#Use_in_cr... But such systems are based on the assumption that "this type of problem is probably hard even with quantum computers". I believe we don't have anything more "quantum-proof" than that.. And of course, there are cryptosystems with unconditional security. Such as OTP.
- chess93 7y agohttps://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography
- Eldernas 7y agoYou may find this to be of interest https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Pos...
- w8rbt 7y agoMany old, hard problems are still hard even on quantum computers (SAT, TSP, etc. cannot be solved in polynomial time on quantum computers). Factoring can be done in polynomial time on quantum computers. FFT can be made even faster. But again, some classic, hard problems still stand. So don't worry, quantum computers are not magic solutions to all hard problems, just some.
- rurban 7y agoHow likely is it that for breaking 2048 bit RSA integers you'll just need 2048 unnoisy qbits? That this lowered 20M requirement is just ploy to keep people using 2048 bits, not 4K as required by GNU. It is my understanding that 2048 qbits are already in reach to well-funded state agencies.
- imtringued 7y agoIt doesn't look like there is even a need for quantum proof algorithms. An Epyc CPU with 32 cores has 20 billion transistors. Even if we can build qubits as tiny as a transistor you won't be able to break RSA with ridiculous key lengths above 2000000 bits. In reality qubits will be bigger than transistors, not all quibits can be active at the same time and there won't be the same exponential growth in the number of qubits as we have seen in conventional computers.