Tight and Optimal Reductions for Signatures based on Average Trapdoor Preimage Sampleable Functions and Applications to Code-Based Signatures

André Chailloux; Thomas Debris-Alazard

Paper 2020/006

Tight and Optimal Reductions for Signatures based on Average Trapdoor Preimage Sampleable Functions and Applications to Code-Based Signatures

André Chailloux and Thomas Debris-Alazard

Abstract

The GPV construction [GPV08] presents a generic construction of signature schemes in the Hash and Sign paradigm. This construction requires a family F of trapdoor preimage sampleable functions (TPSF). In this work we extend this notion to the weaker Average TPSF (ATPSF) and show that the GPV construction also holds for ATPSF in the Random Oracle Model. We also introduce the problem of finding a Claw with a random function (Claw(RF)) and present a tight security reduction to the Claw(RF) problem. Our reduction is also optimal meaning that an algorithm that solves the Claw(RF) problem breaks the scheme. We extend these results to the quantum setting and prove this same tight and optimal reduction in the QROM. Finally, we apply these results to code-based signatures, notably the Wave signature scheme and prove tight and optimal reductions for it in the ROM and the QROM improving and extending the original analysis of [DST19a]

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: post-quantum signature schemes quantum random oracle model code-based cryptography trapdoor preimage sampleable functions
Contact author(s): thomas debris @ rhul ac uk
andre chailloux @ inria fr
History: 2020-01-03: received
Short URL: https://ia.cr/2020/006
License: CC BY

BibTeX

@misc{cryptoeprint:2020/006,
      author = {André Chailloux and Thomas Debris-Alazard},
      title = {Tight and Optimal Reductions for Signatures based on Average Trapdoor Preimage Sampleable Functions and Applications to Code-Based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2020/006},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/006}},
      url = {https://eprint.iacr.org/2020/006}
}