Improving the SPHINCS post-quantum signature scheme, part 1

Guillaume Endignoux completed his master’s thesis in our research team, working on hash-based post-quantum signatures. Among his contributions, he investigated the subset-resilience problem, a computational problem behind the HORS few-time signature scheme, itself a component of the SPHINCS many-time signature scheme. Findings include:

• Adaptive attacks dramatically reducing HORS’ security, using a greedy algorithm
• Improved classical attack on SPHINCS, with complexity instead of
• A new construction, called PORS, more secure than HORS, reducing the SPHINCS signature size of more than 4 KiB

Our research paper Clarifying the subset-resilience problem details Guillaume’s findings. Below I’ll provide a non-technical summary, starting with HORS (see our previous article for a visual introduction to HORS).

How HORS works

In HORS, a private key is a list of secret values and the public key is the list where is a one-way function. To sign a message with HORS, you just compute a set of indices , and reveal the secret values . Here is a kind of hash function returning indices.

Obviously, with such a scheme you can only sign so many messages until all ‘s are revealed.

Adaptive attack on HORS

To attack HORS, an attacker just needs to find a message such that the indices have already been used in previous messages. In the non-adaptive case, an attacker would passively collect a large number of signatures and then brute force for a message whose have all been previously revealed. We can do much better in the adaptive case.

If the attack is adaptive, an attacker can first seek a set of messages such that

1. The first messages maximize the number of distinct indices revealed
2. The indices of the -th message are all included in the indices of the first messages

This is the idea behind the greedy algorithm in Section 4.1 of the paper. Once such messages are found, just query the signing oracle for the signatures of the first messages in order to forge a signature for the $q+1$-th message.

But we can do even better. In the HORS paper (and in SPHINCS), the function doesn’t guarantee that all indices will be distinct. So, you may end up with fewer than distinct indices, which means that you’ll need to collect fewer secret values in order to forge a signature. Such messages are called weak messages in Section 4 of the paper, which details the impact on HORS’ security.

From HORS to PORS

“HORS” stands for hash-to-obtain-a-random-subset; we propose PORS, PRNG-to-obtain-a-random-subset, which uses a PRNG to generate a list of distinct indices. This guarantees that weak messages won’t exist. Section 6 of the paper details how PORS works.

We apply SPHINCS with two extra tweaks:

1. PORS becomes PORST, or tree-PORS, using the same trick as HORST in SPHINCS: the public key is compressed from values to a single value, computed as the root of the binary tree with $t$ leaves.
2. PORST is used not only to generated the signature indices, but also the leaf index, or the reference of the PORST key pair to be used. Indeed, in SPHINCS a PORST instance corresponds to a leaf in a hyper tree (a tree of trees).

As explained in Section 6.4, SPHINCS then becomes more secure for a given parameter size. This allows for shorter signatures to guarantee a 128-bit post-quantum security level. “SPHINCS-PORST” signatures are then 36,384-byte instead of 41,000-byte.