Skip to Main content Skip to Navigation
Conference papers

Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes

Abstract : We present here a new family of trapdoor one-way Preimage Sampleable Functions (PSF) based on codes, the Wave-PSF family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized (U,U+V)-codes. Our proof follows the GPV strategy [GPV08]. By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property of our family is ensured by using and proving a variant of the left-over hash lemma. We instantiate the new Wave-PSF family with ternary generalized (U,U+V)-codes to design a “hash-and-sign” signature scheme which achieves existential unforgeability under adaptive chosen message attacks(EUF-CMA) in the random oracle model. For 128 bits of classical security, signature sizes are in the order of 15 thousand bits, the public key size in the order of 4 megabytes, and the rejection rate is limited to one rejection every 10 to 12 signatures.
Complete list of metadata

https://hal.inria.fr/hal-02424057
Contributor : Jean-Pierre Tillich <>
Submitted on : Thursday, December 26, 2019 - 3:19:54 PM
Last modification on : Monday, February 22, 2021 - 12:42:04 PM

Links full text

Identifiers

Collections

Citation

Thomas Debris-Alazard, Nicolas Sendrier, Jean-Pierre Tillich. Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes. ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2019, Kobe, Japan. pp.21-51, ⟨10.1007/978-3-030-34578-5_2⟩. ⟨hal-02424057⟩

Share

Metrics

Record views

124