Project: Lattice based Cryptography
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
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.
Cryptanalysis
- 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