[Cryptography] Many-times signatures, faster than one

[Santi J. Maccallini]

Hi all,
I want to share some interesting improvements on hash-based-signatures that
I've found.

In typical signatures schemes (for example DSA, ECDSA) one is able to
generate an arbitrary number of signatures, and the size of each signatures
is constant and independent on the number of signatures.

That's not the case with hash-based signatures.  In signatures the size and
cost depend on the number of signatures:
Hash-based based signatures use a one-time signature (OTS) as its building
block, only useful to sign one message per key. The one-time signature is
then transformed into a many-times scheme using a Merkle tree (or a modern
variant, for example XMSS). As the number of needed signatures grows, the
tree gets larger. As a result , the cost and the size of the signatures
increase as well. They can get quite big compared to classical schemes.

The improvement follows from studying signatures in a blockchain, where all
signatures become public. In the paper I show that it is possible to
construct many-times signatures more efficient on than an OTS. As the
number of signatures grows, the signatures become more and more efficient.
This is quite unlike previous schemes.

If keys are used to sign a sufficient number of messages, they can
outperform classical signatures by a wide margin.

For anyone interested, it's explained in more detail here:
http://jotasapiens.com/research

>From One to Many: Synced Hash-Based Signatures (2017)
sha256 0fdc28c3c3a14f37004c23aa93bfc7b4efbd028cf8d6bcc8ae5df0

Cheers,
Santi J.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170406/eee3d2b1/attachment.html>