One-Way/Collision-Resistant Hash Functions

Based on General Lattices

• [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).

Based on Cyclic/Ideal Lattices

• [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)

Based on NTRU Lattices

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