On the security of the Winternitz one-time signature scheme

Johannes Buchmann; Erik Dahmen; Sarah Ereth; Andreas Hülsing; Markus Rückert

doi:10.1007/978-3-642-21969-6_23

On the security of the Winternitz one-time signature scheme

Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, Markus Rückert

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

74 Citations (Scopus)

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	https://doi.org/10.1007/978-3-642-21969-6_23
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

Access to Document

10.1007/978-3-642-21969-6_23

Cite this

Buchmann, J., Dahmen, E., Ereth, S., Hülsing, A., & Rückert, M. (2011). On the security of the Winternitz one-time signature scheme. In A. Nitaj, & D. Pointcheval (Eds.), Progress in Cryptology – AFRICACRYPT 2011 : 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011 Proceedings (pp. 363-378). (Lecture Notes in Computer Science; Vol. 6737). Springer. https://doi.org/10.1007/978-3-642-21969-6_23

Buchmann, Johannes ; Dahmen, Erik ; Ereth, Sarah et al. / On the security of the Winternitz one-time signature scheme. Progress in Cryptology – AFRICACRYPT 2011 : 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011 Proceedings. editor / A. Nitaj ; D. Pointcheval. Berlin : Springer, 2011. pp. 363-378 (Lecture Notes in Computer Science).

@inproceedings{ed0d37483fb943889c4117777c755c7d,

title = "On the security of the Winternitz one-time signature scheme",

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.",

keywords = "Hash-based signatures, post-quantum signatures, pseudorandom functions, security reductions",

author = "Johannes Buchmann and Erik Dahmen and Sarah Ereth and Andreas H{\"u}lsing and Markus R{\"u}ckert",

year = "2011",

doi = "10.1007/978-3-642-21969-6\_23",

language = "English",

isbn = "9783642219689",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "363--378",

editor = "A. Nitaj and D. Pointcheval",

booktitle = "Progress in Cryptology – AFRICACRYPT 2011",

address = "Germany",

note = "4th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2011), Africacrypt 2011 ; Conference date: 05-07-2011 Through 07-07-2011",

}

Buchmann, J, Dahmen, E, Ereth, S, Hülsing, A & Rückert, M 2011, On the security of the Winternitz one-time signature scheme. in A Nitaj & D Pointcheval (eds), Progress in Cryptology – AFRICACRYPT 2011 : 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011 Proceedings. Lecture Notes in Computer Science, vol. 6737, Springer, Berlin, pp. 363-378, 4th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2011), Dakar, Senegal, 5/07/11. https://doi.org/10.1007/978-3-642-21969-6_23

On the security of the Winternitz one-time signature scheme. / Buchmann, Johannes; Dahmen, Erik; Ereth, Sarah et al.
Progress in Cryptology – AFRICACRYPT 2011 : 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011 Proceedings. ed. / A. Nitaj; D. Pointcheval. Berlin: Springer, 2011. p. 363-378 (Lecture Notes in Computer Science; Vol. 6737).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the security of the Winternitz one-time signature scheme

AU - Buchmann, Johannes

AU - Dahmen, Erik

AU - Ereth, Sarah

AU - Hülsing, Andreas

AU - Rückert, Markus

N1 - Conference code: 4

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Hash-based signatures

KW - post-quantum signatures

KW - pseudorandom functions

KW - security reductions

UR - http://www.scopus.com/inward/record.url?scp=79960076269&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-21969-6_23

DO - 10.1007/978-3-642-21969-6_23

M3 - Conference contribution

AN - SCOPUS:79960076269

SN - 9783642219689

T3 - Lecture Notes in Computer Science

SP - 363

EP - 378

BT - Progress in Cryptology – AFRICACRYPT 2011

A2 - Nitaj, A.

A2 - Pointcheval, D.

PB - Springer

CY - Berlin

T2 - 4th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2011)

Y2 - 5 July 2011 through 7 July 2011

ER -

Buchmann J, Dahmen E, Ereth S, Hülsing A, Rückert M. On the security of the Winternitz one-time signature scheme. In Nitaj A, Pointcheval D, editors, Progress in Cryptology – AFRICACRYPT 2011 : 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011 Proceedings. Berlin: Springer. 2011. p. 363-378. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-21969-6_23

On the security of the Winternitz one-time signature scheme

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this