Hacker News Reader

Comment by jamoes | Hacker News Reader

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.

View on HN

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/

Reply on news.ycombinator.com