Jeudi 21 février 2019 à 16h30 en salle C48
Thomas Debris-Alazard (INRIA)
Titre : Wave: A New Code-Based Signature Scheme
Résumé :
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. For 128 bits of classical security, signatures are 8 thousand
bits long and the public key is smaller than one megabyte.