Abstract
We show that the Winternitz one-time signature scheme is existentially unforgeable under adaptive chosen message attacks when instantiated with a family of pseudo random functions. Compared to previous results, which require a collision resistant hash function, our result provides significantly smaller signatures at the same security level. We also consider security in the strong sense and show that the Winternitz one-time signature scheme is strongly unforgeable assuming additional properties of the pseudo random function. In this context we formally define several key-based security notions for function families and investigate their relation to pseudorandomness. All our reductions are exact and in the standard model and can directly be used to estimate the output length of the hash function required to meet a certain security level.
Original language | English |
---|---|
Title of host publication | Progress in Cryptology – AFRICACRYPT 2011 |
Subtitle of host publication | 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011 Proceedings |
Editors | A. Nitaj, D. Pointcheval |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 363-378 |
Number of pages | 16 |
ISBN (Print) | 9783642219689 |
DOIs | |
Publication status | Published - 2011 |
Externally published | Yes |
Event | 4th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2011) - Dakar, Senegal Duration: 5 Jul 2011 → 7 Jul 2011 Conference number: 4 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 6737 |
ISSN (Print) | 03029743 |
ISSN (Electronic) | 16113349 |
Conference
Conference | 4th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2011) |
---|---|
Abbreviated title | Africacrypt 2011 |
Country/Territory | Senegal |
City | Dakar |
Period | 5/07/11 → 7/07/11 |
Keywords
- Hash-based signatures
- post-quantum signatures
- pseudorandom functions
- security reductions