Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

In this session, we will talk about McEliece assumptions. The security of the McEliece scheme is based on two assumptions as we have already seen: the hardness of decoding a random linear code and the problem of distinguishing a code with a prescribed structure from a random one. In this sequence, we will study in detail these two assumptions. The first assumption claims that decoding a random linear code is difficult.  First, notice that the general decoding problem is basically a re-writing of the Syndrome Decoding problem. And both are equivalent to the problem of finding codewords of minimal weight. The Syndrome Decoding in the binary case is state as follows. Given a binary matrix, a syndrome S and a non-negative integer W, the weight. The decision problem faces the following question. There exists an error pattern of weight at most w with syndrome S? while the computational problem is to find such a vector. The decoding problem was proved to be NP-complete in 1978 by Berlekamp, McEliece and van Tilborg in this article. For the q-ary case, see the article of Barg. Take notice that this proof took place at the same time that the McEliece cryptosystem was introduced. Thus, the worst case of the computational problem is known to be difficult in general. Of course, depending on the input, some instances can be solved in polynomial time as we have already seen in the first week. Actually, the instance of Syndrome Decoding involved in breaking code-based systems are in particularly a subclass of Syndrome Decoding where the weight w is bounded by half the minimum distance. This problem is not NP, however it is conjectured to be NP-Hard. But even more in the McEliece cryptosystem, the chosen code is not completely random. Even if the matrix is not distinguishable from a random binary matrix of the same size, the decoding problem uses parameters of those of a Goppa code. This means that the code has length 2^m and the dimension is n mt, where t is the correction capacity.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Thème(s)