Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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 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 (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].
Complete list of metadata

https://hal.inria.fr/hal-03138441
Contributor : André Chailloux Connect in order to contact the contributor
Submitted on : Thursday, February 11, 2021 - 10:40:48 AM
Last modification on : Friday, January 21, 2022 - 3:17:14 AM

Identifiers

Collections

Citation

André Chailloux, Thomas Debris-Alazard. Tight and Optimal Reductions for Signatures Based on Average Trapdoor Preimage Sampleable Functions and Applications to Code-Based Signatures. PKC 2020 - IACR International Conference on Public-Key Cryptography, Jun 2020, Edinburgh / Virtual, United Kingdom. pp.453-479, ⟨10.1007/978-3-030-45388-6_16⟩. ⟨hal-03138441⟩

Share

Metrics

Les métriques sont temporairement indisponibles