Paper 2018/996
Wave: A New Code-Based Signature Scheme
Thomas Debris-Alazard and Nicolas Sendrier and Jean-Pierre Tillich
Abstract
We present here Wave the first ``hash-and-sign'' code-based signature scheme which strictly follows the GPV strategy [GPV08]. It uses the family of ternary generalized $(U,U+V)$ codes. We prove that Wave achieves {\em existential unforgeability under adaptive chosen message attacks} (EUF-CMA) in the random oracle model (ROM) with a tight reduction to two assumptions from coding theory: one is a distinguishing problem that is related to the trapdoor we insert in our scheme, the other one is DOOM, a multiple target version of syndrome decoding. The algorithm produces uniformly distributed signatures through a suitable rejection sampling. Our scheme enjoys efficient signature and verification algorithms. For 128 bits of classical security, signature are $8$ thousand bits long and the public key size is slightly smaller than one megabyte. Furthermore, with our current choice of parameters, the rejection rate is limited to one rejection every 3 or 4 signatures.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Code-based CryptographySignature SchemeGPVSecurity ProofDecoding Algorithm
- Contact author(s)
- thomas debris @ 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