Daniele Micciancio: Publications

To Appear

  1. D. Micciancio
    Generalized compact knapsaks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions    .
    ECCC Electronic Colloquium on Computational Complexity, TR04-095. [Preliminary version in FOCS 2002.]

  2. D. Micciancio
    The RSA group is pseudo-free
    Advances in Cryptology - Eurocrypt 2005. Aarhus, Denmark. May 2005. LNCS. Springer. To appear.

  3. D. Micciancio, O. Regev
    Worst-case to average-case reductions based on Gaussian measure
    Submitted to SIAM Journal on Computing. [Preliminary version in FOCS 2004.]

  4. A. Hevia, D. Micciancio
    Simultaneous broadcast revisited
    Principles of distributed computing - PODC 2005, Las Vegas, NV, July 2005. To appear.

2005

  1. D. Micciancio, S. Panjwani
    Adaptive security of symbolic encryption
    Theory of cryptography Conference - TCC 2005. Cambridge, MA, USA. February 2005. LNCS 3378, Springer, pp. 169-187.

  2. V. Guruswami, D. Micciancio, O. Regev
    The complexity of the covering radius problem on lattices and codes
    Computational Complexity 14:90-120, 2005. [Invited paper. Preliminary version in CCC 2004]

2004

  1. D. Micciancio, B. Warinschi
    Completeness theorems for the Abadi-Rogaway logic of encrypted expressions
    Journal of Computer Security, 12(1):99-129, 2004. [Invited paper. Preliminary version in WITS 2002]

  2. D. Micciancio, B. Warinschi
    Soundness of Formal Encryption in the presence of Active Adversaries
    Theory of Cryptography Conference - TCC 2004. Cambridge, MA, USA. February 2004. LNCS 2951, Springer, pp. 133-151.

  3. D. Micciancio, S. Panjwani
    Optimal communication complexity of generic multicast key distribution
    Advances in Cryptology - Eurocrypt 2004. Interlaken, Switzerland, May 2004. LNCS , Springer, pp. 153-170.

  4. V. Guruswami, D. Micciancio, O. Regev
    The complexity of the covering radius problem on lattices and codes
    Computational Complexity Conference - CCC 2004. Amherst, MA, USA. June 2004, pp.161-173.

  5. U. Feige, D. Micciancio
    The inapproximability of lattice and coding problems with preprocessing
    Journal of Computer and System Sciences, 69(1):45-67, August 2004. [Invited paper. Preliminary version in CCC 2002.]

  6. D. Micciancio, O. Regev
    Worst-case to average-case reductions based on Gaussian measure
    45th Annual Symposium on Foundations of Computer Science - FOCS 2004. Rome, Italy. Oct. 2004. IEEE, pp. 372-381

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

2003

  1. I. Dumer, D. Micciancio, M. Sudan
    Hardness of approximating the minimum distance of a linear code
    IEEE Transactions on Information Theory, 49 (1):22-37, Jan. 2003. [Preliminary versions in FOCS 1999 and ISIT 2000.]

  2. M. Bellare, D. Micciancio, B. Warinschi
    Foundations of group signatures: formal definition, simplified requirements and a construction based on general assumptions
    Advances in Cryptology - Eurocrypt 2003. Warsaw, Poland, May 2003. LNCS 2656, Springer, pp. 614-629.

  3. D. Micciancio, E. Petrank
    Simulatable commitments and efficient concurrent zero-knowledge
    Advances in Cryptology - Eurocrypt 2003 . Warsaw, Poland, May 2003.LNCS 2656, Springer, pp. 140-159.

  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.

2002

  1. D. Micciancio and S. Goldwasser
    Complexity of Lattice Problems: A Cryptographic Perspective [BOOK]
    The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers. March 2002, 220 pages

  2. A. Hevia, D. Micciancio
    The provable security of Graph-Based One-Time Signatures and extensions to algebraic signature schemes
    Advances in Cryptology - Asiacrypt 2002. Queenstown, New Zealand, Dec 1-5, 2002. LNCS 2501, Springer-Verlag. pp. 379-396

  3. D. Micciancio
    Generalized compact knapsaks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions    .
    43rd Annual Symposium on Foundations of Computer Science - FOCS 2002. Vancouver, BC, Canada, Nov. 16, 2002. IEEE. pp. 356-365

  4. D. Micciancio
    Improved cryptographic hash functions with worst-case/average-case connection.
    Proceedings of the 34th Annual ACM Symposium on Theory of Computing - STOC 2002. May 19-21. Montreal, Canada. pp. 609-618.

  5. U. Feige, D. Micciancio
    The inapproximability of lattice and coding problems with preprocessing.
    Computational Complexity - CCC 2002. May 21-23. Montreal, Canada. pp. 44-52.

  6. T. Malkin, D. Micciancio, S. Miner
    Efficient generic forward-secure signatures with an unbounded number of time periods
    Advances in Cryptology - Eurocrypt 2002. Amsterdam, The Netherlands, April 28-May 2, 2002. LNCS 2332, Springer-Verlag, pp. 400-417.

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

  8. D. Micciancio, B. Warinschi
    Completeness theorems for the Abadi-Rogaway logic of encrypted expressions
    Workshop on Issues in the Theory of Security - WITS 2002. Jan. 12-13. Portland, Oregon.

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

2001

  1. D. Micciancio
    The hardness of the closest vector problem with preprocessing.
    IEEE Transactions on Information Theory, 47 (3):1212-1215, March 2001.

  2. D. Micciancio
    The shortest vector problem is NP-hard to approximate to within some constant
    SIAM Journal on Computing, 30 (6):2008-2035, March 2001.

  3. 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, pp. 231-236.

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

2000

  1. I. Dumer, D. Micciancio, M. Sudan
    Hardness of approximating the minimum distance of a linear code     (Abstract)
    IEEE International Symposium on Information Theory - ISIT 2000, pp. 252. June 25-30, 2000. Sorrento, Italy.

1999

  1. O. Goldreich, D. Micciancio, S. Safra and J.-P. Seifert
    Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
    Information Processing Letters    , 71(2):55-61, 1999.

  2. I. Dumer, D. Micciancio, M. Sudan
    Hardness of approximating the minimum distance of a linear code    ,
    In 40th Annual Symposium on Foundations of Computer Science - FOCS 1999. NewYork, NY, Oct. 17, 1999. IEEE. pp. 475-484.

  3. R. Canetti, J. Garay, D. Micciancio, G. Itkis, M. Naor, B. Pinkas
    Multicast security: A taxonomy and some efficient constructions
    IEEE INFOCOM 1999, pp. 708-716.

1998

  1. R. Gennaro, D. Micciancio, T. Rabin
    An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products
    5th ACM Conference on Computer and Communication Security - CCS 1998, November 1998, San Francisco, CA, USA, pp. 67-72.

  2. D. Micciancio
    The shortest vector problem is NP-hard to approximate to within some constant (Macthey Award)
    39th Annual Symposium on Foundations of Computer Science - FOCS 1998. November 1998, Palo Also, CA, USA, pp. 92-98.

  3. R. Canetti, D. Micciancio, O. Reingold
    Perfectly one-way probabilistic hash functions
    Proceedings of the 30th Annual ACM Symposium on Theory of Computing - STOC 1998. May 1998, Dallas, TX, USA, pp. 131-140.

1997

  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, CA, USA, LNCS 1294, Springer, pp. 277-291.

  2. 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, LNCS 1233, Springer , pp. 163-192.

  3. D. Micciancio
    Oblivious data structures: applications to cryptography    .
    Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing - STOC 1997, May 1997, El Paso, TX, USA, pp. 456-464.