*11:51*[PhD][Update] Alexander Meurer: A Coding-Theoretic Approach to Cryptanalysis

Name: Alexander Meurer

Topic: A Coding-Theoretic Approach to Cryptanalysis

Category:foundations

Description: In this thesis we study the applicability of coding-theoretic algorithms to cryptanalysis and provide new insights into the practical security of different cryptographic primitives. The main results can be summarised as follows:

**"Information Set Decoding"**(ISD) algorithms. This class contains all instantiations of the best-known generic decoding algorithms for random linear codes to date.

**representation technique**, we design a new ISD algorithm which asymptotically achieves an exponential improvement over all known methods. Within the generalised ISD framework we provide a rigorous formal proof of superiority of the new algorithm for arbitrary code rates.

**McEliece one-way function**and we efficiently break all low-noise instances of the

**"Learning Parities with Noise"**(LPN) problem. The main technical contribution of this part is a refined non-asymptotic analysis of the proposed algorithm.

**error correction in RSA private keys**is presented. This algorithms allows to recover the original RSA secret key in polynomial time (w.r.t. the bit length of the modulus) given a noisy copy, i.e. given a copy very every individual bit is independently flipped with (unknown) p[...]