[Resource Topic] 2023/588: Wave Parameter Selection

Welcome to the resource topic for 2023/588

Wave Parameter Selection

Authors: Nicolas Sendrier


Wave is a provably EUF-CMA (existential unforgeability under adaptive chosen message attacks) digital signature scheme based on codes \cite{DST19a}. It is an hash-and-sign primitive and its security is built according to a GPV-like framework \cite{GPV08} under two assumptions related to coding theory: (i) the hardness of finding a word of prescribed Hamming weight and prescribed syndrome, and (ii) the pseudo-randomness of ternary generalized (U|U+V) codes. Forgery attacks (i)—or message attacks—consist in solving the ternary decoding problem for large weight \cite{BCDL19}, while, to the best of our knowledge, key attacks (ii) will try to exhibit words that are characteristic of (U|U+V) codes, which are called type-U or type-V codewords in the present paper. In the current state-of-the-art, the best known attacks both reduce to various flavours of Information Set Decoding (ISD) algorithms for different regime of parameters. In this paper we give estimates for the complexities of the best known ISD variants for those regimes. Maximizing the computational effort, thus the security, for both attacks lead to conflicting constraints on the parameters. We provide here a methodology to derive optimal trade-offs for selecting parameters for the Wave signature scheme achieving a given security. We apply this methodology to the current state-of-the-art and propose some effective parameters for Wave. For \lambda=128 bits of classical security, the signature is 737 bytes long, scaling linearly with the security, and the public key size is 3.6 Mbytes, scaling quadratically with the security.

ePrint: https://eprint.iacr.org/2023/588

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .