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?
$\begingroup$
$\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$– ambisoCommented Nov 20, 2020 at 19:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
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.
-
$\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 ♦Commented Mar 28, 2017 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$– ponchoCommented Mar 28, 2017 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$– ponchoCommented Mar 28, 2017 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$– ponchoCommented Mar 28, 2017 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$– mephistoCommented Mar 29, 2017 at 21:30
$\begingroup$
$\endgroup$
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.
