index.md

layout
main

Idealcodes

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.

Abstract

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.

Members

• Daniel Augot (leader),
• Johan S. R. Nielsen (post-doc),
• Luca De Feo.

Events

• December 10, 2014, UVSQ. CLIC 2014: Codes, Lattices, Ideals, Cryptography.

Talks

• (December 10, 2014), Fast Decoding of Hermitian Codes Using <script type="math/tex">𝔽[x]</script>-Lattice Basis Reduction, Johan S. R. Nielsen. UVSQ. CLIC 2014.

• (December 10, 2014), Coppersmith's Algorithm, Luca De Feo. UVSQ. CLIC 2014.

Publications