How do hash-based post-quantum digital signatures work? (Part 1)

One class of post-quantum digital signatures is hash-based digital signature schemes. Unlike the current digital signature schemes used to validate blockchain transactions, hash functions provide much less structures for quantum computers to exploit, and are widely believed to be quantum-safe. The goal of this article is to provide an up-to-date overview of hash-based digital signatures and explain how they work in detail.

Digital signatures widely used on current blockchain infrastructures, such as BLS and ECDSA, are based on the discrete logarithm problem.

For those who are not familiar with digital signatures, there are four parts of a signature scheme: System Generation (SysGen), Key Generation (KeyGen), Signature Generation (Sign), and Signature Verification (Verify).

For example, in ECDSA public key is generated on an elliptic curve group of generator , with private key satisfying . Given , it is difficult to find using classical algorithms.

The BLS signature scheme is constructed on a pairing group . The public/secret key pair satisfies .

Because quantum algorithms being good at finding periodicity of some functions, it uncovers special structures of classically hard problems like factorization and discrete logarithm. When quantum computers with thousands of logical qubits are available, BLS, ECDSA, and other signature schemes relying on factorization and discrete logarithm problems will not be secure.

For example, finding prime factors of a number can be reduced to finding period of a function , where is a coprime of . Once a period is found, then the two prime factors can be found by calculating and . The greatest common divisor can be found quickly with the famous Euclidean Algorithm, it runs on a classical computer. On the other hand, finding the period of is hard on classical computers, but a QPU can do it within polynomial time.

Although current-day quantum computers only have a few hundred noisy physical qubits, quantum computer builders do have intensive roadmaps to achieve large-scale quantum computers. Superconducting quantum computer manufacturers like IBM and Rigetti Computing are moving towards 1000-physical-qubit quantum computers, and use tileable modules to obtain larger number of logical qubits. Beyond that, there are several other methods that could lead to meaningful quantum computing systems in the foreseeable future, including Ion Trap, Neutral Atoms, and Measurement Based Quantum Computing.

On the other hand, there is so far no efficient quantum algorithm found to break a hash function, and quantum computers only speeds up birthday attack to compared to on classical computers.

Now let’s look at how hash functions are used to construct digital signatures and go through hash-based quantum-safe signatures.

One-Time Signature Schemes

The first hash-based signature was Lamport Signature first introduced in 1979. It is a one-time signature scheme (OTS) because one Lamport signature key can only securely sign one message. The signature scheme works as follows:

For each message, the signer needs to prepare for two sets of key pairs. and .

are calculated by hashing . Assuming we are using a 256-bit cryptographic hash function to produce digests of messages, each set of key pairs consists of 256 secret keys and public keys. In total, we will need to prepare for 512 secret keys and 512 public keys to sign any single message.

To sign a message, first hash the message into a 256-bit random number; Then, based on the bit value of the hashed number, choose SK accordingly.

Note that we will always sign a digest of a message (where is a cryptographic hash function) instead of signing a message of arbitrary length. To make notations simple, we will only use instead of in the rest of the article. When you see , you know that it actually means .

To verify the signature, first compute , then compute from the signature, verifies that are indeed results hashed from , and the indexes are correct.

The process exposes half of the secret keys after signing any message. So key pairs can only be used once, otherwise an attacker will be able to use the exposed secret keys to validate messages.

Manage OTS Keys with Merkle Trees

From a 21th century crypto user’s standpoint, the Lamport signature scheme might at first look strange and messy. Writing down private key or mnemonic phrase once can be already stressful and annoying, isn’t it driving people crazy if that key can only sign one message, and a different public key has to be shared for every message?

It turns out that the OTS (introduced later) signature schemes can be not that bad, if we can properly introduce mechanisms and tools to manage the keys.

Because Lamport OTS and Winternitz OTS can only sign one message at a time, if multiple messages need to be signed, there must be many keys. The Merkle Tree Signature Scheme (commonly called “MSS”) was invented by Ralph Merkle to manage Lamport OTS keys.

The basic idea is to use Merkle tree leaves to store Lamport OTS keys. Because Merkle tress are binary trees, a Merkle tree of height has leaves. If leaves are used to manage digests of Lamport OTS keys, a Merkle tree can manage Lamport OTS key pairs.

When signing a message, one Lamport key pair needs to be picked up from the tree that has not been used before. The signature consists of the index of the leaf, the Lamport public key, the digest of the Lamport public key (the leaf), and the authentication path of that leaf.

If many messages need to be signed, the above process can be repeated. As a Lamport key pair is a one-time key pair, no leaf can be selected more than once. Therefore, MSS is a stateful signature scheme.

You might also have noticed that the Lamport signature scheme itself does not prevent middle-man attack, if the verifier is given a Lamport signature only.

In order to verify the signer’s Lamport public keys are authentic without Merkle tree, the verifier needs to keep a copy of the keys. Because all the individual key pairs are one-time use only, the verifier then needs to keep a copy of all public keys. Using a Merkle tree effectively allows the verifier to only save the Merkle root instead of saving key pairs, reducing space from to . It means that securely exchanging a single Merkle root allows many signature verifications.

