Ask HN: What would quantum computing do to crypto currencies and blockchain?

https://news.ycombinator.com/item?id=29636864

by Blackstone4 • 5 years ago

8 5 5 years ago

news.ycombinator.com

What would quantum computing do to crypto currencies and blockchain? Would it be able to defeat the encryption? What safety measures are in place?

PaulHoule• 5 years ago

Just like an ASIC miner beats every other kind of Bitcoin miner, a Quantum Miner might be so much faster than an ASIC miner that it wins every time.

bitxbitxbitcoin• 5 years ago

Same thing it will do to other industries. Force devs to update to quantum resistant algorithms.

mikewarot• 5 years ago

Assuming it can be done at all, it's just going to be like more Moore's law. The algorithms that work fastest have shifted because CPUs got faster faster than RAM and I/O. This will be an even faster CPU.

m1m1ck• 5 years ago

"All cryptocurrencies are not the same. Today, they share a common quantum vulnerability through use of non-quantum safe Elliptic Curve Digital Signature Algorithm (ECDSA) digital signatures yet they have very different risks of quantum attack"

"The underpinning digital signature scheme (Elliptic curve) is vulnerable to a quantum computer attack."

"Migration to an alternative quantum safe digital signature scheme will require a ‘hard fork’, a non-compatible new blockchain created." https://eprint.iacr.org/2021/967.pdf

same/related question & answers: https://bitcoin.stackexchange.com/questions/10323/how-vulner...

olliej• 5 years ago

I mean the hashing itself won't be overly impacted as the best case is grover's algorithm which is a sqrt() improvement in complexity, coupled with what looks like a significantly lower speed for QC vs nonQC I doubt in the short term it will be game changing - longer term obviously it will be due to asymptotic complexity being reduced.

The bigger issue is the keys, similar to RSA, ECC can be "broken" by Shor's algorithm. Again the speed of early QCs probably means it won't be an immediate "all our keys are belong to them" scenario, but as QCs improve and error levels go down and performance goes up it will become increasingly untenable to rely on ECC or any other hidden subgroup based algorithm.

Happily there are a number of quantum resistant algorithms available. McEliece[1] is a super easy to understand algorithm, it is robust against all computation models. I can't recall if it was actually proved to be unbreakable but I vaguely recall that that may be the case (I have a book somewhere but it may be in my office and I don't go to work any more :D ).

The real problem with post quantum cryptography as I understand it, is not the lack of quantum resistant algorithms - McEliece has been around since the 70s, learning with errors since the 80s, and the vector one who's name I forget since at the latests the 90s - it's that the key sizes are large. Possibly not so large that they're impractical for blockchain nonsense, but certainly too large to be used in TLS. So most PQC algorithm work is focused on reducing key sizes, the problem is doing so runs the risk of introducing structural features in the keys that can weaken or break the expected security level.

[1] The core principle is super easy to understand. Basically you can create an error correcting code matrix that can correct k errors, and mangle it with a permutation matrix. This mangling can be performed completely randomly so there are no biases to leverage as with HSP algorithms like ECC. You essentially end up publishing that mangled matrix as your public key.

Encryption is super easy, it's just a matrix multiplication of the public key and the message. At this point you have got anything secure as an attacker just inverts the public key and can get your message out. So this is where the security happens: You randomly flip k bits of the encrypted message. Now if an attacker tries to use the inverted public key they get garbage out. Only the recipient can decode the message.

To decrypt the recipient can apply the inverse of their permutation matrix, leaving them with a stream of data covered by their error correcting code. They can then decode the message with that code, and correct all the errors you added, thus ending up with the original message.

To me this is super easy to understand.

That said from the literature it seems like LWE or the vector one (SVP?) are considered better, but I do not maths hard enough to understand them :D

Ask HN: What would quantum computing do to crypto currencies and blockchain?

Related Stories