Quantum Attack on Public-Key Algorithm | Hacker News Reader

Quantum Attack on Public-Key Algorithm

schneier.com

95 pointsjonbaer25 comments

The 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/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

Lattice-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.

If 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.

I 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).

I 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.

Practical 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.)

Public keys are only stored as a hash in the blockchain though (assuming no address re-use). Is RIPEMD-160 vulnerable to QC?

Addresses that have been sent from will be vulnerable because their public key will be displayed in the outgoing transaction. One-use addresses will not be vulnerable, as their public keys are indeed stored only as hashes in the blockchain, but the algorithm is not only RIPE, but something like SHA256(RIPEMD-160(SHA256(Public_Key))). I dont know about RIPE, but sha256 should be QC resistant. Thus if you do not reuse addresses you should be safe against QC.

> It would also be the absolute end of Bitcoin and derivatives, at least as far as I know.

Not really, because bitcoin only relies on the signature aspect of PKC. So, bitcoin could move over to Lamport signatures, which are not affected by quantum computing.

Lamport signatures are larger than ECDSA signatures, so blockchain bloat would be an issue. But presumably by then hard drives and all other computing specs would have increased substantially.

Here's an interesting article by Vitalik Buterin which explains how the transition could take place: http://bitcoinmagazine.com/6021/bitcoin-is-not-quantum-safe-...

Could you describe how such a cross over could happen smoothly? Seems like there would be mass panic, all the mining rigs would have to re assemble etc.

That's really the problem I foresee. It'd be extremely hard to pull off without a bank run or a speculative frenzy. Financial markets are unbelievably skittish about uncertainties.

Announce a transition time a few years into the future so the miners don't get a capital loss. Code clients to switch over to the new algorithm at the transition time. When the transition finally comes, even those with slightly out of date client will switch over, since it was coded far in advance.

Wouldn't this require quantum computing to be developed relatively gradually and in the open? Seems likely that a gov or company will suddenly reveal it or have it exposed.

Sudden, catastrophic leak of an operational QC would definitely be a cryptogeddon scenario.

I guess it's a good thing that Dan Bernstein (one of the early evangelists for PQ crypto [1]) has been focusing on (pretty) fast code-based quantum-resistant cryptography lately, instead of lattice-based crypto:

http://cr.yp.to/talks/2013.06.12/slides-djb-20130612-a4.pdf

http://binary.cr.yp.to/mcbits-20130616.pdf

[1] http://pqcrypto.org/

I 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://github.com/NTRUOpenSourceProject/ntru-crypto

Wait, so can quantum computers now crack public key cryptography, or not?

Looks like the algo attacked was already a quantum algorithm, not classical computing algorithm.

No - 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).

Only 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.

This 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.

That 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.

The news here is that a new quantum algorithm has been developed to attack one very specific form of public key cryptography.

If 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.

I 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.

Reply on news.ycombinator.com