Approximate Common Divisors via Lattices


March 24, 2014


Nadia Heninger


University of Pennsylvania


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.


Nadia Heninger

My primary research interests are in cryptography and security, with particular interest in cryptography in practice, cryptanalysis, privacy, lattices, computational number theory, and coding theory. I am part of the Security Laboratory and the Theory Group at Penn.

Previously, I was a visiting researcher at Microsoft Research New England in Cambridge, MA, and an NSF mathematical sciences postdoctoral fellow in the Department of Computer Science and Engineering at UC San Diego. I have a Ph.D. in computer science from Princeton University and a B.S. in electrical engineering and computer science from UC Berkeley.