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

- Very hard to break by the adversary, so that even randomly chosen keys are hard to break.
- Easy to compute by the legitimate parties, e.g., those who know a secret key.
- Evaluated against practical cryptanalytic attacks, in order to determine appropriate values of the security parameter

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

*D. Micciancio*

**A note on the minimal volume of almost cubic parallelepipeds**

Discrete and Computational Geometry, 29 (1), .Dec 2002, pp. 133-138.*D. Micciancio*

**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 measureSIAM J. on Computing. To appear. [Invited paper. Preliminary version in FOCS 2004]

*D. Micciancio*

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.*D. Micciancio*.

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.

*M. Bellare, S. Goldwasser, D. Micciancio*

**“Pseudo-random” generators within cryptographic applications: the DSS case**

Advances in Cryptology - CRYPTO 1997, August 17-21, 1997, Santa Barbara, California. Lecture Notes in Computer Science 1294, Springer-Verlag, pp. 277-291.*R. Gennaro, D. Micciancio*

Cryptanalysis of a pseudorandom generator based on braid groups

Advances in Cryptology - Eurocrypt 2002. Amsterdam, The Netherlands, April 28-May 2, 2002. LNCS 2332, Springer-Verlag, pp. 1-13