Approximate Common Divisors via Lattices

Опубликовано 8 июля 2016, 1:02

Coppersmith's technique using lattices to find small roots of polynomial equations (and Howgrave-Graham's extension to solving equations modulo divisors) have produced many fascinating results, particularly in the cryptanalysis of RSA: low public exponent padding vulnerabilities, low public exponent vulnerabilities, and efficient key recovery from partial information. In this talk, I will discuss generalizations of these results and their applications. Extending these results to multivariate equations informs our understanding of fully homomorphic encryption schemes over the integers. The extension to rings of integers over number fields informs our understanding of learning with errors over ideals. And finally, the analogue of these results for polynomial rings turns out to give new efficient decoding algorithms for decoding families of error-correcting codes, including Reed-Solomon codes, Parvaresh-Vardy codes, and algebraic geometry codes. Joint work with Henry Cohn.