Ressource pédagogique : 2.1. Formal Definition

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

Welcome to the second week of this MOOC entitled Code-Based Cryptography. This week, we will talk in detail about the McEliece cryptosystem. First, in this session, we will describe formally the McEliece and the Niederreiter systems, which are the principal public-key schemes, based on error-correcting code. Let K be a security parameter. An encryption scheme is defined by the following spaces: the space of all possible messages, the space of all ciphertexts, the space of the public-keys, and the space of the secret-keys.Then, we need to define the following algorithms. A key generation algorithm, which is a randomized algorithm that outputs a public-key and a secret-key; this algorithm should run in expected polynomial time. An encryption algorithm, which is also a randomized algorithm that takes a message and the public-key and outputs a ciphertext; this algorithm runs also in expected polynomial time. And a decryption algorithm, which is an algorithm that takes a ciphertext and a secret-key, and outputs the original plaintext or declares a failure; this algorithm runs in polynomial time. It is required that the decryption of the ciphertext is again the plaintext, and we demand that the fasten attack on the system requires at least 2^k bit operations. In 1978, McEliece introduced the first public-key cryptosystem, as we have already seen, based on error-correcting codes. The security of this scheme is based on two intractable problems: the hardness of decoding, and the problem of distinguishing a code with a prescribed structure. This property makes this scheme an interesting candidate for post-quantum cryptography. Another advantage consists of its fast encryption and decryption algorithms. But the main drawback is the large size of the keys. We will use as public-key, a large generator matrix.

"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)