Paper 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}$.
Note: Updated version, to appear in ASIACRYPT'2001
Metadata
- Available format(s)
- PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. ASIACRYPT'2001
- Keywords
- digital signatureMcEliece cryptosystemNiederreiter cryptosystemGoppa codessyndrome decodingshort signatures
- Contact author(s)
- Nicolas Sendrier @ inria fr
- History
- 2001-10-19: revised
- 2001-02-17: received
- See all versions
- Short URL
- https://ia.cr/2001/010
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2001/010,
author = {Nicolas Courtois and Matthieu Finiasz and Nicolas Sendrier},
title = {How to achieve a {McEliece}-based Digital Signature Scheme},
howpublished = {Cryptology {ePrint} Archive, Paper 2001/010},
year = {2001},
url = {https://eprint.iacr.org/2001/010}
}
