XMSS: hash-based stateful digital signature

01 Jul

Introduction

XMSS (eXtended Merkle Signature Scheme) represents a fundamental component of the SPHINCS+’s construction, which is a post-quantum hash-based digital signature selected in the NIST standardization process.

As a standalone solution, XMSS is itself a cryptographic scheme suitable for specific applicative scenarios. Moreover, it has been standardized by NIST, together with the similar LMS, in the context of stateful digital signatures. Even if XMSS shows many nice features [1] compliant also with the post-quantum process, the stateful property makes it not so attractive from a practical point of view. Indeed, to preserve the overall security, the scheme needs to keep track of all signatures produced with the same private key.

This limitation is overcome by its embedding in SPHINCS+.

XMSS

In the XMSS’s construction, the role played by particular binary trees, named Merkle trees, is crucial. Given a certain hash function $\text{H}$ , each Merkle tree node is obtained by computing the hash value of the two nodes (the children) at the lower level [2]. Therefore, the Merkle tree is completely determined by its childless nodes called leaves. In the here considered case, the leaves are all and only the lowest-level nodes. Lastly, the node on the top of the tree is referred to as the root.

In the following, an eight-leaf Merkle tree.

In XMSS, the private key a is a bit string (seed) used to generate a couple of WOTS+ keys $(ws_i, wp_i)$ for each leaf of Merkle tree. More precisely, each leaf is set as a public key $wp_i$ and the resulting root $r$ represents the XMSS public key.

The XMSS signature of a message $M$ consists of its WOTS+ signature, using a properly chosen [3] $ws_i$ , and the authentication path, i.e., the set of necessary and sufficient nodes to compute the root of the tree starting from $i$ -th leaf.

In the verification phase, the receiver gets a candidate $wp_i$ starting from the received WOTS+ signature. Then, the authenticity of $wp_i$ is ensured thanks to the authentication path, included in the overall signature, and the root, public key of the scheme. More precisely, $wp_i$ and the authentication path allow the receiver to compute a candidate Merkle tree root and check if it coincides with the already known one.

HyperTrees

The use of Merkle trees allows to consider a public key of small size, given that it can be identified with just the root of the tree.

Using Merkle trees to generate and verify signatures has some drawbacks, especially if one has to satisfy the requirements imposed by NIST concerning the number of signing operations that is possible to realize with a single private key. In order to satisfy such requirements one should build a tree with an extremely high number of leaves (around $2^{64}$ ), thus rendering impossible the efficient construction and transmission of an authentication path inside the digital signature.

In order to overcome these shortcomings, it may be useful to introduce a new mathematical object called HyperTree, which is a Merkle tree where the leaves, corresponding to WOTS+ public keys, are used (with the respective private key) to sign and validate the roots of other trees on a lower layer. It is hence defined as a hierarchy formed by different layers of Merkle trees: each leaf of an intermediate tree signs the root of a tree at the lower layer, while the leaves of the lowest layer trees are used to sign messages.

What follows is a representation of an HyperTree formed by three layers of trees [4], where it is possible to notice how a layer and the one below it are linked by a WOTS+ signature.

Resorting to a HyperTree thus makes it possible to obtain a structure with a high number of leaves (as per the NIST requirements), without requiring to manage a unique Merkle tree of size such that it could hinder the usability of the digital signature algorithm. The introduction of intermediate layers of trees allows to avoid having to explore all the branches of the resulting construction in order to produce a valid authentication path.

In the case of a scheme that makes use of a HyperTree, the digital signature is composed by the WOTS+ signatures connecting the different layers of trees, together with the authentication path formed by the nodes needed to recompute the roots of all Merkle trees up to the one at the highest layer (filled in black in the previous image). The root of the highest layer tree of the HyperTree represents the public key of the scheme.

In the last few years two new algorithms, called XMSS^MT and HSS, have been proposed: these schemes are the result of the application of HyperTrees to the already described XMSS and LMS. Using HyperTrees is not enough, though, to overcome the main issue that affects XMSS and LMS, which is the need of maintaining a state in order to prevent signing twice with the same private key, which could have catastrophic consequences on the security of the scheme. It then becomes essential to choose digital signature algorithms that allow to sign a limited number (greater than one) of different messages with the same key without reducing security. These algorithms are called Few Time Signatures (FTS): in the next article of this blog post series a FTS will be described and focus will be put on how that can be integrated together with WOTS+ and the HyperTrees in order to obtain the fundamental core of SPHINCS+.

[1] Efficiency, parameters size and implementation simplicity.
[2] Notice that the level numbering is reversed with respect to the top-down one on standard binary trees.
[3] The unique requirement is that the key has not been used already to sign other messages.
[4] Image from “National Institute of Standards e Technology (NIST). FIPS 205 (Draft) – Stateless Hash-Based Digital Signature Standard. 2023.”

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at the end of 2020 focusing in particular on issues related to quantum technologies.

Marco Rinaudo, a bachelor’s degree in Mathematics from the University of Turin and a master’s degree with a specialization in Cryptography from the University of Trento. Following a 2022 curricular internship at Telsy, he has been part of the Cryptography Research Group since January 2023.