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