International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Thomas Debris-Alazard
Nicolas Sendrier
Jean-Pierre Tillich
Download:
DOI: 10.1007/978-3-030-34578-5_2
Search ePrint
Search Google
Award: Best Paper
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 [28]. 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.
BibTeX
@article{asiacrypt-2019-30009,
  title={Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11921},
  pages={21-51},
  doi={10.1007/978-3-030-34578-5_2},
  author={Thomas Debris-Alazard and Nicolas Sendrier and Jean-Pierre Tillich},
  year=2019
}