Paper 2016/1042

"Oops, I did it again" -- Security of One-Time Signatures under Two-Message Attacks

Leon Groot Bruinderink and Andreas Hülsing

Abstract

One-time signatures (OTS) are called one-time, because the accompanying reductions only guarantee security under single-message attacks. However, this does not imply that efficient attacks are possible under two-message attacks. Especially in the context of hash-based OTS (which are basic building blocks of recent standardization proposals) this leads to the question if accidental reuse of a one-time key pair leads to immediate loss of security or to graceful degradation. In this work we analyze the security of the most prominent hash-based OTS, Lamport's scheme, its optimized variant, and WOTS, under different kinds of two-message attacks. Interestingly, it turns out that the schemes are still secure under two message attacks, asymptotically. However, this does not imply anything for typical parameters. Our results show that for Lamport's scheme, security only slowly degrades in the relevant attack scenarios and typical parameters are still somewhat secure, even in case of a two-message attack. As we move on to optimized Lamport and its generalization WOTS, security degrades faster and faster, and typical parameters do not provide any reasonable level of security under two-message attacks.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. SAC 2017
Keywords
Hash-based signaturesone-time signaturesfew-time signaturespost-quantum cryptographytwo-message attacks.
Contact author(s)
authors-oops @ huelsing net
History
2017-09-25: last of 2 revisions
2016-11-06: received
See all versions
Short URL
https://ia.cr/2016/1042
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1042,
      author = {Leon Groot Bruinderink and Andreas Hülsing},
      title = {"Oops, I did it again" -- Security of One-Time Signatures under Two-Message Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1042},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1042}},
      url = {https://eprint.iacr.org/2016/1042}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.