Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
Henry Cohn, Nadia Heninger · Advances in Mathematics of Communications · 2015
We develop a framework for solving polynomial equations with sizeconstraints on solutions. We obtain our results by showing how to apply atechnique of Coppersmith for finding small solutions of polynomialequations modulo integers to analogous problems over polynomial rings,number fields, and function fields. This gives us a unified view of severalproblems arising naturally in cryptography, coding theory, and the study oflattices. We give (1) a polynomial-time algorithm for finding smallsolutions of polynomial equations modulo ideals over algebraic numberfields, (2) a faster variant of the Guruswami-Sudan algorithm for listdecoding of Reed-Solomon codes, and (3) an algorithm for list decoding ofalgebraic-geometric codes that handles both single-point and multi-pointcodes. Coppersmith's algorithm uses lattice basis reduction to find ashort vector in a carefully constructed lattice; powerful analogies fromalgebraic number theory allow us to identify the appropriate analogue of alattice in each application and provide efficient algorithms to find asuitably short vector, thus allowing us to give completely parallel proofsof the above theorems.