Ask HN: What would quantum computing do to crypto currencies and blockchain?
What would quantum computing do to crypto currencies and blockchain? Would it be able to defeat the encryption? What safety measures are in place?
"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...
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