Cryptology ePrint Archive: Report 2001/010

How to achieve a McEliece-based Digital Signature Scheme

Nicolas Courtois, Matthieu Finiasz and Nicolas Sendrier

Abstract: McEliece is one of the oldest known public key cryptosystems. Though it was less widely studied that RSA, it is remarkable that all known attacks are still exponential. It is widely believed that code-based cryptosystems like McEliece does 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. It's security can be reduced in the random oracle model to the well-known {\em 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^{83}$.

Category / Keywords: public-key cryptography / digital signature, McEliece cryptosystem, Niederreiter cryptosystem, Goppa codes, syndrome decoding, short signatures

Publication Info: ASIACRYPT'2001

Date: received 12 Feb 2001, last revised 19 Oct 2001

Contact author: Nicolas Sendrier at inria fr

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Note: Updated version, to appear in ASIACRYPT'2001

Version: 20011019:090411 (All versions of this report)

Short URL: ia.cr/2001/010

Discussion forum: Show discussion | Start new discussion