BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures

Cas Cremers; Samed Düzlü; Rune Fiedler; Marc Fischlin; Christian Janson

Paper 2020/1525

BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures

Cas Cremers

, CISPA Helmholtz Center for Information Security, Germany

Samed Düzlü

, Universität Regensburg, Germany

Rune Fiedler, Technische Universität Darmstadt, Germany

Marc Fischlin

, Technische Universität Darmstadt, Germany

Christian Janson

, Technische Universität Darmstadt, Germany

Abstract

Modern digital signature schemes can provide more guarantees than the standard notion of (strong) unforgeability, such as offering security even in the presence of maliciously generated keys, or requiring to know a message to produce a signature for it. The use of signature schemes that lack these properties has previously enabled attacks on real-world protocols. In this work we revisit several of these notions beyond unforgeability, establish relations among them, provide the first formal definition of non re-signability, and two generic transformations that can provide these properties for a given signature scheme in a provable and efficient way. Our results are not only relevant for established schemes: for example, the ongoing NIST PQC competition towards standardizing post-quantum signature schemes had six candidates in its third round of which three are to be standardized. We perform an in-depth analysis of all the candidates with respect to their security properties beyond unforgeability. We show that many of them do not yet offer these stronger guarantees, which implies that the security guarantees of these post-quantum schemes are not strictly stronger than, but instead incomparable to, classical signature schemes. We show how applying our transformations would efficiently solve this, paving the way for the standardized schemes to provide these additional guarantees and thereby making them harder to misuse.

Note: Version 1.4 - October 2023: Jelle Don, Serge Fehr, Yu-Hsuan Huang, and Patrick Struck pointed out a flaw in non re-signability in all previous versions. We have fixed this issue by restricting the message sampler in the non re-signability Definition 4.3 to output computationally-independent auxiliary information. Version 1.4.1 - October 2023: added citation [DFHS23]

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. IEEE Symposium on Security and Privacy (S&P 2021)
Keywords: Digital signature scheme exclusive ownership DSKS attack non re-signability message-bound signatures NIST PQC candidates
Contact author(s): cremers @ cispa de
samed duzlu @ ur de
rune fiedler @ cryptoplexity de
marc fischlin @ cryptoplexity de
christian janson @ cryptoplexity de
History: 2023-10-23: last of 5 revisions; 2020-12-08: received; See all versions
Short URL: https://ia.cr/2020/1525
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1525,
      author = {Cas Cremers and Samed Düzlü and Rune Fiedler and Marc Fischlin and Christian Janson},
      title = {BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1525},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1525}},
      url = {https://eprint.iacr.org/2020/1525}
}