13 ms·
Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory
- stirlo 6y agoJust to be clear such a machine has not yet been built. This is only a theoretical paper at the moment.
- reagent_finder 6y agoYeah, I was thinking "Waaait, aren't they at <100 qubits still?"
- deleted 6y ago[deleted]
- elephantum 6y agoDo I understand correctly, that largest quantum computer that exists today contains less than 100 qubits? Also it does not seem that there's an exponential grow in this area: https://www.statista.com/statistics/993634/quantum-computers-by-number-of-qubits/#:~:text=Quantum%20computers%20by%20number%20of%20qubits%20achieved%20up%20to%202019%2C%20by%20organization&text=The%20statistic%20shows%20the%20number,new%20quantum%20computer%20by%20IBM https://www.statista.com/statistics/993634/quantum-computers.... They hit the wall in 2017. We should be safe for now :)
- cameronperot 6y agoIBM has 1000 qubits on their roadmap by 2023 [1]. I'm interested to see how that goes, and what we can learn from it about scaling up these systems into the thousands of qubits. Edit: for anyone interested in learning more about quantum computation, I have a list of resources on my website [2]. [1] https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadmap/ https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadm... [2] https://cameronperot.com/resources/#quantum-physics https://cameronperot.com/resources/#quantum-physics
- akvadrako 6y agoSince I didn't see it mentioned, I assume those are 1000 noisy qubits, so they'll require error correction. I wonder how many ideal qubits they are equivalent to.
- megiddo 6y agoAnd the error rate of 10^-3 seems problematic, as well.
- CodesInChaos 6y agoThose quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography. https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm https://crypto.stackexchange.com/questions/59795/largest-int... A 2019 paper manged to factor 21 on a 16 qubit ibmqx5, but failed to go up to 35: > the algorithm fails to factor N=35. This is due to the cumulative errors coming from the increasing number of two-qubits gates necessary to implement the more complex MEF needed for this case https://arxiv.org/abs/1903.00768 https://arxiv.org/abs/1903.00768
- graderjs 6y agoJennifer and Peter Shor wrote a limerick that seems relevant: If computers that you build are quantum, Then spies of all factions will want 'em. Our codes will all fail, And they'll read our email, Till we've crypto that's quantum, and daunt 'em. And Volker Strassen responded at a conference: To read our E-mail, how mean of the spies and their quantum machine; Be comforted though, they do not yet know how to factorize twelve or fifteen. Source: http://www-math.mit.edu/~shor/notapoet.html http://www-math.mit.edu/~shor/notapoet.html
- CodesInChaos 6y ago> Till we've crypto that's quantum, and daunt 'em. Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.
- _hl_ 6y ago"Secure against quantum" doesn't really mean much because too little is known to make that claim confidently. AFAIK the term generally refers to algorithms that don't rely on factoring being hard, but instead make some different hardness assumptions that we currently don't have classical or quantum algorithms for.
- DebtDeflation 6y ago>largest quantum computer that exists today contains less than 100 qubits The numbers reported in the press are physical qubits not logical qubits. You need multiple physical qubits + error correction to create a single logical qubit. The main type of error correction used today is something called "surface codes". With this type of error correction it's estimated that MILLIONS of physical qubits will be required to create a SINGLE fully error corrected logical qubit. https://www.ncbi.nlm.nih.gov/books/NBK538709/ https://www.ncbi.nlm.nih.gov/books/NBK538709/ We do not have actual quantum computers today and we don't seem to be much closer to having them than we were a decade ago. What we have are really interesting quantum science experiments that get misrepresented by the press (and a handful of companies with a commercial interest in doing so).
- mikewave 6y agoThe largest production quantum computer that exists today - as in, the largest you personally can get access to - has 5,436 qubits: the D-Wave Advantage system. Admittedly, it's not a gate-model machine that can run Shor's Algorithm, but it is a quantum computer, and at more than double the number of qubits plus far higher inter-qubit connectivity than our previous D-Wave 2000Q, it definitely demonstrates tremendous progress. If you have a moment, you can sign up to use it for free at https://cloud.dwavesys.com https://cloud.dwavesys.com - we have an online IDE, Jupyter notebook training material and tons of docs, a community forum, and of course some shiny demos that submit problems to the live QPU if you want to try them out.
- hk1337 6y agoSo, then I am definitely good using 4096 RSA?
- upofadown 6y agoSure, but ridiculously large key sizes like 4096 bit RSA are not really any more resistant to quantum computing than smaller sizes. This is probably a joke, but the suggestion was made that you might be OK with a 1 TB RSA key size: * https://www.schneier.com/blog/archives/2017/05/post-quantum_rs.html https://www.schneier.com/blog/archives/2017/05/post-quantum_...
- bcaa7f3a8bbc 6y agoThat pqRSA paper by DJB is a joke, but it's mathematically correct and an interesting thought experiment - RSA really becomes post-quantum when you use a 1 TB key because it outgrows what Shor's algorithm can scale at that point. The paper is actually better, it proposed an original algorithm, GEECM, that's faster than Shor's algorithm for numbers with many small factors, then also showed pqRSA is safe from GEECM. He even submitted the algorithm to the NIST Post-Quantum Competition for review (among his more practical algorithms like Classic McEliece), it's just hilarious. > DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!" https://crypto.stackexchange.com/questions/59591/why-is-pqrsa-in-the-nist-pqc-submissions https://crypto.stackexchange.com/questions/59591/why-is-pqrs... Here's his explanation of the idea: https://cr.yp.to/talks/2017.06.27/slides-djb-20170627-pqrsa-16x9.pdf https://cr.yp.to/talks/2017.06.27/slides-djb-20170627-pqrsa-...
- SAI_Peregrinus 6y agoGiven the number of Star Wars references in the various NIST Post-Quantum Competition scheme names (CRYSTALS-KYBER, SABER, NewHope) I'm rather sad he didn't call it "Post Quantum RSA - The Phantom Menace".
- deleted 6y ago[deleted]
- SilasX 6y agoI would have preferred they title it "How to factor 2048 ..."
- jepler 6y agoBesides the number of qbits, is "multimode memory" real or hypothetical?
- codeulike 6y agoFrom the abstract: We suggest realizing such an architecture using a microwave interface between a processor made with superconducting qubits and a multiplexed memory using the principle of photon echo in solids doped with rare-earth ions. I would guess hypothetical
- dzdt 6y agoQuantum computers of this scale are probably 5-15 years out. Basically this is a warning that if you have secrets that should still be kept secret over that timeframe, you should not be using RSA today.
- hannob 6y agoI'd be willing to bet a lot that it's not 5 years, and am still quite confident it's not 15. Of course nobody knows, but these things are still very far from anything that is running today.
- cronin101 6y agoAt this rate, maybe the first commercial Fusion plants will have asymmetric quantum encryption securing their management portal.
- albertgoeswoof 6y agono no no, you need high performance enterprise grade http on port 80 listening on all interfaces for a power plant portal
- tatersolid 6y agoBuilt with Java(TM) EnterpriseServletContainerGeneratorSingletBean Technology. Has been continuously running since GWB was in office, not a single patch applied!
- dandellion 6y agoBut even if I agree that it's almost impossible in 5 years it's better to be cautious and assume it could be broken in 5. And there's also the fact it could be broken by some governments long before anyone finds out I guess.
- carlmr 6y agoEven if it was, 177days for cracking your password with the most advanced technology that exists in the world, still means you have some very powerful enemies. Practically you don't need to think about it.
- tbabej 6y agoThis paper basically explores a hypothetical scenario where scaling quantum memory ends up being cheaper than scaling computational qubits. The title (or abstract) unfortunately does not mention the quantum memory requirements at n=2048 explicitly. For factoring 2048 RSA integers, the technique proposed in the paper would require ~430 million memory qubits (see the table at top of page 16).
- bunnie 6y agoI'm trying to make sense of the 'memory qubits' e.g. 'spatial modes' in the paper. Do you know if they are they a sort of...quantum flip flop? Is this also a hypothetical structure, or have they been built and shown to be able to reliably store and retrieve quantum state in such spatial modes? 430 million is a much, much larger number than their headline 13436 qubits...
- oldgradstudent 6y agoSo magic computer could be more effective with more magic memory than with more magic processing power, right?
- bdamm 6y agoQuantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.
- gallerdude 6y ago...would be like bringing mathematics to Mesopotamia. Can you expound on this? What sort of breakthroughs are bottlenecked by developments in quantum computing?
- Craighead 6y agoTemperature
- ThePhysicist 6y agoThe authors hide the fact that this would require millions of memory qubits (which need to be as accurate as the normal qubits), so the title is a bit misleading IMHO.
- zozbot234 6y agoThat's just 6.56 qubits per factored RSA integer - or alternately, 11.57 days per factored RSA integer. Quite impressive either way!
- codeulike 6y agoThats not what they mean. Title should read '2048 bit'
- kjrose 6y agoIt's an interesting theory but like most items in quantum computing it is purely theoretical. Not sure how much it would cost to build. I hope someone gets a grant to work out the engineering difficulties in this.
- reikonomusha 6y agoI would say most items in quantum computing are not theoretical. They’ve been demonstrated. Moreover, quantum physics is by far our most accurate theory of physics we have What is still hypothesized is whether these elements, which have been demonstrated to work in small numbers (<100), will work in large numbers.
- AlanYx 6y agoUntil someone successfully demonstrates an error-corrected qubit, it's probably fair to still call a lot of work in the quantum computing realm theoretical.
- davidmurdoch 6y agoThis reminds me to listen to MC Frontalot's Secrets from the Future again. If you haven't heard it yet, you're in for a treat! https://youtu.be/FUPstXCqyus https://youtu.be/FUPstXCqyus
- isolli 6y agoSide question: if quantum computers fulfill their promise, won't they break encryption as we know it? Are we ready for that kind of upheaval?
- hannob 6y agoYes and kinda yes. There's a standardization process going on for post quantum cryptography at the US NIST. Results expected before the almighty RSA-breaking quantum computer arrives. There's still a concern about store-and-encrypt-later (i.e. someone can store encrypted communication today and decrypt it once a QC is available), and how relevant that is depends on some unknowns (how many years to you expect your comms to be secret? how many years till a usable QC is available?).
- KMag 6y agoNote, for instance, that Google ran an experiment where Chrome connecting to Google hosts used both conventional elliptic curve Diffie-Hellman over Curve25519 and post-quantum "New Hope" RLWE. A hash of the results of the two key agreements was used for ChaCha20 encryption of the keystream. A store-and-decrypt attack in this case should be required to break both conventional Curve25519 and experimental New Hope. Note that the best known quantum attacks on ChaCha20 cut the key size in half, so 256-bit ChaCha20 should still be fine, as long as your key agreement protocol is quantum-resistant.
- BelenusMordred 6y ago> Are we ready for that kind of upheaval? Quite sure cryptographers are ahead of the curve, they are a conservative bunch. There's multiple finalists in the NIST post-quantum comp with different quantum-hard mathematical properties. An over-abundance of lattice cryptography being standardised could possibly be a problem in the long term though. Asymmetric public key crypto and signatures being broken is the only real threat, there's no theoretical issues with symmetric crypto, hashing or MAC's. A quantum break already has a multi-billion dollar bounty on it in the form of cryptocurrency wallets which would be hard to fight against in the form of wages or violent coercion. This is probably the best evidence on Earth that no one actually has this capability.
- jakozaur 6y agoOne day you can start calculating private keys based on public keys. This is the biggest crypto puzzle: find private key of Sathoshi Bitcoin wallet with 1 mln bitcoins. Over $50 Bln prize for one crypto puzzle. This would be AlphaGo moment of quantum computing if you could make that one attack successful even while paying huge price (e.g. years of quantum datacenter work).
- unilynx 6y agoCashing out and actually getting $50B may be as much of a challenge as finding the private key
- umvi 6y agoWhy, do people actively monitor that wallet for activity? I'm assuming if any BTC at all moves out of that wallet it'll cause a massive correction to BTC price as people can no longer assume that those bitcoins are off the market.
- vbezhenar 6y agoI'm sure that enough geeks have all kinds of triggers to spot that kind of activity.
- Invictus0 6y agoHypothetically, you could publicly announce that you'll sell the stash at the rate of 1% per year, to demonstrate faith in the continued growth of bitcoin in order to finance <humanitarian project> and reassure the market that it won't massively crash.
- renata 6y agoAnd you could even sign the announcement with one of Satoshi's wallet keys.
- gjm11 6y agoImagine that you find Satoshi's private key and start trying to sell his million bitcoins. Approximately one minute after you start this process, someone will figure out that either (1) bitcoins no longer securely belong to anyone or (2) Satoshi thinks selling off all his bitcoin is a good idea. Approximately two minutes after you start this process, the price of bitcoin will plummet. Sorry, you will not be taking home $50B today.
- 2iP1zbR 6y agolayman here. i understand that if said theoretical computer did exist, encrypted stored data using today's standards is for the most part compromised, outside of further obfuscation, which the popular opinion seems to believe only helps so much. that means the past is compromised, with some amount of implementation afterwards. i've always wondered just how much the future is compromised. i've always thought about encryption this way: P = some degree of computational power A = some small unit of P, like a laptop B = the largest unit of P practically possible under the same laws of physics as A (data encrypted by A cannot be "cracked" by B in a reasonable amount of time) so in my head, so long as a normal civilian can access qubit technology (likely questionable), encryption still works by increasing the number of rounds. what am i missing? edited for format, then again for clarity
- monocasa 6y agoQuantum computers will have civilian access. They already do in fact. And the issue is that they change _the complexity_ for some algorithms so adding rounds isn't going to help. We'll just migrate to quantum resistant algorithms like we migrated away from MD5.
- wealthyyy 6y agoQuantam is a scam. Repeat, it's a bullshit. Read Scott Locklin blog post.
- stkai 6y agoCould anyone take a stab at the cost of such a computer, if it were possible to build today? Like, I know there are computers of <100 qubits, but how much does one cost?
- haltingproblem 6y agoI fear it is my obligation to point out this excellent screed by Scott Lockin: "Quantum computing as a field is obvious bullshit". A beautiful excerpt from the article: When I say Quantum Computing is a bullshit field, I don’t mean everything in the field is bullshit, though to first order, this appears to be approximately true. I don’t have a mathematical proof that Quantum Computing isn’t at least theoretically possible. I also do not have a mathematical proof that we can or can’t make the artificial bacteria of K. Eric Drexler’s nanotech fantasies. Yet, I know both fields are bullshit. Both fields involve forming new kinds of matter that we haven’t the slightest idea how to construct. Neither field has a sane ‘first step’ to make their large claims true. ..... “quantum computing” enthusiasts expect you to overlook the fact that they haven’t a clue as to how to build and manipulate quantum coherent forms of matter necessary to achieve quantum computation. A quantum computer capable of truly factoring the number 21 is missing in action. In fact, the factoring of the number 15 into 3 and 5 is a bit of a parlour trick, as they design the experiment while knowing the answer, thus leaving out the gates required if we didn’t know how to factor 15. The actual number of gates needed to factor a n-bit number is 72 x n^3; so for 15, it’s 4 bits, 4608 gates; not happening any time soon. [1]: https://scottlocklin.wordpress.com/2019/01/15/quantum-computing-as-a-field-is-obvious-bullshit/ https://scottlocklin.wordpress.com/2019/01/15/quantum-comput...
- TheRealPomax 6y agoexcept we already use qubits in the real world, and we already use entangled pairs in banking, so it's not really all that bullshit anymore. Quantum computers with a significant number (e.g thousands, but really, millions) of qubits, however, are still quite a ways away. But clearly not in the realm of bullshit anymore.
- haltingproblem 6y agoI would love to learn more, please share any relevant useful links. Edit: Cursorily googled and did not find a reference for usage but plenty of papers talking about potential applications. Might be wrong though.
- mikeodds 6y ago