- Label UNT : UNIT
- Date de réalisation : 5 Mai 2015
- Durée du programme : 6 min
- Classification Dewey : Analyse numérique, Théorie de l'information, données dans les systèmes informatiques, cryptographie, Mathématiques
- Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
- Langue : Anglais
- Mots-clés : algèbre linéaire, chiffrement à clé publique, cryptage des données, cryptographie, McEliece, LDPC, MDPC
- Conditions d’utilisation / Copyright : Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
2.5. Critical Attacks - Semantic Secure Conversions
In this session, we will
study critical attacks against the public-key cryptosystem.
The partial knowledge on the plaintext reduces
drastically the computational cost of the attack to the
McEliece cryptosystem. For example, suppose that the
adversary knows r bits of the plaintext. Then the difficulty of
recovering the remaining k - r
bits in the complete McEliece with parameters [n, k] is equivalent to that of recovering the full plaintext in
the McEliece with parameters [n, k - r]. This is given by this formula. You just need to observe this equation where G_I denotes the restriction of the matrix G to the rows indexed by I. We study another attack, which is called the reaction attack. In this attack, the adversary just needs to observe the reaction of the receiver. So, this attack can be classified as a CCA but with a weaker assumption. This attack rests upon the following premise: a decoder will not attempt to correct a vector with t + 1 or more errors. The idea of the attack is the following: first of all, an adversary flips one bit of the ciphertext. Then, the adversary transmits the flipped ciphertext to the receiver and observes his reaction. The receiver could have two possible reactions.
First reaction: if the flipped bit is an error-free position, then the ciphertext will have t + 1 errors, so it is uncorrectable. The second reaction: if i is an error position, then the flipped ciphertext will have t - 1 error, and the receiver will be able to decrypt it. We repeat this process for every position until we have retrieved the error pattern. Another possible attack is the resend-message attack. Note that the encryption of the same message twice produces two different ciphertext. A message-resend condition can be easily detected by observing the weight of the sum of the two ciphertexts.
Note that the sum of the two ciphertexts is the sum of the two error vectors, what we have here. But, if the underlying plaintexts are different, then the expected weight of the sum is about the dimension of the code. Let