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

It is a long-standing open problem to build an efficient and secure digital signature scheme based on the hardness of decoding a linear code which could compete with widespread schemes like DSA or RSA. The latter signature schemes are broken by a quantum computer with Shor’s algorithm. Code-based schemes could provide a valid quantum resistant replacement. We present here Wave the first « hash-and-sign » code-based signature scheme which strictly follows the GPV strategy which ensures universal unforgeability. It uses the family of ternary generalized $(U, U+V)$ codes. Our algorithm produces uniformly distributed signatures through a suitable rejection sampling (one rejection every 3 or 4 signatures). Furthermore, our scheme enjoys efficient signature and verification algorithms. Typically, for 128 bits of classical security, signatures are in the order of 10 thousand bits long and the public key is in the order of one megabyte.​