This is the very first post in the HIVE Quantum-Resistance Community, introducing the community and outlining why I feel the existence of a living and active community looking into the subject of Quantum Resistance for HIVE is really really important.
Shor's algoritm
Quantum computing is really amazing technology that is currently emerging into the realm of becoming practically usable for very specific use-cases. One very interesting application of QC is integer factorization. There is an elegant little algorithm called Shor's algorithm that allows a quantum computer to do integer factorization. Big deal, you may think. Regular computers can do integer factorization as well, so why care about this specific use?
Well, on a regular computer, we use what is known as a General Number Field Sieve to do integer factorization. We could dive into complexity theory, and bring in that Shor's algorithm solves integer factorization in polynomial time, but a single image tells more than a thousand words:
Given that much of cryptography relies on integer factorization being hard for relatively modest numbers of n, Shor's algoritm can be a real buzz killer for public key cryptography that realies on integer factorization.
Qubits and error correction.
So why isn't quantum computing a huge problem for much of publoc-key cryptography yet ? The answer is qubits. It isn't that easy to just stack up qubits as it is to stack up traditional computing building units. Qubits are noicy, and a lot of error correcting logic is needed at the moment to get things working reliably.
We need hundreds or thousands of qubits in a single quantum computer to slice through a public key and reconstruct the private key, if the PKI relies on the dificulty of integer factorization.
Such a quantum computer is still a number of years away. In 2020, the horizon came closer a bit more than a single year as a huge leap was made in the compression of the required error correction logic needed for such a computer.
ECDSA
The ECDSA PKI signing algoritm used by HIVE and many other blockchains, doesn't rely on integer factorization. Instead it relies on an the mathematical properties of an elliptic curve. But guess what? There is an adjusted version of Shor's algorithm that should work with elliptic curve cryptography as well. The amount of qubits required to slice though a HIVE pubkey is about 1500. A number that as projected now should be possible 4 to 8 years from now.
ECDSA & blockchains
So how is ECDSA used in blockchains. There is a special little trick in ECDSA that combines signatures with public keys, that greatly limits the exposure time of public keys to quantum computing attacks. When you sign a bitcoin transaction, and do so using a tiny recovery field, the signature, combined with the transaction data allows for reconstruction of the public key. Given that a bitcoin address is a hash of the public key, a signature on a transaction that completely spents an unspent output is the first and only time the public key is exposed to the world. If bitcoin transactions were instantly final and if noone ever re-used a private key, this would make bitcoin invulnerable to QC attacks. Unfortunately reality is different.
For one, because the bitcoin blockchain is literally littered with USOs linked to a private key that has already been used to sign a transaction.
Secondly because transactions are not final instantly. There is a time window between a signed transaction being pushed to the network, and it actually becoming final.
So bitcoin has two issues with quantum resistance. Key-reuse, and the network's time-window until a signed transaction becomes final.
XMSS quantum resistant signatures
XMSS (eXtended Merkle Signature Scheme) as used in the #QRL blockchain implements what is basically an exhaustible quantum resistant signing key. Depending on creation parameters, a XMSS key could be used to sign for example 2048 transactions. This works quite well for a blockchain where only monetary value is relevant.
Not the whole answer
So how about HIVE? HIVE also uses ECDSA, but unlike Bitcoin, re-use of public keys isn't an error, its an intrinsic part of the actual architecture. In fact, not just signatures, but even the public keys of all accounts are published on the blockchain. Something like XMSS will likely solve a huge part of the QR problem for HIVE, but not without other, likely major architectural changes to the blockchain.
HIVE needs your brain
It is possible that something like the NTRU Signature Algorithm could be a better fit for HIVE. Or more likely, that something like a smart combination of both NTRU and XMSS is needed. There are also roadmap considerations to factor in. A huge pile of things to figure out.
There are still a few years left before the problem becomes real. But there isn't that much time left before we need to start discussing a roadmap to fixing things before the problem becomes real for HIVE.
Apart from that, just doing work on getting quantum resistance up and ready ahead of time might boost market confidence in $HIVE.
In short, HIVE needs us to work on this. needs YOU and your brain to be involved. Please join the HIVE Quantum-Resistance community and weigh in with your insights and ideas.
Looking forward to your posts here.