# Do other one-time signature schemes exist?

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).

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).

• Is SPHINCS one-time? Apr 2 '16 at 9:55
• No, there's no limit on the number of signatures in SPHINCS. Apr 3 '16 at 10:56
• what does it mean stateless hash based signature? Nov 19 '17 at 6:06