The security of many cryptosystems based on error-correcting codes relies on the hardness of the following problem: given a matrix H, a vector s, and an integer w, find a vector e with at most w nonzero coordinates such that He = s. This is called the syndrome decoding problem. The main objective of this thesis is to propose new algorithms to solve it and to refine the analysis of existing ones.
Many decoding algorithms crucially use a subroutine that solves the nearest neighbor problem. First, we study methods for solving this problem. In particular, we analyze the May–Ozerov algorithm for the nearest neighbor problem to compare it with a more classical algorithm called the projection method. To this end, we establish new bounds on the complexity of these two algorithms that take constant and polynomial factors into account. These results show that the May–Ozerov algorithm is galactic: although its complexity has a better asymptotic exponent than the projection method, it becomes more efficient only for instance sizes that are out of reach in practice. We thus show that using the projection method in information-set decoding algorithms is the better of the two choices.
Second, we study the quasi-abelian syndrome decoding problem, on which the security of several pseudorandom correlation generators relies. We reduce this problem to one of interpolating sparse multivariate polynomials over small finite fields. We then develop new algorithms to solve this interpolation problem. On the one hand, simple methods inspired by an idea of Richard Zippel; on the other hand, a more advanced method based on an embedding into the complex numbers and on compressed sensing. These algorithms enable practical attacks against several proposed parameter sets for the quasi-abelian syndrome decoding problem. In particular, for the aggressive parameters of the F4OLEAGE protocol, our implementation distinguishes the output of the generator from random with an advantage greater than 60% and recovers the entire set of secret polynomials with probability greater than 13%.