6 ms·
Quantum Attack on Public-Key Algorithm
- zkhalique 12y agoWait, so can quantum computers now crack public key cryptography, or not?
- rnovak 12y agoLooks like the algo attacked was already a quantum algorithm, not classical computing algorithm.
- rbanffy 12y agoNo - it's classical, but it was, until now, considered resistant to quantum algorithms (as in a QC would not yield a significant improvement over a classical computer).
- gliese1337 12y agoOnly if we can actually build general purpose quantum computers. The news here is that a new quantum algorithm has been developed to attack public key cryptography; other quantum algorithms that attack certain kinds of cryptography were already known. None of them matter practically until we have computers that can actually run them, which we don't, but the discovery of another new attack algorithm means that developing such computers would be a slightly bigger deal than we thought it was before.
- apendleton 12y agoThis one is also noteworthy because the algorithm it attacks was developed specifically with resistance to quantum attacks in mind, unlike the breed of public-key crypto currently in use, which is widely known to be vulnerable to quantum attacks.
- tptacek 12y agoThat may be true of Soliloquy, but I'm not sure it's the case that lattice problems were originally researched as an antidote to QC. Lattice theory has applicability to cryptography in general, so it's natural that people explored its suitability as a crypto primitive. I don't think it's reasonable to draw the conclusion from this paper that "cryptographers set out to foil QC and in this case failed". One derivative scheme in a broad class of lattice crypto designs fell, that's all. Lattice crypto has very strong post-quantum crypto marketing, because of NTRU.
- tptacek 12y agoThe news here is that a new quantum algorithm has been developed to attack one very specific form of public key cryptography.
- gruntled 12y agoIf anyone can build a big enough quantum computer (enough qubits) and prevent it decohering (that is, keeping it quantum long enough) to run Shor's algorithm, standard public key crypto like RSA would be broken. That has been known in theory since the 90s. But if anyone ever builds such a quantum computer it isn't necessarily the end for public key crypto because there is a workaround that will work on classical computers, and that is to avoid trapdoor functions that can be broken by Shor's algorithm. So if a quantum computer comes along that can break, say, 256 bit RSA, we can save public key crypto by everyone switching to a different algorithm. That's the idea of post-quantum cryptography. And although RSA might be broken by a future quantum computer we can still have some sort of public key cryptography. From the looks of this blog post, though, one of the new post-quantum public key algorithms can be broken. At least it could be if anyone ever makes a big enough quantum computer. And there's still the possibility that someone will find a trapdoor function that will be quantum resistant, so it isn't the end for all public key crypto. tl;dr One more public key scheme might have fallen to a quantum algorithm. But the quantum hardware isn't there yet, so it's OK for now.
- SapphireSun 12y agoI talked to a dude who made an interesting point about quantum computers. Quantum computations rely on particles behaving in a "quantum manner" in order for Shor's algorithm to reduce the big O complexity in factoring integers. However, at a certain size, you won't be able to entangle all the particles because there will be so many they'll start to behave like a macro material. If true, this implies that quantum methods will only work up to a certain key size. Above that, you could run quantum computers in parallel, but now you're scaling your efficiency linearly instead of super-linearly, so hopefully having a huge (maybe impractically huge?) key size would be a sufficient defence. I understand that RSA gets substantially slower with larger keys though, so maybe it wouldn't be practical even if the key fits easily in memory. I'm not an expert in physics or security, but I'd love for a physicist or cryptographer to comment as I thought that was a really intriguing argument.
- jamoes 12y agoLattice-based public key schemes are designed to be quantum resistant. So this is a troubling development, because it might indicate that other lattice-based public key schemes are vulnerable to similar attacks. It might be very difficult or even impossible to create quantum-proof public key schemes. Fortunately, though, a quantum-proof signature scheme (meaning no encryption or decryption, just signing) has already been developed: Lamport Signatures. These rely on the security if hash algorithms (such as SHA256), which are not weakened by the existence of quantum computing.
- api 12y agoIf PKC turned out to be almost impossible post-QC, boy would that ever change the world of computing, networking, pretty much everything. It would mean everything would have to run on pre-shared secret keys. It would also be the absolute end of Bitcoin and derivatives, at least as far as I know.
- nightcracker 12y agoI don't think you read the post you replied to. Bitcoin requires secure signing and hashing, which are post-quantum secure (hash functions and Lamport/Merkle signatures).
- api 12y agoI read it. Bitcoin also relies on elliptic curve crypto, which will fall to QC. Without a replacement, the entire concept of cryptocurrency as we currently know it falls.
- tptacek 12y agoPractical quantum cryptanalysis is already the end of Bitcoin, which relies on ECC algorithms that will fall to QC. (Maybe you're making the broader statement, that if QC turns out to make all forms of public key crypto insecure, regardless of the hard problem they're based on, then it won't even be possible to design a working alternative to Bitcoin.)
- tptacek 12y agoThe subtext of Schneier's post is that a lattice encryption scheme was found vulnerable to a QC algorithm, which is meaningful because lattice encryption schemes are seen as a promising post-quantum crypto scheme --- that is, a scheme that would, unlike RSA (IFP), DH (DLP) and ECC (ECDLP), remain secure even if it becomes feasible to deploy large-scale quantum computers. Two things worth knowing: * There are multiple hard lattice problems in number theory (the paper refers to one of them in the conclusion). And other lattice schemes have been found vulnerable, to non-quantum attacks. * There are multiple hard problems not involving integer lattices that are believed to be hard for quantum computers. McEliece, for instance, is another well-known candidate for post-quantum public key crypto, and it's based on linear codes, not lattices. Lamport signatures[1] realize public key crypto purely from hash functions (which aren't hugely weakened by QC.) A good intro to these issues: http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf http://pqcrypto.org/www.springer.com/cda/content/document/cd... Nick Weaver's "what if all trapdoors are vulnerable to QC" comment seems a little premature. [1]: http://en.wikipedia.org/wiki/Lamport_signature http://en.wikipedia.org/wiki/Lamport_signature
- amckenna 12y agoI wonder how the attack would fair against other Lattice-based schemes such as NTRU, which was recently open sourced. https://en.wikipedia.org/wiki/NTRU https://en.wikipedia.org/wiki/NTRU https://github.com/NTRUOpenSourceProject/ntru-crypto https://github.com/NTRUOpenSourceProject/ntru-crypto