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

Thomas Debris-Alazard; Nicolas Sendrier; Jean-Pierre Tillich

Paper 2018/996

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

Thomas Debris-Alazard, Nicolas Sendrier, and Jean-Pierre Tillich

Abstract

We present here a new family of trapdoor one-way functions that are Preimage Sampleable on Average (PSA) based on codes, the Wave-PSA 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-PSA 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 13 thousand bits, the public key size in the order of 3 megabytes, and the rejection rate is below one rejection every 100 signatures.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. ArXiv
Keywords: Code-based Cryptography Signature Scheme GPV Security Proof Decoding Algorithm
Contact author(s): thomas debris @ inria fr
nicolas sendrier @ inria fr
jean-pierre tillich @ inria fr
History: 2019-10-28: last of 4 revisions; 2018-10-22: received; See all versions
Short URL: https://ia.cr/2018/996
License: CC BY

BibTeX

@misc{cryptoeprint:2018/996,
      author = {Thomas Debris-Alazard and Nicolas Sendrier and Jean-Pierre Tillich},
      title = {Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/996},
      year = {2018},
      url = {https://eprint.iacr.org/2018/996}
}