DI Management Home > Cryptography > SPHINCS+ > Few Time Signature (FTS)

Few Time Signature (FTS)

A Few Time Signature (FTS) scheme allows an issuer to sign a "few" messages using a OTS construction with the same key.

We consider two schemes: HORS and FORS.

Few Time Signature (FTS) Procedure

As a first approximation, if the OTS signature over a message of $b$ bits requires $k$ private key values, then we generate a larger number $t$ of private keys and pick parameters such that ${}^{t}C_{k} \ge 2^b$, where ${}^{t}C_{k}$ is the number of combinations of $t$ items taken $k$ at a time

Combination Formula ${}^{t}C_{k} = \frac{t!}{(t-k)!\,k!}$ where $n! \equiv 1 \cdot 2 \cdot 3 \cdots (n-2) \cdot (n-1) \cdot n$.

The procedure is


HORS (pronounced "whores") stands for "Hash to Obtain Random Subset" and was devised by the father and son team Reyzin and Reyzin [REYZ02].

Alternative HORS using a Merkle tree

Forest of Random Subsets (FORS)

This excellent diagram from [MAH21] demonstrates the difference between HORS and FORS signatures.


HORS and FORS signatures of the message 100 011 110 where $a = 3$ and $t = 8$. The 8 rectangles under each tree depict the eight secret keys whose hashes are stored in the corresponding leaf nodes.

<< previous: Basic Merkle Signature Scheme Contents next: SPHINCS+ Introduction >>

Contact us

To comment on this page or to contact us, please send us a message.

This page first published 17 March 2023. Last updated 17 March 2023.