By Victoria de Quehen, Security Researcher, ISARA Corporation
Published February 24, 2020
Digital signature algorithms are a critical component of public-key infrastructure, with applications ranging from code signing to establishing secure connections. However, classical digital signature algorithms will be vulnerable to quantum-enabled attacks. Hash-based cryptography is among the oldest area of quantum-safe cryptography, with digital signature algorithms dating back to 1979, before the invention of elliptic curve cryptography.
In the late 1970’s, Leslie Lamport introduced the idea of a One-Time Signature (OTS)—a signature algorithm that could be used at most once. Although it may not seem practical to use a signature scheme that can only be used at most once, shortly after Lamport’s influential publication, Ralph Merkle turned this seemingly impractical idea into a signature algorithm that could be used many times, and in doing so, gave birth to the first many-time hash-based algorithm.
Hash-based signatures fall into two distinct types: stateful and stateless.
All many-time hash-based signature algorithms work by efficiently combining many instances of OTSs. However, with stateful hash-based signature algorithms, it is vital to not accidentally sign multiple messages with the same OTS signing key. After each signature the state is updated, and this essentially keeps track of which OTS keys have been used. Managing state can be difficult with severe consequences if implemented incorrectly. It is important to make correct architectural decisions (for example, for disaster recovery) to safely manage state if there are multiple pieces of hardware or equipment that have to work together. For this reason, we recommend working with companies with expertise in stateful hash-based cryptography.
There are also stateless hash-based signatures, that do not require managing a state, and are far easier to implement. Unfortunately, stateless signatures are far less efficient: the signatures are much larger and they are computationally more intensive. As well, stateless signatures are still 2-4 years away from standardization. On the other hand, stateful hash-based algorithms are expected to be standardized within a year, and with real-world expertise they can be implemented safely.
Hash-based cryptography was first developed by Leslie Lamport and Ralph Merkle in the late 1970s. Since Merkle’s original scheme , hash-based algorithms have become much more efficient. The leading contenders for post-quantum hash-based signatures are the stateful algorithms Multi-Tree eXtended Merkle Signature Scheme (XMSSMT)  and Hierarchical Signature System (HSS) , and the stateless algorithm SPHINCS+ .
A major advantage of hash-based signatures is a high degree of confidence in their mathematical security. Unlike other quantum-safe cryptographic algorithms which are 2-4 years away from being standardized, the stateful hash-based signature schemes XMSSMT and HSS have been studied and approved by the Crypto Forum Research Group (CFRG) and published as RFC 8391 and RFC 8554 , respectively.
Although CFRG RFC’s are not technically considered to be standards, the National Institute of Standards and Technology (NIST) has recently published a draft Special Publication (NIST SP 800-208 ) which, when finalized, will serve as a national standard for XMSSMT and HSS. As is common with NIST standards, this special publication will likely become a de facto international standard as well.
Hash-based cryptography creates signature algorithms whose security is mathematically based on the security of a selected cryptographic hash function.
Consider, for example, NIST’s set of well-trusted and ubiquitous cryptographic hash functions Secure Hash Algorithm 2 (SHA-2). SHA-2 is considered to be secure against attacks by adversaries having access to today’s most powerful supercomputers, and it is believed to be quantum-safe as well. This means a hash-based signature algorithm that uses SHA-2 is essentially as secure as SHA-2, which is to say, extremely secure.
Moreover, even in the unlikely event that SHA-2 is compromised, the security of hash-based signatures could be restored simply by switching to another uncompromised hash function. Systems like these hash-based signatures, where switching between algorithms has a low cost, are referred to as crypto-agile.
Use cases that require immediate action could in many cases benefit from a hash-based solution. For example, many long-lived connected devices, especially ones that operate in hard-to-reach locations, such as satellites, will need security well after large-scale quantum computers are likely to exist.
For this reason, these devices could benefit from an approved hash-based digital signature algorithm. Such algorithms can be integrated now, to avoid financially prohibitive or logistically impossible upgrades in the future.
ISARA has implemented the leading candidates, HSS, XMSS, XMSSMT and SPHINCS+, as part of our ISARA Radiate Quantum-safe Toolkit. By using our ISARA Catalyst OpenSSL Connector, you can create and sign digital certificates with these quantum-safe signature algorithms.
ISARA is also able to provide solutions and expertise for managing state, and specialized strategies for managing trees, which yield resource trade-off optimizations for given hardware requirements.
As mentioned before, the first construction, developed by Lamport, has the disadvantage that it is only a one-time signature scheme. As we will see, Merkle overcame this limitation and constructed a many-time signature algorithm by using binary trees and cryptographic hash functions.
A One-Time Signature (OTS) scheme is a set of three algorithms: one for generating one-time key pairs, one for computing one-time signatures, and one for signature verification. An instance of an OTS scheme has a specific key-pair (P, S), where P is the public key and S is the private (signing) key.
Both the OTS schemes and the Merkle trees (described below) use hash functions. An important question to ask is if the same hash function can be securely used for both types of constructions. And indeed, by including just a little extra data in each hash (this is called domain separation) we can essentially treat a single hash function as many distinct hash functions. In other words, if we use SHA-256 to generate the OTS instances, we can still securely use SHA-256 to construct the Merkle trees.
Many-time, or full, hash-based signature schemes use hash trees to efficiently combine many instances of an OTS scheme.
We will now discuss how Merkle used binary trees—like the one shown in Figure 1—to combine many OTSs to create the public key of a many-time hash-based signature scheme. While the initial step of constructing the tree from these OTSs (which can be done offline) is usually slow in comparison to many other quantum-resistant constructions, signing is fast.
In a (perfect) binary tree all the nodes (except for the top node) come in pairs with a single node above them, and the distance from the bottom most nodes to the top-most is always the same. The node directly above another is its parent node, a node directly below a parent is its child node, and a pair of child nodes with the same parent are called sibling nodes. For example, in Figures 2 and 3, N1,0 and N1,1 are sibling nodes. They are also the child nodes of N2,0 ; that is, N2,0 is their parent node.
The top-most node is called the root node. The nodes on the bottom of the tree, which have no child nodes, are called leaf nodes. The leaf nodes are denoted L0 , . . . . , L7 in Figure 2.
The level of a node is its distance from the bottom. By this we mean the leaf nodes have level 0, and the nodes Nj,i in Figure 2 have level j. The level of the root node, normally denoted h, is called the height of the tree. For example, the tree in Figure 2 has height 3. Merkle used binary trees to combine OTSs, More specifically: each leaf nodes comes from the public key of a (distinct) OTS instance, and every other node in the tree is calculated from its two child nodes. We will now describe how these nodes are calculated using a cryptographic hash function.
Roughly speaking, a cryptographic hash function is a function that maps an arbitrary amount of data to a reasonably small, usually fixed length, output in a way where it is practically impossible to find an input that maps to a specific output (or two inputs that give the same output).
Intuitively, we can think of a Merkle tree as using hash functions to compress an ordered set of values into a single value, in a way where it is still easy to prove a value belongs to the original set. More concretely, a Merkle tree can be constructed from an ordered set P0 , . . . . , Pm of public keys of OTSs and a hash function H in the following way:
N1,0 = H(L0 || L1) and N2,1= H(N1,0 || N1,1 );
where || denotes (bit-string) concatenation. (More generally, in Figure 3
N1,i= H(L2i || L2i+1) and Nj+1,i= H(Nj,2i || Nj,2i+1).)
The public key of the Merkle signature algorithm is the root node. In Figure 2, the root node (public key) is N3,0.
For a clearer picture of how to build a parent node, see Figure 3.
A hash tree is a generalization of a Merkle tree, where the Pican be arbitrary data instead of OTS public-keys, see Figure 2.
As you cannot find the inverse of a hash function, it is practically impossible to find the nodes lower in the tree from nodes higher in the tree. Hence, it is impossible to find out information about the OTS signing keys given any set of nodes in the tree, in particular, given the root node.
Notice that for any Pi that was used to create the Merkle tree, there is a unique path from the leaf node Li to the root node (public key). For example, in Figure 4 the path from L2 to the top is drawn in red. Given Pi, if you can construct a path of this form, then this proves with almost certainty that Pi was one of the values used to create the Merkle tree. This follows from the fact that it is computationally infeasible to find an input to H with a specific output, hence you cannot find nodes lower in the tree from nodes higher in the tree.
However, we actually use the sibling nodes of the leaf-to-root path nodes in order to check that the path was constructed legitimately. For this reason we introduce the notion of the authentication path of Pi, to be the ordered set of sibling nodes of the nodes in the path from Li to the root node. In Figure 4, the authentication path (in blue) of P2 is L3, N1,0, N2,1. Given Pi(the public key of an OTS), and an authentication path for Pi, we can verify (authenticate) that Picorresponds to a leaf node. That is, if Piwas actually used in the generation of the tree, then it should be simple to reconstruct the path from Pito the root node, given the authentication path.
Referring to Figure 4, we can prove that P2 was use to create the public key of the Merkle tree given only its authentication path (in blue) L3, N1,0 , N2,1 , by constructing a path from P2 to the root node (public key).
To do this we just check that the values
give a path where the last value H(N2,1 || H(N1,0 || H(L3 || H(P2)))) is the public key of the many-time signature algorithm (i.e., the root node). As P2was actually used to construct the Merkle tree, H(N2,1|| H(N1,0 || H(L3 || H(P2)))) = N3,0 by construction.
If the above calculation yields the public key, then we have proven P2 was one of the OTS keys originally used to create the hash tree (because finding an illegitimate authentication path would require solving the computationally intractable problem of finding inverse images of a hash function).
A generic construction for a many-time scheme is summarized below:
Secret Key Generation: Create m = 2hOTS public/secret key-pairs (Pi, Si). Intuitively, we can think of the secret key of the many-time scheme as the material needed to generate the OTS key-pairs.
Public Key Generation: Create the hash tree for P1 , . . . . , Pm as described above. The root node is the public key of the hash-based signature scheme.
Signatures: To sign a message, choose an index i that has never been used before. Sign the message with Si(the OTS signing key) to get the one-time signature _, and calculate the authentication path of Pi. The signature for the message is the one-time signature _, together with the authentication path of Pi.
Verification: To verify a signature on a message, we first run the onetime verification scheme using the message and _. Next, check that the authentication path of Pi gives a valid path from Pi to the public key of the hash-based signature (root node). If it does, accept the message and signature as authentic.
Time/Space Tradeoffs: As the tree can be regenerated from P1 , . . . . , Pm , storing the entire tree is not always necessary. The decision of how much of the tree to store and how to manage the tree, leads to various CPU/memory tradeoffs. Moreover, all the keys P1 , . . . . , Pmcan also be regenerated from a single short seed, further reducing the amount of long-term storage required.
Number of Signatures: If the tree has height h, then it can be used to sign up to 2h messages.
Stateful Signatures: As each OTS signing key can be used at most once, in a stateful hash based signature scheme it is important to keep track of which one-time key-pairs have been used.
 David Cooper, Daniel Apon, Quynh Dang, Michael Davidson, Morris Dworkin, and Carl Miller. Recommendation for stateful hash-based signature schemes. Technical report, National Institute of Standards and Technology, 2019.
 Andreas Hülsing et al. SPHINCS+. NIST Round 2 Submissions for Post-Quantum Cryptography Standardization, 2019.
 A Hülsing, D Butin, S Gazdag, J Rijneveld, and A Mohaisen. XMSS: eXtended Merkle Signature Scheme. Crypto Forum Research Group RFC. rfc-editor.org/info/rfc8391, 2018.
 David McGrew, Michael Curcio, and Scott Fluhrer. Leighton-Micali hash-based signatures. Crypto Forum Research Group RFC. rfceditor. org/info/rfc8554, 2019.
 Ralph Merkle. Secrecy, authentication, and public key systems. Ph. D. Thesis, Stanford University, 1979.
If you have further questions, set up a meeting with our team here.
Learn about the other five areas of math used in quantum-safe cryptography in our blog series, "Math Paths to Quantum-Safe Security":