zbMATH — the first resource for mathematics

On the security of the McEliece public-key cryptosystem. (English) Zbl 1072.94007
Blaum, Mario (ed.) et al., Information, coding and mathematics. Proceedings of workshop honoring Professor Bob McEliece on his 60th birthday, Pasadena, CA, USA, May 24–25, 2002. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7079-9/hbk). The Kluwer International Series in Engineering and Computer Science 687, 141-163 (2002).
The author discusses the main aspects of the McEliece cryptosystem and its dual Niederreiter’s variant. In these systems, the ciphertext is a corrupted codeword (or its syndrome) and the decryption consists in applying a decoding procedure. It is assumed that these systems use rational binary Goppa codes which provide probably the best choice at present time.
In \(\S 2\) the author presents the encryption schemes and describes in \(\S 3\) how they can be implemented. The \(\S 4\) is devoted to cryptanalysis which are divided into two categories: the decoding attacks which are directed on one particular ciphertext, and the structural attacks aimed on the public key. In \(\S 5\) the author presents the main features of the digital signature schemes, and finally in \(\S 6\) he formally proves that the breaking code-based public-key cryptosystem is at least as hard as solving one out of two supposedly difficult problems: the distinguishability of rational Goppa codes and the decoding of a linear code with Goppa parameters.
In conclusion, the author notes that the security of McEliece (and Niederreiter) cryptosystem is good in all aspects and encryption and decryption have a very low algorithmic complexity, though the signing cost of the digital signature scheme is relatively high. Other serious drawbacks are an information rate strictly smaller than one, and a very large key size.
For the entire collection see [Zbl 1054.94001].

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
94B05 Linear codes, general
94B35 Decoding
94-06 Proceedings, conferences, collections, etc. pertaining to information and communication theory