23 ms·
Breaking RSA with a quantum computer?
- TacticalCoder 4y ago> A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. If a quantum computer can break 2048-bit RSA, what about elliptic curves?
- TillE 4y agoElliptic curves are also vulnerable to Shor's algorithm. However, there are several new algorithms for asymmetric cryptography, such as Google's NewHope: https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography...
- vlovich123 4y agoI had the same question as OP and you seem to have misinterpreted the question. Specifically this article is about showing a meaningful reduction in the Quantum bits required for Shor's algorithm by pairing it with lattice reduction (whatever that means). Does this approach of combining classical lattice reduction technique + quantum Shor's hold for elliptic curves? Are there any other problems beside cracking crypto algorithms that this technique could be applied to that might actually be useful vs just a more complicated attack vector?
- molticrystal 4y agoWho was the guy and what was the flawed and retracted paper mentioned in the below quote from Schneier's article? >In email, Roger Grimes told me: “Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers…but reviewers found a flaw in his algorithm and that guy had to retract his paper.
- deleted 4y ago[deleted]
- psyfi 4y agoSchnorr's "This distroyes the RSA cryptosystem"?
- worldsavior 4y agoEven if it's not true, it shows that RSA is breakable by the near future.
- deleted 4y ago[deleted]
- thesz 4y agoHere's an implementation of Schnorr's algorithm with an attempt to estimate the amount of work needed to factorize big numbers: https://github.com/lducas/SchnorrGate https://github.com/lducas/SchnorrGate It also contains some links to critique of the Schnorr's algorithm paper. It looks like either much more p_n-smooth integer pairs are needed or the size of the p_n-smooth integers should be much bigger than estimated by original Schnorr's paper. Or both estimations are off. As the paper discussed Schneier relies on the assumptions of the (classic) Schnorr's algorithm, it may also be off in the calculations as well.
- nowherebeen 4y agoI just watch this yesterday about post quantum cryptography. https://youtu.be/_C5dkUiiQnw https://youtu.be/_C5dkUiiQnw
- pelasaco 4y agoI remember that some small countries, running DPI in their up-link were just storing their whole encrypted traffic to - when this day comes - be able to decrypt the traffic and see who was conspiring against the government back in the days and then start the witch hunt. Maybe this day is coming. Maybe its already there for some degree.
- simne 4y agoIn Russia few decades lobbied initiative, to store all country traffic for some amount of time, for law enforcement agencies. As I know, now this reborn-ed to store just connection initiation data (tcp syn from tcpdump, gsm call originate/receiver numbers, datetime stamp and duration). In Ukraine, I hear inside, one law enforcement agency asked big provider ~ in 2000 to gather all emails. Co-owner said, "ok, you will got it". Than he few weeks gather old hdds from everywhere, and once sent to this agency small truck with few hundreds hdds, filled with data. After that, at least 10 years, nothing similar asked.
- pelasaco 4y agothere were/are countries in africa with small uplink, pretty easy to store everything in flows, pcaps and then extract encrypted attachments offline, run different tools and techniques to identify adversaries (that in that region, are mostly seem as deadly enemies)
- simne 4y agoYes, and Africa is not alone. Colleague said, he considered to build internet in Uzbekistan, even visited country. What he see, they have all very unfriendly or extremely conservative (Afghanistan) countries around, so he cannot just buy external internet channel. Internet there extremely slow, most time near impossible to use, only email working (but could delay for few hours). To send tweet or whatsapp, start app, push "send" and lay phone/tablet alone turned on, and in few hours will see "message delivered".
- 4moola 4y agoIt's high time to transition from RSA to the unbreakable TUPLEZZ (www.tuplezz.com)
- itcrowd 4y agoHuge, if true. However, many such claims have surfaced before and turned out to be dudds. For now, I am taking it with a spoon of salt but with an interest of any follow-ups and peer review.
- K0balt 4y agoI think history will show that the current state of the art quantum cypher breaking is well ahead of what is being discussed here.
- barathr 4y agoYeah, I think this is a sign that while, as the post notes, it's not clear that this is a 100% airtight paper/algorithm, there are major advancements happening in this space.
- gfaster 4y agoIn an update on the article, it reveals that it relies on an algorithm that breaks down with larger N for an unknown reason. It seems like we're safe for now.
- esjeon 4y agoEven when it worked, QC itself is not massively deployable right now. Agencies will be sucking their thumbs while everyone migrates to something stronger or even quantum-proof algorithms. No drama.
- stek29 4y agoHN discussion for the paper itself: https://news.ycombinator.com/item?id=34235964 https://news.ycombinator.com/item?id=34235964
- deleted 4y ago[deleted]
- pvg 4y agoIt's not an HN discussion if there's no discussion there.
- gjsman-1000 4y agoI'm surprised nobody has written a thriller yet where a new mathematical algorithm is found (maybe something to do with primes?), all encryption suddenly collapses, and with that we go into a psuedo-apocalypse where nobody is sure whether anything is authentic anymore. Banks can't share cash, ID systems are useless, we've still got electricity but no functioning internet, hardware root of trust is shattered...
- somat 4y agoOne of the neater bits of world building/subplots in the book "A fire upon the deep" is their ship is a freighter with a cargo full of one time pad keys. that is, the encryption you would revert to in a world where factorization is easy.
- omoikane 4y ago"Summer Wars"[1] features breaking keys as a plot element, with a passing mention of Shor's Algorithm. The rest of the movie is mostly unrelated to math. Good movie though. [1] https://en.wikipedia.org/wiki/Summer_Wars https://en.wikipedia.org/wiki/Summer_Wars
- jsmith99 4y agoSymmetric encryption should still be unbreakable even against quantum computers or any advances in prime numbers. Given we currently trust CAs they could switch to something like Kerberos.
- gambiting 4y agoIn the worst possible case we just switch to the one time pad encryption, which makes things inconvenient but literally can't be cracked by any computer or algorithm(tldr: the length of the key is as long as the length of the message, so a message can decode into anything and you can't tell whether the text you decoded is the right one or not). So a scenario where literally no encryption is available seems far fetched.
- tptacek 4y agoThere's any number of less subtle and more important problems with this idea, but another problem you have here is that one-time pads only provide confidentiality, not integrity.
- advisedwang 4y agoEven if this particular scheme doesn't work at scale, the writing is on the wall for conventional crypto. If you are encrypting data that will be at rest for more many years it's time to start think about migrating to post-quantum crypto so you don't end up one day discovering you're entire corpus is vulnerable.
- gjsman-1000 4y agoPost-quantum cryptography is not necessarily secure either. One of the four finalists in a NIST competition for post-quantum cryptography [SIDH] was suddenly, out of the blue, shattered with an algorithm that could break it in hours on a laptop. Turns out it was secure against quantum computers but insecure against classical computers. If you want to be safe, you might almost consider standard cryptography on one of the three-remaining post-quantum algorithms to be (hopefully) safer. Also this might be bad news for Bitcoin in the ultra-long-term...
- Grimburger 4y ago> If you want to be safe You use post-quantum with a vetted algorithm in a hybrid scheme, usually this just involves concatenation or hashing.
- g_p 4y agoMy understanding is that Bitcoin, used correctly, is effectively quantum safe. Since the "recipient" address of a UTXO is expressed as a hash, a user does not broadcast their public key until after they spend the funds. If you follow good practice, you make a single transaction, sending funds to the recipient, and the "change" to yourself, in a new wallet address (addressed by the hash of its public key). This means the public key is never visible to an attacker until its balance is zero. Therefore, to attack this and steal funds through false transactions, you effectively need both a pre-image attack on SHA256 (so you have a valid public key to match the UTXO address), and a way to solve the discrete logarithm problem, breaking ECDSA (on the Secp256k1 curve), so you can sign using the private key corresponding to that public key. SHA256 would come under Grover's algorithm, I believe, which would give you 128 bits of security under a quantum attack. That is still pretty good going.
- meltyness 4y agoA note to cast further suspicion on the immediate risk severity: The researchers indicate use of a computer built with superconducting qubits in the abstract, to that, superconducting qubits present barriers such as - limited coherence time due to common atmospheric muon events, and resulting phonons - limited topological connectivity, further increasing needed coherence time.
- reikonomusha 4y agoLimited coherence time is not explained as simply as "atmospheric muon events". There are a variety of reasons, some environmental, others a result of imperfect fabrication, etc. that contribute to decoherence, gate error, etc.
- meltyness 4y agoI know that, but I recall specific literature reflecting the specific effect mentioned[0] and it seems intuitive that the surface area and orientation currently in use for these qubits may potentiate the effect, I think the other effects you list are barriers to other qubit registers as well. [0] https://ai.googleblog.com/2022/01/resolving-high-energy-impacts-on.html?m=1 https://ai.googleblog.com/2022/01/resolving-high-energy-impa...
- emptybits 4y ago"And there’s the nagging question of why the Chinese government didn’t classify this research" Would like to hear informed thoughts on any state's pros and cons of sharing such obviously weaponizable discoveries.
- deleted 4y ago[deleted]
- johncessna 4y agoAs a guess, if you're the only one who knows about this, it's one hell of a zero day. Once used though, the cat is out of the bag and industry will race to patch it. Yes, it'll take time. If I were a country who could easily just drop bombs on people to cause destruction, then I'd rather leak something that I have no defense against in the hopes it gets patched rather than save it as a tool to use.
- kadoban 4y agoThere is more to diplomacy and war than destruction. If you can read your adversary's private messages, you can do a lot better than blowing their shit up.
- matthewdgreen 4y agoThis is not my area, but I wanted to mention this before speculation got out of control: some quick feedback from colleagues is that the analysis in this paper seems to assume Schnorr's claims from 2021 [0] without detailed supporting evidence that these claims are true for large parameters like the ones needed to factor RSA-2048. But these claims are viewed skeptically, and this paper doesn't provide much evidence to change that. [0] https://eprint.iacr.org/2021/933 https://eprint.iacr.org/2021/933
- yuhong 4y ago[dead]
- gronky_ 4y agoYou divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_code https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap https://www.ibm.com/quantum/roadmap
- andrewla 4y agoIf this roadmap is accurate for the present, the types of qbits here are NISQ qubits, so not useful for any sort of generalized computation no matter how many they have. Which is to say that Osprey has 433 qubits, so should be capable of 86 fault tolerant error corrected qubits, so they should be able to factor (not bothering with the math) AT LEAST ONE NUMBER using Shor's algorithm, and yet they cannot.
- krastanov 4y agoIf the paper is to be believed you are wrong in two different ways: 1) If the paper is right, they are claiming they need 300ish physical qubits that can sustain about 1000 gates before decohering. No need for scalable error correction. 2) Independently of the veracity of the paper, if you actually need logical error corrected (and fault tolerant) qubits, you need error correcting codes with much more severe overhead than the 5-qubit code. The 5-qubit code is a pedagogical example, not something that would actually work under realistic conditions. And even the 5-qubit code needs quite a few extra ancillary qubits for fault tolerance (which is more expensive than simple error correction).
- greggarious 4y agoWhat practical things can be done once RSA is broken?
- quotemstr 4y agoDecrypt decades of pre-PFS archived encrypted internet traffic.
- deleted 4y ago[deleted]
- jokoon 4y agoso just increase to 4096 or 8192 bits or beyond?
- TacticalCoder 4y agoWhy is this downvoted? Ain't it exponentially harder to break RSA using qubits each time you double the key length? Until we switch to quantum resistant algorithms, we can keep doubling the key length for some time no? 8192 bits should still be acceptable speed wise (if we consider that 2048 bits is broken, then I'll take slower operations over broken keys any day of the week).
- adgjlsfhk1 4y agoBecause it isn't. This paper (alegedly) uses sublinear qbits (that's the whole point).
- 3np 4y agoWhat isn't what?
- adgjlsfhk1 4y agoThe number of qbits isn't exponential in key length with this paper (if it's correct)
- krastanov 4y agoNo, if you have a scalable quantum computer (which no one has yet), then doubling the key size just requires doubling the number of logical qubits. That is for asymmetric encryption that uses "hidden subgroup problems", like RSA. We have newer asymmetric algorithms that are resistant to quantum attacks, they are just not well tested yet.
- jeandejean 4y agoJudging by the current difficulties of building a quantum computer with bigger number of qbits, I'd assume scaling linearly isn't trivial at all. So increasing key size should definitely increase security, if not exponentially, at least buying a lot of time?
- shockeychap 4y ago> Honestly, most of the paper is over my head—both the lattice-reduction math and the quantum physics. Yeah, that alone is impressive. Schneier led a group that wrote Twofish, which was one of the AES finalists before losing Rijndael.
- tptacek 4y agoIt's not in fact that impressive. The math for all sorts of cryptography goes over Schneier's head (as he sort of infamously implied with elliptic curve, over a decade ago). That's normal! Cryptographers specialize. Having a really careful, fine-grained, up-to-date intuition for differential cryptanalysis is crucial for designing hashes and ciphers, but less so for a key exchange. Not writing this to dunk on Schneier so much as to relate that cryptography is specialized, and that generally there aren't a lot of people that you'd expect to be ultra up on PQ key exchanges and modern block cryptography.
- Strilanc 4y agoI want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm starts by picking a random seed and you can show that some choices of seed simply don't work. He proves a lower bound on how many have to work. Also, given a working seed, sometimes the quantum sampling process can correctly return a useless result. He bounds how often that can occur as well. He never says "I think this problem is rare so it's probably fine", instead he says "this problem is at least this rare therefore it is fine". Essentially the only real problem not addressed by the paper was that it required arbitrarily good qubits... so he went and invented quantum error correction [2]. The paper being discussed here [3] does not strike me as meticulous. It strikes me as sloppy. They are getting good numbers by hoping potential problems are not problems. Instead of addressing the biggest potential showstoppers, they have throwaway sentences like "It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA". How many shots are needed for each sample point fed into the classical optimization algorithm? How many steps does the optimization algorithm need? How do these scale as the problem size is increased? How big are they for the largest classically simulable size (RSA128 with 37 qubits according to their table)? These are absolutely critical questions!... and the paper doesn't satisfyingly address them. Is there somewhere where I can bet money that this doesn't amount to anything? 1: https://arxiv.org/abs/quant-ph/9508027 https://arxiv.org/abs/quant-ph/9508027 2: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493 https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2... 3: https://arxiv.org/abs/2212.12372 https://arxiv.org/abs/2212.12372