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

Average-case hardness from worst-case intractability assumptions

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

  1. D. Micciancio
    A note on the minimal volume of almost cubic parallelepipeds
    Discrete and Computational Geometry, 29 (1), .Dec 2002, pp. 133-138.

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

  3. 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]

  4. D. Micciancio
    Generalized compact knapsaks, cyclic lattices, and efficient one-way functions

    Computational Complexity. To appear. [Invited paper. Preliminary version in FOCS 2002]

  5. V. Lyubashevsky, D. Micciancio
    Generalized compact knapsacks are collision resistant
    International Colloquium on Automata, Languages and Programming  - ICALP  2006, Venice, Italy. To  appear.

Algorithms and Cryptographic Applications

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

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

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

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

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

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

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