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 language | English |
---|---|
Title of host publication | Selected Areas in Cryptography – SAC 2017 |
Subtitle of host publication | 24th International Conference, Ottawa, ON, Canada, August 16-18, 2017, Revised Selected Papers |
Editors | Carlisle Adams , Jan Camenisch |
Place of Publication | Cham |
Publisher | Springer |
Chapter | 15 |
Pages | 299-322 |
Number of pages | 24 |
ISBN (Electronic) | 978-3-319-72565-9 |
ISBN (Print) | 978-3-319-72564-2 |
DOIs | |
Publication status | Published - 2018 |
Event | 24th International Conference on Selected Areas in Cryptography (SAC 2017) - Ottawa, Canada Duration: 16 Aug 2017 → 18 Aug 2017 Conference number: 24 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 10719 |
ISSN (Print) | 0302-9743 |
Name | Security and Cryptology |
---|---|
Publisher | Springer |
Conference
Conference | 24th International Conference on Selected Areas in Cryptography (SAC 2017) |
---|---|
Abbreviated title | SAC 2017 |
Country/Territory | Canada |
City | Ottawa |
Period | 16/08/17 → 18/08/17 |
Funding
This work was supported by the Commission of the European Communities through the Horizon 2020 program under project number 645622 PQCRYPTO. Permanent ID of this document: 85629c7dc69dad1c4be4fbd7e360086c. Date: September 25, 2017.
Keywords
- Few-time signatures
- Hash-based signatures
- One-time signatures
- Post-quantum cryptography
- Two-message attacks