Ressource pédagogique : 2.8. Reducing the Key Size - MDPC codes

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

This is the last session where we will talk about reducing the key size. Here we will introduce the MDPC codes. In 2012, the MDPC codes were proposed for the McEliece schemes. An MDPC code is a code that admits a binary moderate density-parity check matrix. Typically, the Hamming weight of each row is of the order the square of the length. In this sequence, I will describe this scheme of quasi-cyclic MDPC McEliece for a binary code of rate one half. So, we use circulant matrices of blocks of size p to define the codes. The length will be 2p and the dimension p. Other parameters are the weight of the parity check equations and the number of correctable errors. So, let us explain the McEliece schemes using quasi-cyclic MDPC code. First of all, we pick randomly two vectors of weight p, such that the concatenated vector has a weight smaller than w. We will repeat until the corresponding polynomial h0 is invertible. In particular, we ask the weight to be odd. Then, the secret key and the public key will be the corresponding matrices. To encrypt a message, we apply the following function, that is, we encode the message and we add random errors of weight smaller than t. But we will describe them in terms of polynomial. To decrypt, we use an MDPC-like iterative decoding algorithm as the Gallager's Bit-Flipping algorithm, already explained in the previous session. The quasi-cyclic MDPC proposal is secure under two assumptions. First of all, the problem of distinguishing a public key from a random quasi-cyclic matrix or equivalently the problem of finding codewords of weight w in the dual of an MDCP code; and the hardness of decoding random quasi-cyclic codes. The security reduction can be translated in terms of polynomials as follows.

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