Identifying computationally hard problems is only the first step in the construction of secure cryptographic functions. In order to be useful in cryptographic applications, these functions should be
Typcal notions of hardness (e.g., NP-hardness) used in computational complexity, refer to the worst-case instance of a problem: a problem is hard if no algorithm can solve every instance. In cryptography one needs average case hardness, so that even randomly chosen keys are hard to break. One of the features that make lattices so interesting from a cryptographic perspective is that we can build functions that are hard to break on the average, based on the assumtion that lattice problems are hard in the worst-case. The first result of this kind was proved by Ajtai in 1996, who build one-way functions based on the assumption that certain lattice problems are hard to approximate within moderately large polynomial factors n^c (for some c>8).
A note on the minimal volume of almost cubic parallelepipeds
Discrete and Computational Geometry, 29 (1), .Dec 2002, pp. 133-138.
Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor
SIAM Journal on Computing, 34(1):118-169, 2004. (Preliminary versions in STOC 2002 and CCC 2002.)
D. Micciancio, O. Regev
Worst-case to average-case reductions based on Gaussian measure
SIAM J. on Computing. To appear. [Invited paper. Preliminary version in FOCS 2004]
Generalized compact knapsaks, cyclic lattices, and efficient one-way functions
Computational Complexity. To appear. [Invited paper. Preliminary version in FOCS 2002]
V. Lyubashevsky, D. Micciancio
Generalized compact knapsacks are collision resistant
International Colloquium on Automata, Languages and Programming - ICALP 2006, Venice, Italy. To appear.
D. Micciancio, B. Warinschi
A linear space algorithm for computing the Hermite normal form
International Symposium on Symbolic and Algebraic Computation - ISSAC 2001. July 18-21, 2001, London, Canada.
Improving Lattice based cryptosystems using the Hermite Normal Form.
Cryptography and Lattices Conference - CaLC 2001. March 29-30, 2001, Providence, Rhode Island. LNCS 2146, Springer-Verlag, pp. 126-145.
M. Bellare, D. Micciancio
A new paradigm for collision-free hashing: Incrementality at reduced cost
Advances in Cryptology - Eurocrypt 1997. May 11-15, 1997, Konstanz, Germany. Lecture Notes in Computer Science 1233, Springer-Verlag, pp. 163-192.
D. Micciancio, S. Vadhan
Statistical zero-knowledge proofs with efficient provers: lattice problems and more
Advances in Cryptology - Crypto 2003. Santa Barbara, CA, USA, August 2003. LNCS 2729, Springer, pp. 282-298.
Y.-K. Liu, V. Lyubashevsky, D. Micciancio
On bounded distance decoding for general lattices
International Workshop on Randomization and Computation - RANDOM 2006, Barcellona. To appear.