How to achieve a McEliece-based digital signature scheme.

Nicolas Courtois
Systèmes Information Signal (SIS),
Toulon University
BP 132
83957 La Garde Cedex, France
courtois@minrank.org

Matthieu Finiasz
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Matthieu.Finiasz@inria.fr

Nicolas Sendrier
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Nicolas.Sendrier@inria.fr

In Advances in Cryptology - ASIACRYPT 2001, number 2248 in LNCS, pages 157-174. Springer-Verlag, 2001.

Abstract

McEliece is one of the oldest known public key cryptosystems.Though it was less widely studied than RSA,it is remarkable that all known attacks are still exponential.It is widely believed that code-based cryptosystems like McEliece do not allow practical digital signatures.In the present paper we disprove this belief and show a way to build a practical signature scheme based on coding theory.Its security can be reduced in the random oracle model to the well-known syndrome decoding problem and the distinguishability of permuted binary Goppa codes from a random code.For example we propose a scheme with signatures of 81 bits and a binary security workfactor of 2⁸³.

Keywords

Digital signature,McEliece cryptosystem,Niederreiter cryp- tosystem,Goppa codes,syndrome decoding,short signatures.

See also

Nicolas Courtois, Matthieu Finiasz and Nicolas Sendrier. How to Achieve a McEliece-Based Digital Signature Scheme. Cryptology ePrint archive, Report 2001/010, February 2001.
Nicolas Courtois, Matthieu Finiasz and Nicolas Sendrier. How to Achieve a McEliece-Based Digital Signature Scheme. Rapport de recherche RR-4118, INRIA, February 2001.