Quantum Resistant Crypto favors Winternitz Signature Scheme
While classical computers store information in the form of bits (a 1 or 0), a quantum computer can store information in any superposition of 1 or 0 or both simultaneously. As a result, quantum computers can now solve important problems once thought intractable.
However, the prospect of quantum computing being used for nefarious purposes is also likely. This is particularly true for cryptocurrencies that rely on encryption as a means to thwart bad actors. Fortunately, several cryptocurrencies are seeking to become quantum-resistant.
At present, two cryptocurrencies (IOTA and QRL) rely on Winternitz signature schemes to achieve quantum resistance. Both coins implement the Winternitz scheme differently.
Loosely based on the Lamport Signature, the Winternitz signature scheme is simply a one-time signature (OTS) scheme. That is, it’s typically founded on general one-way functions (e.g., SHA-256), and for security purposes requests that users limit each transaction to one secret/public key pair. And since it relies on relatively small key and signatures sizes, it can sign several bits at once.
A good video explanation of this signature scheme can be found here. Listed below are two projects that rely on the Winternitz signature scheme.
IOTA is arguably the best-known quantum-resistant cryptocurrency. Conceptualized as a Tangle, the cryptocurrency is similar to a Directed Acyclic Graph (DAG). Instead of a traditional blockchain, each block can reference more than one parent.
By implementing this configuration, IOTA has consistently marketed itself as “quantum-proof” rather than merely quantum-resistant. However, it’s not the DAG that has served to underscore this claim but its signature scheme.
Instead of elliptic curve cryptography (ECC), IOTA relies on the Winternitz One-Time Signature Scheme. Although quantum-resistant, Winternitz signatures can easily reveal part of the private key. Hence, users are encouraged to only use a sending address once.
Users who fail to do so may enable a bad actor to sign a second transaction with the used address fairly easily.
Fortunately, IOTA also employs open source python code to check if a signature has already been used within the IOTA Tangle
Bending Backwards for Winternitz
Winternitz signature schemes tend to be both very large (up to 3900 bytes) and very slow (as the underlying hash system must be executed hundreds of times). These disadvantages will certainly slow adoption by other cryptocurrencies.
Moreover, IOTA made Winternitz reliant on a cryptographic hash function named Curl-P-27I (later deemed vulnerable to signature forgery).
IOTA resolved this issue by employing ternary hardware (as opposed to traditional binary hardware). Thus, its data structures use trits (-1,0,1) instead of bits (0,1) and trytes (three trits) instead of bytes (eight bits).
When Curl-P-27 proved untenable, IOTA selected a hashing function named Kerl (based on Keccak) that could be converted to ternary.
The costs associated with quantum resistance have IOTA reviewing whether to implement an Edwards-curve Digital Signature Algorithm (EdDSA). The EdDSA operates over twisted Edwards curves and is a variant of the Schnorr signature scheme.
Unfortunately, this would also make IOTA more vulnerable to quantum attacks.
The Nonce Advantage
While IOTA’s Winternitz signatures can claim to be quantum-resistant, that cannot be said for DAGs in general.
When DAGs were first introduced, they were thought to be quantum-resistant, Today, DAGs can be fully “crypto-analyzed by solving a system of bilinear polynomial equations” (see “ Practical Algebraic Attack on DAGs “)
Fortunately, IOTA’s Tangle is not strictly a DAG. Unlike DAGS,
“Each (IOTA) transaction must have a nonce proving Proof-of-Work (PoW) and include pointers to two other transactions. In order to add transactions to the tangle, a user selects two tip transactions from the tangle to reference in her transaction. Once created and signed, the user performs sufficient Proof-of-Work and broadcasts the transaction to the IOTA network (see “ Cryptanalysis of Curl-P and Other Attacks on the IOTA Cryptocurrency “).
It’s these nonces that ultimately help Tangle achieve some semblance of quantum resistance. How? An article by Sergei Popov (“ The Tangle “) provides the reasoning.
Let’s say an attacker decides to use all of their computing power to conduct a large double-spending transaction. Since this transaction is very large, the Tangle might “approve transactions prior to the legitimate transaction used to pay the merchant” (p.15).
In essence, the attacker is seeking to have their “dishonest subtangle outpace the honest subtangle. If this happens, the main tangle continues growing from the double-spending transaction, and the legitimate branch with the original payment to the merchant is orphaned” (p.16).
While such an attack appears custom-made for a quantum computer, it can be prevented if the weight of such a transaction is capped. As Popov notes, IOTA does not need to check very many nonces to find a suitable hash.
Because it can do so relatively quickly, this mitigates any advantages that a quantum computer might have in terms of efficiency/speed. Especially when compared to Bitcoin.
Update: Move to EdDSA
IOTA recently announced it’s implementing a more standard signature scheme (an EdDSA signature scheme named ed25519). While the new signature scheme is expected to reduce transaction volume and increase blockchain usability, IOTA can no longer claim to be quantum-resistant.
Quantum Resistant Ledger ( QRL) appears to be quickly gaining notice among the quantum-aware. The cryptocurrency recently had its XMSS (eXtended Merkle Signature Scheme) standardized and approved by the National Institute of Science and Technology (NIST).
It’s fairly easy to grasp XMSS, as it relies on Winternitz OTS+ as its main building block. Unlike IOTA, XMSS does not rely on the user to remember whether they have re-used a one-time signature. Instead, the QRL web wallet reviews past transactions and “uses the number of sent transactions to calculate the current XMSS tree index.”
As a stateful hash-based signature scheme, XMSS requires constantly updating the secret key (unlike conventional digital signature schemes). Fortunately, the blockchain is stateful as well.
Users can securely reuse addresses, up to a certain point. Out of the box on, users can also select a huge tree-height, (²¹⁸ signatures), which allows them to conduct 262k possible outgoing transactions. Although this is quite a large number, QRL allows the user to extend this capability as well.)As QRL documentation explains, this reasoning goes to the heart of XMSS:
In general, since an OTS Key Index is limited, users are cautioned not to use them all up else their funds will be lost. Fortunately, when the Winternitz OTS Signature Scheme is combined with a Merkle tree authentication scheme, users possess the capacity to create more OTS.
EnQLAVE and Future Directions
The QRL team is currently working on a project called EnQlave. An Ethereum web wallet, EnQlave secures a user’s ERC20 tokens against a quantum computer attack. In essence, it operates as a long-term storage vault.
The technology rests on creating a unique quantum-safe address via a smart contract. Aside from using a standard Ethereum ECDSA signature, EnQlave relies on QRL’s XMSS signature as well.
QRL has partnered with Insight Researchers in an attempt to stay ahead of quantum computing advances in the blockchain space. The latter will facilitate “QRL’s Proof-of-Stake network with research into lattice cryptography and signature aggregation.”
Accordingly, QRL will seek to reduce its overall block size as a means to improve its scalability.
As stated above, cryptocurrencies relying on the Winternitz Signature scheme must track all the private keys signed (and remain cognizant of the limit on signatures as well).
QRL is currently working hard to implement a stateless signature scheme with reusable addresses. This solution, known as Falcon, depends on finding a cryptographic signature algorithm that can resolve the short integer solution problem (SIS) over NTRU lattices.
Resolving an SIS problem requires resolving a random set of linear equations. Since the solution set is likely to involve a myriad number of integer solutions, its best of the solution uses only small numbers (thus, the sum of their square should be small). Although quantum computers have sought to resolve this Falcon problem, they have yet to do so.
Although the Winternitz Signature scheme limits users to one-time addresses, it remains robust against quantum computing. While a quantum-proof signature scheme is not expected to be broken anytime soon, there is no guarantee that it may eventually become obsolete as well.
Indeed, two other cryptocurrencies have devised non-algorithmic methods for achieving quantum resistance (XTRABYTES and ILCOIN). Those two coins will be the subject of my next article.
