Wave: a New Family of Trapdoor One-Way PSF Based on Codes

Intervenant(s) : Thomas Debris
(joint work with Nicolas Sendrier and Jean-Pierre Tillich)
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 $UV$-codes. Our proof follows the GPV strategy. 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 $UV$-codes to design a « hash-and-sign » signature scheme which achieves {em 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 13 thousand bits, the public key size in the order of 3 megabytes, and the rejection rate is limited to one rejection every 10 to 12 signatures.
damien.vergnaud (at)