As a result of using Merkle tree, signature must include auth path each time - a bit more space, and the verifier computes more hashes for verifying each signature.

Winternitz OTS

Another problem with Lamport OTS is that the Lamport public keys and Lamport signatures are too long. Robert Winternitz provided an improved signature scheme (now called WOTS) that significantly reduced the size of signature.

Instead of preparing private and public key pairs for every bit of a message, Winternitz OTS divides a hashed message into chunks. If a message is divided into N chunks, and each chunk has l bits, we have . We will use the same $l,N& notations across this article to make it easier to read.

Suppose that we still use a 256-bit hash function on the message, and get a 256-bit digest of the message. In this case, (for example, , , or , , etc.)

Use the above example, is splitted into 64 chunks and each chunk has 4 bits. So, WOTS only needs to prepare for 64 private keys . Public keys are computed by applying a hash function on each private key for times.

A WOTS signature is generated as follows.

1. Compute the decimal values of each chunk from the message digest. For example, the decimal value of the first chunk is 5.
2. Compute signature of th chunk by hashing the corresponding private key times.In the above example, will be hashed times.
3. Apply (1) and (2) on chunks and produce signature .

To verify the signature, a verifier will first hash the message and get a 256-bit digest . The verifier then divides into chunks, obtaining decimal values of each group.

The verifier then hashes each value the signature times, getting . If is identical to the public key set , signature is valid, otherwise the signature is rejected.

The tradeoff of WOTS is to add more computation in signature generation and verification. As a result, WOTS signatures will be significantly smaller than Lamport signatures (by a factor of about 4 to 8 according to Merkle).

Notably, WOTS is still a one-time signature scheme, because once a key pair is used, an attacker can produce a valid message for each chunk as long as the decimal value of a chunk is smaller than the original value. Therefore, it is not going to be secure at all to use WOTS more than once.

WOTS+

WOTS+ adds randomization to WOTS. It first adds an additional public key to the set of public keys . The new is a set of random numbers .

is a hash function used by WOTS+ that replaces used in WOTS. takes two inputs and is recursively defined as:

where is the private keys and is a hash function.

The WOTS+ signature is generated in a similar way to WOTS, with some modifications. It first divides a message into pieces , then computes a checksum , concatenate the checksum, producing .

Compute the signature:

Send the signature together with the random number to the verifier.

A signature can be verified by continuing hashing the elements from the received until each of the entire set of is verified by .

Specifically, compute

If elements match , the signature is valid, otherwise reject the signature.

Although WOTS and some variants of WOTS use simple hash chains, their iteration methods are common and simple. However, WOTS+ has some special mode of iteration, which enables the tight security proof without requiring the used hash function family to be collision resistant.

The eXtended Merkle Tree Signature Scheme

Because WOTS+ is still a one-time signature scheme, key management is important if there are multiple messages to sign.

The Extended Merkle Tree Signature Scheme (commonly called XMSS) uses Merkle tree to manage WOTS+ keys in a similar way that MSS uses a Merkle tree to manage Lamport keys.

Because we already know how MSS works with Lamport key pairs, let's look at the top-level Merkle tree first.

In XMSS, the public key is the XMSS Merkle root. Every leaf of the Merkle tree is a Merkle root of a WOTS+ public key set. To illustrate this, "expand" from above we will have a "sub" Merkle tree attached to leaf above. This tree is also called "L-tree" in literatures.

Bitmasks are used in L-trees. Before applying the hash function to two nodes each time, two bottom values will XOR with their corresponding bitmasks. Each level of the L-tree has two bitmask values and , they will be used to XOR left and right nodes on that level. Therefore, a L-tree of height will need bitmasks in total.

Now moving down the L-tree - the leaves of a L-tree are WOTS+ public keys. Every leaf represents one WOTS+ public key, which is created using a chain of hash values from a private key as described in WOTS+.

To sign a message , first choose a leaf indexed by from the XMSS tree and make sure the leaf has never been used before. Then we know that the leaf is a Merkle root of a WOTS+ public keys set. The WOTS+ private keys can be used to sign the message, and get a WOTS+ signature of message . The XMSS signature where is the index of the WOTS+ key pairs and is the Merkle root of this WOTS+ public keys set.

To verify the signature, first verify the using and the WOTS+ public keys indexed by , then verify the correctness of with and the XMSS public key.

With XMSS, multiple WOTS+ keys can be managed and validated.

Further Reading

The signature schemes introduced in this article are basic building blocks of hash-based signature schemes. More in-depth analysis of algorithmic properties of hash-based signature schemes can be found in this paper by Andreas Hülsing et al.

There are other previously NIST recommended signature schemes (e.g. the Leighton-Micali Signature) and multi-tree variance such as Hierarchical Signature System (HSS) and the multi-tree XMSS (XMSS-MT). These signature schemes and the ones introduced in the first part of this article are not currently recommended by the NIST's recent Third Round of Post-Quantum Cryptography Standardization Process. However, it is important to understand the details of these signature schemes, because newer, and often more complicated signature schemes are designed based on the ideas of these algorithms.

The second part of this article will introduce more recent developments of hash-based signature schemes, including SPHINCS/SPHINCS+, as well as the status of engineering and open source libraries.