I'm curious to know if there are any one-time signature schemes other than Lamport's or its variants (Merkle trees are one such variant). The first I've discovered is called "Bins and Balls" which doesn't use a trapdoor function.

Any others? Are they smaller than Lamport signatures? I'd like descriptions, too (also of BiBa).


1 Answer 1


HORS (Hash to Obtain Random Subset) is a simple few-time signature scheme with smaller signatures than BiBa.

Let $f$ be a one-way function and $H$ be a hash function that outputs a random size $k$ subset of $\{1,2,...,t\}$, where $k$ and $t$ are parameters that affect security with $k < t$.

The signing key is a random tuple $(s_1,...,s_t)$, and the public key is $(f(s_1),...,f(s_t))$. Now to sign a message $m$, compute the set $S = H(m)$ and output $\{s_i : i \in S\}$. To verify, apply $f$ to each element of the signature and check this matches with the public key.

Each signature reveals $k$ elements of the secret key, so depending on the choice of $k$ and $t$, a few messages can be signed before security is compromised.

This was used as a building block in SPHINCS, which is a stateless hash-based signature scheme that allows unlimited messages to be signed (but is much more complex).

  • $\begingroup$ Is SPHINCS one-time? $\endgroup$
    – Melab
    Commented Apr 2, 2016 at 9:55
  • $\begingroup$ No, there's no limit on the number of signatures in SPHINCS. $\endgroup$
    – pscholl
    Commented Apr 3, 2016 at 10:56
  • $\begingroup$ what does it mean stateless hash based signature? $\endgroup$
    – Infinity
    Commented Nov 19, 2017 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.