6
$\begingroup$

There are several one-time signature schemes. The original one - Lamport - has very big signature sizes (several kbs). Is there an one-time signature scheme on which relies only on simple assumptions (one-way functions and random oracle), and on which signatures are no larger than a few bytes?

$\endgroup$
1
  • $\begingroup$ Since signature schemes like BLS or Schnorr/ECDSA are also one-time secure, technically you could include these too, so for BLS that would be 48 bytes :-) $\endgroup$
    – cisnjxqu
    Nov 20 '20 at 19:30
9
$\begingroup$

Well, if we assume a 128 bit hash function (and arrange things such that we assume only (second) preimage resistance), and use a Winternitz scheme with W=65536 (signing/verifying will be expensive), that'll get you down to about 168 bytes (assuming you insert an 8 byte randomizer into the initial hash, needed if we assume that the attacker can choose the message to be signed).

If we are even more aggressive (80 bit hash; may be good enough assuming it doesn't have to be TLA-proof), and W=$2^{29}$ (so Winternitz needs only a single check digit; signing/verifying will be real expensive), and a 4 byte randomizer, that gets you down to 44 bytes; but you had to make a lot of sacrifices to get to that level.

$\endgroup$
10
  • $\begingroup$ Is the first proposed construction similar to that in Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas T. Hülsing, and Markus Rückert's On the Security of the Winternitz One-Time Signature Scheme (extended abstract in proceedings of Africacrypt 2011), with $b=64$ and $w=16$? $\endgroup$
    – fgrieu
    Mar 28 '17 at 12:53
  • 1
    $\begingroup$ @fgrieu: actually, $w=65536$ in their notation, and I believe the security level $b$ would be 128 (although their proof gives a rather smaller value), but otherwise, yes... $\endgroup$
    – poncho
    Mar 28 '17 at 13:26
  • 1
    $\begingroup$ @fgrieu: this is notation, but yes, I'm sure Buchmann et al use the convention that $w$ (actually, $w-1$) is the length of the Winternitz chain, and so you end up doing $O(w)$, not $O(2^w)$ operations. As for W-OTS+, Andreas's improvement is improved provable security, not shortened signatures; he shows that his scheme achieves the security level you'd expect (as opposed to Buchmann et al's scheme, where they proved a significantly smaller level); I already assumed that when I said "I believe the security level $b$ would be 128" $\endgroup$
    – poncho
    Mar 28 '17 at 14:04
  • 1
    $\begingroup$ @fgrieu: hmmm, yes, it appears that document is a bit inconsistent. However, if you read further papers by those authors, they do use the "$w$ is the Winternitz length/base" convention... $\endgroup$
    – poncho
    Mar 28 '17 at 14:40
  • 1
    $\begingroup$ @fgrieu: In the security claim this $w$ definitely refers to the chain length. The typo on page 2 is probably there because most previous papers used the $2^w$ chain length terminology while this paper was the first that allowed chains of length which is not a power of two. The reasoning at that time was that it might lead to better trade-offs which I think turned out wrong. $\endgroup$
    – mephisto
    Mar 29 '17 at 21:30
1
$\begingroup$

To add to the answer by poncho: Theoretically, there is also the Bleichenbacher-Maurer Scheme (probably best described in Dods, Smart, Stam: "Hash Based Digital Signature Schemes". Cryptography and Coding, LNCS 3796, pp 96-115, Springer Berlin / Heidelberg, 2005) which is asymptotically more efficient than WOTS and can be proven optimal in some metric. However, this is paid for with a terribly complex construction which is why people are not using it. So W-OTS with large w is your tool.

$\endgroup$

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.