TY - GEN
T1 - Tight and Optimal Reductions for Signatures Based on Average Trapdoor Preimage Sampleable Functions and Applications to Code-Based Signatures
AU - Chailloux, André
AU - Debris-Alazard, Thomas
N1 - Publisher Copyright:
© 2020, International Association for Cryptologic Research.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - The GPV construction [GPV08] presents a generic construction of signature schemes in the Hash and Sign paradigm and is used in some lattice based signatures. This construction requires a family 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 (ROM). 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 security for it in the ROM and the QROM, improving and extending the original analysis of [DST19a].
AB - The GPV construction [GPV08] presents a generic construction of signature schemes in the Hash and Sign paradigm and is used in some lattice based signatures. This construction requires a family 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 (ROM). 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 security for it in the ROM and the QROM, improving and extending the original analysis of [DST19a].
UR - https://www.scopus.com/pages/publications/85090013305
U2 - 10.1007/978-3-030-45388-6_16
DO - 10.1007/978-3-030-45388-6_16
M3 - Conference contribution
AN - SCOPUS:85090013305
SN - 9783030453879
T3 - Lecture Notes in Computer Science
SP - 453
EP - 479
BT - Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
A2 - Kiayias, Aggelos
A2 - Kohlweiss, Markulf
A2 - Wallden, Petros
A2 - Zikas, Vassilis
PB - Springer Science and Business Media Deutschland GmbH
T2 - 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020
Y2 - 4 May 2020 through 7 May 2020
ER -