How the cryptanalysis of RSA is (not so) secretly coding theory
Nadia Heninger
We will look at applications of lattice basis reduction over
the integers and over polynomials. In the realm of the integers,
Coppersmithâ€™s method uses lattice basis reduction to find small roots
of polynomials mod an integer of possibly unknown factorization, a lovely
theorem which has many applications in the cryptanalysis of RSA. In
the realm of the polynomials, it turns out that the analogue of
Coppersmithâ€™s theorem gives exactly Guruswami-Sudan list-decoding of
Reed-Solomon codes. This technique can be extended to more general
number fields and function fields.
Joint work with Henry Cohn