The foundation of lattice cryptography rests mostly on two average-case problems: the Short Integer Solution (SIS) problem and the Learning with Errors (LWE) problem. Both problems admit a standard formulation, and a much more efficient “ring” version. Connections between these problems and the worst case complexity of lattice problems are established in the following papers.
Worst-Case to Average-Case Reductions Based on Gaussian Measures
(Micciancio & Regev - SIAM J. Computing 2007/STOC)
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions (Micciancio - Computational Complexity 2007/FOCS 2002)
On lattices, learning with errors, random linear codes, and cryptography
(Regev - J. ACM 2009/STOC 2005)
On Ideal Lattices and Learning with Errors over Rings
(Lyubashevsky, Peikert & Regev - J. ACM 2013/EuroCrypt 2010)
The first worst-case to average-case connection was proved by Ajtai (STOC 1996) for the SIS problem. This has been improved in a number of papers, leading to (1), which is essentially the best known connection known to date. The LWE problem is an injective version of SIS, and it was first connected to worst case lattice problems in (3). The first foundational results for structured versions of these problems (RingSIS and RingLWE) were proved in (2) and (4). These results have been further extended in several papers.
Generalized Compact Knapsacks Are Collision Resistant
(Micciancio & Lyubashevsky - ICALP 2006)
A Toolkit for Ring-LWE Cryptography
(Lyubashevsky, Peikert & Regev - EuroCrypt 2013)
Classical Hardness of Learning with Errors
(Brakerski, Langlois, Peikert, Regev & Stehle - STOC 2013)
Worst-case to average-case reductions for module lattices
(Langlois & Stehle - Des. Codes Cryptography 2015)
Large Modulus Ring-LWE ≥ Module-LWE
(Albrecht & Deo - AsiaCrypt 2017)
On the Gaussian measure over lattices (Stephens-Davidowits - PhD Thesis, NYU 2017)