CryptoDB
Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes
| Authors: | |
|---|---|
| Download: | |
| 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
}