Algebraic approach for the study of algorithmic problems coming from cryptography and the theory of error correcting codes
Vlad Drăgoi · HAL (Le Centre pour la Communication Scientifique Directe) · 2017
McEliece's encryption scheme represents one of the solutions to the security issues that are raised by the possible arrival of quantum computers. The main objective of this thesis is to analyze the security of the McEliece varinats based on MDPC and polar codes.In the case of the MDPC based variant, we manage to reveal a subset of private keys that present an important weakness. We proposed an efficient algorithm that retrieves,for the set of weak keys, the private key given the public key of the system. Next we counted the proportion of weak keys and we used the code equivalence problem to extend the number of keys, that can be retreived with the aforementioned algorithm.We next studied the polar codes and their application to public key cryptography.From an information theory point of view, polar codes have been one of the most studied families of codes, ever since their discovery by Arikan. They are extremely efficient in terms of performance as they are capacity achieving over the Binary Discrete Memoryless Channels and they allow extremely fast encoding and decoding algorithms. Nonetheless, only a few facts are known about their structure. In this context, we introduce an algebraic formalism which allows us to reveal a big part of their structure. We exhibit a few fundamental traits of polar codes: the dual, the minimum distance, the permutation group and the number of minimum weight codewords.We also completely cryptanalyze the McEliece variant using polar codes. The attack is a direct application of the later results on the structure of polar codes.