How to achieve a McEliece-based Digital Signature Scheme.
Nicolas T. Courtois, Matthieu Finiasz, Nicolas Sendrier · 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 codebased cryptosystems like McEliece do not allow practical digital signatures. In the present paper we disprove thisbelief 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 syndrome decoding problem and the distinguishability ofpermuted 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. Key Words: digital signature, McEliece cryptosystem, Niederreiter cryptosystem, Goppa codes, syndrome decoding, short signatures.