Canal-U

4.1. Introduction

Welcome to the fourth week of the MOOC Code-based Cryptography. Recall that we have mainly two ways of cryptanalyzing in the McEliece cryptosystem. We have Message Attacks, which address the problem of decoding a random linear code; these attacks has already been studied in the third week, by Nicolas Sendrier. Notice that efficient generic attack just makes the use of larger code in the McEliece scheme necessary. And we also have Key Attacks. These attacks try to retrieve the code structure, rather than attempting to use an specific decoding algorithm. These attacks will be studied during this week. First, let us give a small introduction. The principle of the McEliece cryptosystem is as follows: consider a large family of codes, with an efficient decoding algorithm, which is indistinguishable from a random family of linear codes of the same length and dimension. Then, the public key is a generator matrix of a code of the chosen family and the number of errors that we can correct. And the secret key is an efficient decoding algorithm specific for such code. The encryption algorithm: we take a plaintext and the public key, and we generate an error-vector of weight at most t, which is the error-correcting capacity. We encode the message using the public key, then, the ciphertext is just the resulting codeword, and the error. How to decrypt? We just apply the secret key that is an efficient decoding algorithm, to retrieve the original message. McEliece proposed to use binary Goppa code, but the parameters that he proposed are not enough nowadays. But there exist other families suitable for the McEliece scheme? On the following slides, we give a summary of these different proposals.