Coppersmith’s Method for Coding Theory and Cryptography

Idealcodes is a two years Digiteo research project, started in October 2014. The partners involved are École Polytechnique (X) and Université de Versailles – Saint-Quentin-en-Yvelines (UVSQ). It funds one post-doc, working at the boundary between coding theory, cryptography and computer algebra.


Idealcodes spans the three research areas of algebraic coding theory, cryptography, and computer algebra, by investigating the problem of lattice reduction (and root-finding). In algebraic coding theory this is found in Guruswami and Sudan’s list decoding of algebraic geometry codes and Reed–Solomon codes. In cryptography, it is found in Coppersmith’s method for finding small roots of integer equations. These topics were unified and generalised by Cohn and Heninger, by considering algebraic geometry codes and number field codes under the deep analogy between polynomials and integers. Sophisticated results in coding theory could be then carried over to cryptanalysis, and vice-versa. The generalized view raises problems of computing efficiently, which is one of the main research topics of Idealcodes.