“Oops, I did it again” – Security of one-time signatures under two-message attacks

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

One-time signatures (OTS) are called one-time, because the accompanying security 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.

Original languageEnglish
Title of host publicationSelected Areas in Cryptography – SAC 2017
Subtitle of host publication24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers
EditorsCarlisle Adams , Jan Camenisch
Place of PublicationCham
PublisherSpringer
Chapter15
Pages299-322
Number of pages24
ISBN (Electronic)978-3-319-72565-9
ISBN (Print)978-3-319-72564-2
DOIs
Publication statusPublished - 2018
Event24th International Conference on Selected Areas in Cryptography (SAC 2017) - Ottawa, Canada
Duration: 16 Aug 201718 Aug 2017
Conference number: 24

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10719
ISSN (Print)0302-9743
NameSecurity and Cryptology
PublisherSpringer

Conference

Conference24th International Conference on Selected Areas in Cryptography (SAC 2017)
Abbreviated titleSAC 2017
CountryCanada
CityOttawa
Period16/08/1718/08/17

Keywords

  • Few-time signatures
  • Hash-based signatures
  • One-time signatures
  • Post-quantum cryptography
  • Two-message attacks

Fingerprint Dive into the research topics of '“Oops, I did it again” – Security of one-time signatures under two-message attacks'. Together they form a unique fingerprint.

  • Cite this

    Groot Bruinderink, L., & Hülsing, A. T. (2018). “Oops, I did it again” – Security of one-time signatures under two-message attacks. In C. Adams , & J. Camenisch (Eds.), Selected Areas in Cryptography – SAC 2017: 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers (pp. 299-322). (Lecture Notes in Computer Science; Vol. 10719), (Security and Cryptology). Cham: Springer. https://doi.org/10.1007/978-3-319-72565-9_15