Author: David Wong
Source: https://cryptologie.net/posts/hash-based-signatures-part-iv-xmss-and-sphincs/
The original article was published in December 2015.
This article is the final chapter in this series of blog posts about hash function-based signature schemes. You can find the first article in this series ( Chinese translation ) here.
Now, we're getting to the interesting part—the actual signature scheme.
PQCrypto released a preliminary proposal over a month ago. The two proposed post-quantum algorithms are " XMSS " and " SPHINCS ":
This article will first introduce XMSS, a stateful signature scheme; then SPHINCS, the first stateless signature scheme!
XMSS
The “ eXtended Merkle Signature Scheme (XMSS)” emerged in 2011 and then became a draft of the IETF (Internet Engineering Task Force) in 2015 .
Its main structure resembles a Merkle tree, with only minor differences. In an XMSS tree, child nodes are XORed with a mask before being hashed to their parent nodes. Each node has a unique mask.
The second unique aspect is that the leaves of an XMSS tree are not hashes of one-time public keys, but rather the root values of another type of tree—called an "L-tree".
L-trees also apply a mask to the hash values of nodes; the mask for an L-tree is different from that of the main XMSS tree, but it is universal across all L-trees.
The leaves of an L-tree store an element with a WOTS+ public key (this scheme is explained in the first article of this series ( Chinese translation )).
If you're like me and wondering why a WOTS+ public key needs to be stored on a tree, here's Huelsing's explanation:
The purpose of the tree structure is not to store a WOTS public key, but to hash it, and this method allows us to prove that a hash function with "second preimage resistance" is sufficient (a hash function with collision resistance is not required).
In addition, the master public key consists of the root node of the XMSS tree and the bitmask used in the XMSS tree and L-tree.
SPHINCS
“SPHINCS” is a newer approach that incorporates many advancements in the field, and more! It brings us the statelessness we’ve all been waiting for.
That's right, this means you no longer need to save any state. But before explaining how it does that, let's look at the construction of SPHINCS.
First, SPHINCS is composed of many trees.
Let's look at the first tree:
- Each node is the hash value of the result of XORing the concatenation of the preceding nodes with the bitmask of its corresponding level.
- The public key consists of the root hash value and the bitmask.
- The leaves of the tree are the compressed public keys of the WOTS+ L-tree.
Please think of the WOTS+ L-tree as the XMSS L-tree we explained earlier, except that its bitmask design looks more like a SPHINCS hash tree (that is, each level of the tree has a dedicated mask).
Each leaf contains a Winderitz one-time signature, allowing us to sign another tree. Therefore, according to the diagram above, the next layer will have 4 SPHINCS trees, each containing a WOTS+ public key in its leaves.
This process continues downwards... The number of stacks of trees and the number of leaves in each tree depend entirely on your initial parameters. Eventually, when you reach layer 0, the WOTS+ signature no longer signs other SPHINCS trees, but rather HORS trees.
HORS trees are structurally identical to L-trees, except they contain HORS few-time signatures instead of Winternitz one-time signatures. We use them to sign our messages, which improves the security of the scheme because as long as we always use the same HORS key when signing a message, nothing serious will happen.
The following diagram, from the SPHINCS paper, abstracts away the WOTS+ L-trees (displaying them as signatures of the next SPHINCS tree) and shows the unique path to a message:
When signing message M, we first create a "randomized" hash value and a "random" index number for M. I use double quotes because in the SPHINCS signature scheme, everything is deterministically calculated using a pseudo-random function. This parameter tells you which HORS tree to use to sign the randomized hash value of M. This is why you don't need to remember the state: because the index number is deterministically derived from the message. Signing the same message will always use the same HORS tree; while signing two different messages will have a high probability of using two different HORS trees.
This series has come to an end!
Addendum: Here is another illustration from the paper " Armed SPHINCS ", which I think is excellent!
(over)
