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

• We generate $t$ private keys and (try to) use a different subset $k$ of them each time to sign each message.

• So, statistically, we can sign a "few" messages picking different subsets of $k$ keys out of the $t$ without compromising the security of the underlying OTS scheme.

• In practice, each time we make a signature the security is reduced, as an adversary can examine earlier signatures and search for hash input that has a particular pattern of output bits, or other weaknesses.

• Both the HORS and FORS schemes are defined in terms of integers $k$ and $t=2^a$ and can be used to sign a string of $ka$ bits.

• In both schemes we split the message digest into $k$ bitstrings of length $a$ each and interpret each $a$-bit substring as an integer written in binary. We use this integer as an index into the key structure.

• FORS is used in SPHINCS+ inside a much larger hypertree structure. To put in context, SPHINCS+ is designed to sign up to $2^{64}$ messages with one key, which is effectively limitless in practice.

HORS

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

• HORS is defined in terms of integers $k$ and $t=2^a$ and can be used to sign a string of $ka$ bits.

• A HORS private key consists of $t$ random $n$-bit values.

  SK = $(sk_0, sk_1, \ldots , sk_{t-1})$

• Compute the HORS public key using a one-way function $f: \{0,1\}^n \rightarrow \{0,1\}^n$

  PK = $(pk_0, pk_1, \ldots, pk_{t-1})$ where $pk_i = f(sk_i)$

• To create a signature, split the message digest into $k$ bitstrings of length $a$ each.

• Interpret each $a$-bit substring as an integer $m$ written in binary in the range $0 \le m \lt t$ giving a sequence of $k$ integers $(m_0, m_1, \ldots, m_{k-1})$

• Use each integer $m_i$ as an index to select the $m_i$-th key from the set of $t$.

• The signature is

  $S = (\sigma_0, \sigma_1, \ldots, \sigma_{k-1})$ where $\sigma_i = sk_{m_i}$

• A verifier checks that $f(sk_{m_i}) = pk_{m_i}$ for $0 \le i \lt k$.

Alternative HORS using a Merkle tree

• Construct the private key SK and compute the signature nodes $S = (\sigma_0 \ldots \sigma_{k-1})$ as before.
• The HORS public key is derived by constructing a Merkle hash tree on top of the set of $t=2^a$ private key elements.
  • Each of the $t$ key values is used as a leaf node, and the tree will be of height $a$.
  • Publish the value of the root node as the HORS public key.
• The signature consists of the $k$ signature nodes $S=(\sigma_0\ldots \sigma_{k-1})$ and their respective authentication paths.
• To verify, recompute the authentication path for each $\sigma_i$ and check the computed root equals the published public key.

Forest of Random Subsets (FORS)

• FORS is an improvement on HORS, designed by the SPHINCS+ team.
• FORS is similar to HORS except we have $kt$ sets of private keys and $k$ binary hash trees.
• Like HORS, FORS is defined in terms of integers $k$ and $t=2^a$ and can be used to sign a string of $ka$ bits.
• A FORS private key consists of $kt$ random $n$-bit values grouped together into $k$ sets of $t$ values each.
  • In SPHINCS+ these are deterministically derived from SK.seed and the address ADRS of the key in the hypertree.
• Key Generation: To derive a FORS public key, construct $k$ binary hash trees on top of the $k$ sets of $t$ private key elements.
  • Each of the $t=2^a$ values is used as a leaf node, resulting in $k$ trees of height $a$.
  • In SPHINCS+, compress the root nodes using a call to $\textbf{Th}_k$.
  • The resulting $n$-bit value is the FORS public key.
• Signing: Given a message of $ka$ bits, extract $k$ strings of $a$ bits.
• Each of these bit strings is interpreted as the index of a single leaf node ($0\ldots t-1$) in each of the $k$ FORS trees.
  • Use the 1st key set for the first signature value, use the 2nd key set for the second, and so forth.
  • The signature consists of these $k$ nodes and their respective authentication paths.
• Verifying: The verifier recomputes the authentication path for each $\sigma_i$ and checks the computed root equals the published public key.
• Unlike HORS, which selects all its signature values from the same set of $t$ keys, FORS generates $kt$ secret keys and dedicates $t$ secret keys for each index out of the $k$ indices.
• FORS mitigates against weak message attacks because, even if two bitstring segments produce an integer of the same value, their index values form different secret paths.

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.

Rate this page

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 27 February 2024.