Lattice-based algorithms are some of the most powerful techniques in cryptanalysis, with broad applications to RSA, elliptic curve cryptography, and post-quantum cryptography, but challenges in improving these algorithms have limited their practical utility. The primary obstacle is understanding and exploiting the geometric structure of generic cryptanalytic lattices; several fast algorithms rely on the predictable lattice structure arising from a particular cryptographic problem, but they are unable to generalize. In this dissertation, I apply the theory of lattice structure to enhance the capabilities of generic lattice-based algorithms and develop fast and practical improvements that efficiently solve a wide array of cryptanalytic problems.

First, I turn to the problem of lattice basis reduction. I develop a method of iteratively compressing the gap between dense sublattices during reduction, resolving an open question of whether it is possible to unify recursive and bit-precision optimizations in a generic lattice reduction algorithm. Second, I explore the lattices which occur when using Coppersmith’s method to find small roots of modular polynomials. By improving the understanding of the sublattice structure, I develop multiple new Coppersmith strategies, resolving an open question of how to automatically build Coppersmith lattices which match the performance of handcrafted constructions. Third, I propose a novel cryptanalytic algorithm which involves implicitly constructing a lattice with a dense, secret sublattice and recovering it with lattice reduction.

This new attack is generically useful; in addition to generalizing and simplifying results for the implicit factorization problem, it dramatically improves a cryptanalytic attack on a real-world system. By carefully handling the possible geometric structures of generic lattices, these new methods merge the capabilities of handcrafted solutions with the usability of generic approaches, paving the way for future progress in cryptanalysis.