7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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