There’s been a lot of chatter about quantum computing destroying bitcoin.
Quantum computers are really effective against Elliptic curve encryption, and RSA encryption. While RSA isn’t used as much in cryptocurrencies, Elliptic Curve Digital Signature Algorithm or ECDSA is the cryptographic algorithm used by Bitcoin to make sure that only the owner can spend their coin.
For bitcoin, one of the biggest issues is the fact that this public key is exposed when a transaction is made. And when the public key is exposed, there’s a possibility that a quantum computer could reverse the calculation and actually find the private key from the public key, given a large enough quantum computer. You use the private key to “sign” the transaction to say, yes, this is me, I approve this. If someone else has it, they can also make a transaction that you don’t approve.
And there are new cryptocurrencies coming out that are saying they are quantum safe, quantum resistant - which means stand up to known attacks by quantum computers.
The ones I’m going to cover here are some of the more popular ones, but also revolve around signature schemes, specifically, the rise of Winternitz One time Signature (W-OTS) and eXtended Merkle Signature Scheme (XMSS) .
Quantum Resistant Ledger
QRL has quantum in its name, so obviously quantum resistance has been the core north star of this cryptocurrency from the beginning.
QRL is the first industrial implementation to utilize IETF specified XMSS; a hash-based, forward secure signature scheme with minimal security assumptions and reusable addresses that comes with NIST approval
It’s always been the case that QRL has been built with non-Elliptic curve encryption, for digital signatures, unlike Bitcoin.
What is XMSS? It’s the eXtended Merkle Signature Scheme (XMSS). They each consist of two components—a onetime signature (OTS) scheme and a method for creating a single, long-term public key from a large set of OTS public keys.
XMSS uses the Winternitz signature scheme, or W-OTS. WOTS starts with 32 random numbers, which are 256 bits each. For each random number, we hash 256 times, using SHA-256. So this becomes our “private key”.
XMSS can be used with different hash functions - SHA-256 and SHAKE-256 are recommended in this document.
A Merkle tree is also called a hash tree. It’s a structure with nodes, a top node, and children nodes below it that are linked. So for a Merkle tree, the non leaf nodes, with a leaf node being a node that does not have a child, is labeled with the hash of the data block, and every non-leaf node is labelled with the hash of the labels of its the child nodes, so it’s hashing the hash.
The hash can be very short compared to the amount of data, which makes it very efficient.
To create a hash tree, the OTS public keys are hashed once to form the leaves of the tree, and these hashes are then hashed together in pairs to form the hash of the next level up. Those hash values are then hashed together, and so on, until all of the public keys have been used to generate a single hash value (the top node, or root), which will be used as the long-term public key.
It is “NIST approved” in some way. It is an approved standard for Stateful Hash-Based Signature Schemes. However, NIST is still going through the process of going through the official post-quantum encryption recommendations, and those seem to be mostly concentrated in lattice based, error correcting code based, and multivariate based cryptosystems.
Those results haven’t been released yet, so we’ll see if this will be a recommendation that NIST places. It does seem that hash based schemes are, as far as we currently know, secure from quantum computing attacks, but NIST is expected to make multiple recommendations in their official post-quantum cryptography report.
But many may claim that Grover’s algorithm could potentially weaken hash based schemes! Well, that could be true, but Grover’s algorithm is not as devastating a speedup. Breaking RSA/ECC encryption with a quantum computer using Shor’s algorithm is exponentially faster, while Grover’s algorithm is quadratically faster.
So, for AES encryption, AES-256 bit encryption becomes the equivalent of AES-128 bit using Grover's Algorithm.
And it hasn’t been shown yet that Grover’s algorithm could be used for SHA-256 problem solving, and there are collision attacks on classical computing that are much better than Grover’s algorithm. So, we shouldn’t compare Grover's algorithm to just classical serialized search, but to the best case scenario.
So, as we were expecting, Quantum Resistant Ledger was built in mind with quantum security, and using a good candidate.
Mochimo says on their website:
In 3-5 years, Quantum Computing is poised to break ECDSA encryption leaving BTC, ETH and all ERC-20 tokens unsafe for transactions and as a store of value.
I personally do not think that we will get to a place where quantum computers can break RSA and ECC encryption in 3-5 years.
It would take 2500 qubits to break elliptic curve discrete logarithms, and 4000 for RSA encryption. However, these are perfect, "logical" qubits. Because of error correction and other necessary processes, we need many more physical qubits to make one logical qubit. The quantum error correction overhead is very large. Some estimates say that 10 million physical qubits would be needed, even the lowest estimates say millions. And different quantum hardware systems need different amounts of quantum error correction. While some quantum computing hardware may scale up more easily or the qubits themselves are easier to create, they’re likely needed to have a lot more overhead, and are harder to control, so their error corrected to logical qubit threshold is even larger.
Mochimo uses the EU’s PQCryptos approved WOTS+, which is the Winternitz signature scheme, whichI just talked about, and like I mentioned, so far, hash-based algorithms do seem to be resistant to quantum computing attacks so far.
We checked out the algorithms that were peer reviewed and acknowledged by the EU backed Quantum Research group PQCRYPTO and chose the WOTS+ algorithm.
PQCRYPTO is a legitimate group with advisors like Dr. Mosca who is at University of Waterloo, a top quantum school, and is deeply involved in quantum cryptography research and educational initiatives in this space.
However, the PQCRYPTO website recommendations have not been updated in a while. The recommendations are from 2015. While there hasn’t been anything that would dramatically change the recommendations in the quantum space, this algorithm hasn’t been broken by quantum computers, it’ll be interesting to see recent updates since the field is moving quickly.
We then wrote and vetted our quantum code with the algorithm’s originator: Andreas Hülsing.
I did find an article that mentions that Andreas Hulsing reviewed and wrote a “Review of Mochimo’s WOTS implementation” paper, however I could not find the original, so it looks like they wrote their own implementations. Here’s what the article that talked about the paper quoted, but if anyone can find the original paper, please comment and let me know: https://medium.com/@qrcollector/i-never-said-wots-isnt-part-of-xmss-877463f17e57
We analysed the C implementation of WOTS provided by Mochimo. We did not find any bugs or security issues in the core implementation (in the /wots subfolder). Under the assumption that the code provided in example.c shows how the signature scheme is used to sign transactions, we identified several issues worth reconsideration. At least one issue weakens the security of the used signature scheme. In addition we identify a possibility for optimization, reducing the size of a transaction from 8,792 bytes to 2,360 bytes.
So it uses the same scheme as QRL, which are, as far as we know, quantum secure.
IOTA is not claiming quantum security or encryption on the home page, however, ages ago, there were claims that IOTA was the only cryptocurrency which is currently Quantum Resistant by using Winternitz OTS+. That obviously isn’t true as we talked about Mochimo and QRL already, and it’s interesting that they are actually moving AWAY from post-quantum security as a core focus.
IOTA was completely and relaunched IOTA 1.5, also called Chrysalis, in April 2021. Beyond other updates, they stopped focusing on quantum proof cryptography.
The IOTA protocol used to use the Winternitz One-Time Signature (W-OTS) scheme as well. However, WOTS does have drawbacks and IOTA ran into some of these issues that exacerbated their security issues, leading to a pretty big wallet hack.
IOTA's cryptography only allowed to use an address once. Reusing an address can be a point of vulnerability. That means a transaction long in the past could be used to recover the private key, and then that private key could be used again today to move coins. Of course, right now that’s safe, but the idea is that a quantum computer could be used to recover the private key.
So this new Chrysalis release uses the Ed25519 signature scheme, which is Edwards-curve Digital Signature Algorithm (EdDSA). It does give a lot of positives to the IOTA tech, because it’s faster, and reduces the transaction size.
It is, however, not quantum safe. Ed25519 is very vulnerable to quantum computers, in that quantum computers are exponentially faster at solving this, and even require less qubits than RSA to break. However, IOTA believes that they can adopt new signature schemes quickly and are waiting for the recommendations for that, and upgrade once that viable scheme is found.
So here, the point is, IOTA used to use quantum secure cryptography, but recently updated and is no longer using it.
There’s other cryptocurrencies that are starting to get into the research side of the effects of the post quantum computing world. Cardano for example, did research a few years ago jointly with a think-tank to start exploring what it would mean for cryptocurrencies
They have also continued publishing work on quantum security in the last few years, so they are definitely keeping an eye on the space, but they are not currently implementing quantum resistance into the cryptocurrency.
One of the latest papers were on the WOTS+ (WOTS plus) algorithm too, so it’s really becoming something that’s gaining popularity in the crypto space.
So in general, a lot of these cryptocurrencies are legitimately using some sort of signature schemes that as far as we know, for now, are safe against quantum computers. Luckily, these quantum resistant crypto currencies. However, that’s not a guarantee of the future that these will stay safe forever.
In late 2016, NIST ran a competition for Post-Quantum Cryptography Standardization to find a suitable quantum-resistant public-key encryption algorithms.And recently, they have chosen 26 candidate algorithms, published in first round status report.
The 26 algorithms had very different approaches, but mostly lay in 3 families: lattice based, error correcting code based, and multivariate based cryptosystems. Lattice based systems have a large body of work behind them, starting back in 1996, and are considered one of the strongest candidates for post-quantum cryptographic standards.
They’re continuing to narrow down the encryption standards, and likely will end up picking more than one algorithm. In 2020 and 2021, NIST will continue to review and test these post-quantum encryption standards, with the aim to have drafts of the recommended standards ready sometime between 2022–2024.
Are you worried about quantum computers and are you getting out of bitcoin and other vulnerable coins?
In my opinion, quantum computers are a legitimate threat over the long term, though scientists disagree on the amount of time we have until we can crack ECC and RSA encryption.
However, cryptocurrencies can be updated pretty quickly, compared to some older systems, but there are some consequences. Check out my YouTube channel for a video on a deep dive on bitcoin's vulnerabilities to quantum computers. Some of the larger cryptocurrencies are aware and thinking about the threat, and many are starting to work on post-quantum security.