- [Ajt96-STOC] M. Ajtai. “Generating hard instances of lattice problems.” (STOC 1996, ECCC TR96-007)
- One-way functions based on the worst-case hardness of SVP_{poly(n)}, poly(n)-uSVP, and SIVP_{poly(n)}.

- [GGH96-ECCC] O. Goldreich, S. Goldwasser, and S. Halevi. “Collision-free hashing from lattice problems.” (ECCC TR96-042)
- The Ajtai function is collision resistant under the same assumption.

- [CN97-FOCS] J.-Y. Cai and A. Nerurkar. “An improved worst-case to average-case connection for lattice problems.” (FOCS 1997)
- Improving the approximation factor up to O~(n^{4+\epsilon})

- [Cai99-CCC] J.-Y. Cai. “A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor.” (CCC 1999, Discrete Applied Mathematics 2003)
- Improving the approximation factor of the assumption.

- [Mic02-STOC] D. Micciancio. “Improved cryptographic hash functions with worst-case/average-case connection.” (STOC 2002, CCC 2002)
- [Mic04-SIAMJComp] D. Micciancio. “Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor.” (SIAM J. on Comp. 2004)
- Improving the approximation factor up to O~(n^3).

- [MR04-FOCS] D. Micciancio and O. Regev. “Worst-case to average-case reduction based on Gaussian measures.” (FOCS 2004, SIAM J. on Comp. 2007)
- Based on GapSVP, SIVP, CRP, or GDD with approximation factor O~(n).

- [Pei07-CCC] C. Peikert. “Limits on the hardness of lattice problems in l_{p} norms.” (CCC 2007, ECCC 2007)
- Based on GapSVP, SIVP, CRP, or GDD with approximation factor O~(n) in l_p norm.

- [GPV08-STOC] C. Gentry, C. Peikert, and V. Vaikuntanathan. “Trapdoors for hard lattices and new cryptographic constructions.” (STOC 2008, ePrint 2007/432)
- Slightly tighter reduction. The parameter q can be set to O~(n).

- [Mic02-FOCS] D. Micciancio. “Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions.” (FOCS 2002, Computational Complexity, Vol. 16, No. 4, 2007)
- One-way functions based on Cyclic-SVP with approximation factor O~(n^3). In the newer version, with approximation factor O~(n)

- [PR06-TCC] C. Peikert and A. Rosen. “Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices” (TCC 2006)
- The variants of M02 is collision resistant under almost same assumption.

- [LM06-ICALP] V. Lyubashevsky and D. Micciancio. “Generalized compact knapsacks are collision resistant.” (ICALP 2006, ECCC 2005)
- Collision-resistant functions based on Ideal-SVP with approximation factor O~(n)

- [LMPR08-FSE] V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen. “SWIFFT: a modest proposal for FFT hashing.” (NIST 2nd Hash Workshop, FSE 2008)
- [ADL+08] Y. Arbitman, G. Dogon, V. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen “SWIFFTX: A Proposal for the SHA-3 Standard.”
- [BL09-INDOCRYPT] J. Buchmann and R. Lindner. “Secure Parameters for SWIFFT.” (INDOCRYPT 2009, http://eprint.iacr.org/2008/493)

- [SS10-EC] Damien StehlĂ©, Ron Steinfeld: Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. EUROCRYPT 2011

Last-modified: 2012-07-18 (Wed) 04:11:16 (3221d)