Daniele Micciancio: Publications

Most recent

  1. Hardness of SIS and LWE with Small Parameters - with C. Peikert, Crypto 2013, to appear. ePrint
  2. An Equational Approach to Secure Multi-Party Computation - with S. Tessaro, ITCS 2013. pdf doi.
  3. Algorithms for the Densest Sub-lattice Problem - with D. Dadush, SODA 2013, pdf
  4. Inapproximability of the Shortest Vector Problem: Toward a deterministic reduction - Theory of Computing 8(22):487-512 (2012). doi ECCC
  5. A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations - with P. Voulgaris, SIAM J. Comput. (2013), special issue on STOC'10, to appear. ECCC Slides
  6. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller - with C. Peikert, Eurocrypt 2012. Invited to special issue of J. Cryptology. doi ePrint

Journal Papers

  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 (July 1999)

  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)
    [Preliminary version in FOCS 1998]

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

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

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

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

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

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

  9. V. Guruswami, D. Micciancio, O. Regev
    The complexity of the covering radius problem
    Computational Complexity, 14(2):90-121 (June 2005).
    [Invited paper. Preliminary version in CCC 2004.]

  10. D. Micciancio, O. Regev
    Worst-case to average-case reductions based on Gaussian measure
    SIAM J. on Computing, 37(1):267-302 (May 2007).
    [Invited paper. Preliminary version in FOCS 2004.]

  11. D. Micciancio
    Generalized compact knapsaks, cyclic lattices, and efficient one-way functions
    Computational Complexity, 16(4):365-411 (Dec. 2007).
    [Invited paper. Preliminary version in FOCS 2002.]

  12. D. Micciancio, S. Panjwani
    Optimal communication complexity of generic multicast key distribution
    IEEE/ACM Transactions on Networking, 16(4):803-813 (Aug. 2008).
    [Preliminary version in Eurocrypt 2004.]

  13. D. Micciancio
    The RSA group is pseudo-free
    J. of Cryptology 23(2):169-186 (April 2010).
    [Preliminary version in Eurocrypt 2005.]

  14. D. Micciancio
    Inapproximability of the Shortest Vector Problem: Toward a deterministic reduction
    Theory of Computing 8(689):487-511 (2012). doi ECCC 2012/020

  15. D. Micciancio, P. Voulgaris
    A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations
    SIAM J. Comput. (2012), STOC'10 special issue, to appear. ECCC 2010/014 Slides
    [Preliminary version in STOC 2010]

Conference Papers

  1. S. Mantaci, D. Micciancio
     An algorithm for the solution of tree equations
    Theory and Practice of Software Development - TAPSOFT 1997. Lille, France. Springer LNCS 1214, pp. 417-428 (Apr. 1997)

  2. M. Bellare, S. Goldwasser, D. Micciancio
     "Pseudo-random" generators within cryptographic applications: the DSS case
    Advances in Cryptology - CRYPTO 1997, Santa Barbara, CA, USA, Springer LNCS 1294, pp. 277-291 (Aug. 1997)

  3. M. Bellare, D. Micciancio
    A new paradigm for collision-free hashing: Incrementality at reduced cost
    Advances in Cryptology - Eurocrypt 1997, Konstanz, Germany, Springer LNCS 1233, pp. 163-192 (May 1997)

  4. D. Micciancio
    Oblivious data structures: applications to cryptography    .
    ACM Symposium on Theory of Computing - STOC 1997, El Paso, TX, USA, pp. 456-464 (May 1997)

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

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

  7. R. Canetti, D. Micciancio, O. Reingold
    Perfectly one-way probabilistic hash functions
    ACM Symposium on Theory of Computing - STOC 1998. Dallas, TX, USA, pp. 131-140 (May 1998)

  8. I. Dumer, D. Micciancio, M. Sudan
    Hardness of approximating the minimum distance of a linear code    ,
    IEEE Symposium on Foundations of Computer Science - FOCS 1999. NewYork, NY, pp. 475-484 (Oct. 1999)

  9. R. Canetti, J. Garay, D. Micciancio, G. Itkis, M. Naor, B. Pinkas
    Multicast security: A taxonomy and some efficient constructions
    IEEE INFOCOM 1999, New York, NY, USA, pp. 708-716 (March 1999)

  10. 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, Sorrento, Italy. pp. 252 (June 2000)

  11. D. Micciancio, B. Warinschi
    A linear space algorithm for computing the Hermite normal form
    International Symposium on Symbolic and Algebraic Computation - ISSAC 2001. London, Canada, pp. 231-236 (July 2001)

  12. D. Micciancio
    Improving Lattice based cryptosystems using the Hermite Normal Form    .
    Cryptography and Lattices Conference - CaLC 2001, Providence, RI. Springer LNCS 2146, pp. 126-145 (March 2001)

  13. 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, Springer LNCS 2501, pp. 379-396 (Dec. 2002)

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

  15. D. Micciancio
    Improved cryptographic hash functions with worst-case/average-case connection.
    ACM Symposium on Theory of Computing - [STOC 2002](http://omega.crm.umontreal.ca/STOC'02/),Montreal, Canada, pp. 609-618 (May 2002)

  16. U. Feige, D. Micciancio
    The inapproximability of lattice and coding problems with preprocessing.
    Computational Complexity Conference - CCC 2002, Montreal, Canada. IEEE, pp. 44-52 (May 2002)

  17. 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. Springer LNCS 2332, pp. 400-417 (April 2002)

  18. R. Gennaro, D. Micciancio
    Cryptanalysis of a pseudorandom generator based on braid groups
    Advances in Cryptology - Eurocrypt 2002. Amsterdam, The Netherlands. Springer LNCS 2332, pp. 1-13 (April 2002)

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

  20. 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. Springer LNCS 2656, pp. 614-629 (May 2003)

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

  22. D. Micciancio, S. Vadhan
    Statistical zero-knowledge proofs with efficient provers: lattice problems and more
    Advances in Cryptology - Crypto 2003. Santa Barbara, CA, USA. Springer LNCS 2729, pp. 282-298 (Aug. 2003)

  23. D. Micciancio, B. Warinschi
    Soundness of formal encryption in the presence of active adversaries
    Theory of Cryptography Conference - TCC 2004. Cambridge, MA, USA. Springer LNCS 2951, pp. 133-151 (Feb. 2004)

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

  25. 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. IEEE, pp.161-173 (June 2004)

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

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

  28. D. Micciancio
    The RSA group is pseudo-free
    Advances in Cryptology - Eurocrypt 2005, Aarhus, Denmark. Springer LNCS 3494, pp. 387-403 (May 2005)

  29. A. Hevia, D. Micciancio
    Simultaneous broadcast revisited
    ACM Symposium on Principles of Distributed Computing - PODC 2005, Las Vegas, NV, pp. 324 - 333 (July 2005)

  30. D. Micciancio, S. J. Ong, A. Sahai, S. Vadhan
    Concurrent Zero Knowledge without Complexity Assumptions
    Theory of Cryptography Conference - TCC 2006, New York, NY. Springer LNCS 3876, pp. 1-20 (March 2006)

  31. V. Lyubashevsky, D. Micciancio
    Generalized compact knapsacks are collision resistant
    International Colloquium on Automata, Languages and Programming - ICALP 2006, Venice, Italy. Springer LNCS 4052, pp. 144-155 (July 2006)

  32. D. Micciancio, S. Panjwani
    Corrupting one vs. corrupting many: the case of broadcast and multicast encryption
    International Colloquium on Automata, Languages and Programming - ICALP 2006, Venice, Italy. Springer LNCS 4052, pp.70-82 (July 2006)

  33. Y.-K. Liu, V. Lyubashevsky, D. Micciancio
    On bounded distance decoding for general lattices
    International Workshop on Randomization and Computation - RANDOM 2006, Barcellona, Spain. Springer LNCS 4110, pp. 450-461 (Aug. 2006)

  34. V. Lyubashevsky, D. Micciancio, C. Peikert, A. Rosen
    Provably secure FFT hashing
    NIST 2nd Cryptogaphic Hash Workshop, Santa Barbara, CA, USA (Aug. 2006)

  35. D. Micciancio
    Efficient reductions among lattice problems
    SODA 2008, San Francisco, CA, USA (January 2008)

  36. V. Lyubashevsky, D. Micciancio, C. Peikert, A. Rosen
    SWIFFT: a modest proposal for FFT hashing
    FSE 2008, Lausanne, Switzerland. Springer LNCS 5086, pp. 54-72 (February 2008)

  37. V. Lyubashevsky, D. Micciancio
    Asymptotically efficient lattice-based digital signatures
    TCC 2008, New York, NY, USA. Springer LNCS 4948, pp. 37-54 (March 2008)

  38. D. Micciancio, S. Yilek
    The round-complexity of black-box zero-knowledge: a combinatorial characterization
    TCC 2008, New York, NY, USA. Springer LNCS 4948, pp. 535-552 (March 2008)

  39. D. Micciancio, A. Nicolosi
    Efficient bounded distance decoders for Barnes-Wall lattices
    IEEE ISIT 2008, Toronto, ON, Canada (July 2008)

  40. A. Hevia, D. Micciancio
    An indistinguishability-based characterization of anonymous channels
    PETS 2008, Leuven, Belgium. Springer LNCS 5134, pp. 24-43 (July 2008)

  41. V. Lyubashevsky, D. Micciancio
    On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
    CRYPTO 2009, Santa Barbara, CA, USA. Springer LNCS 5677, pp. 577-594 (August 2009)

  42. D. Micciancio, P. Voulgaris
    Faster exponential time algorithms for the shortest vector problem
    SODA 2010, Austin, TX, USA, pp. 1468-1480. (January 2010)

  43. D. Micciancio
    Computational soundness, co-induction, and encryption cycles
    Eurocrypt 2010, Nice, France. Springer LNCS 6110 (May 2010)

  44. D. Micciancio, P. Voulgaris
    A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations
    STOC 2010, Cambridge, MA, USA (June 2010).  Slides from Barriers II workshop talk.

  45. D. Micciancio, P. Mol
    Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions CRYPTO 2011
    Santa Barbara, CA, USA. Springer LNCS 6841 (August 2011).

  46. D. Micciancio
    The Geometry of Lattice Cryptography
    FOSAD 2011 (Bertinoro, Italy. August 2011.) Springer LNCS 6858

  47. D. Micciancio, C. Peikert
    Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
    Eurocrypt 2012 (Cambridge, UK. April 2012.) Springer LNCS 7237, pp. 700-718.

  48. D. Micciancio, D. Dadush
    Algorithms for the Densest Sub-lattice Problem
    SODA 2013 (New Orleans, LI, USA. January 2013.) ACM/SIAM, pp. 1103-1122. [link]

  49. D. Micciancio, S. Tessaro
    An Equational Approach to Secure Multi-Party Computation
    ITCS 2013 (Berkeley, CA, USA. January 2013.) ACM, pp. 355-372, [doi]

  50. D. Micciancio, C. Peikert
    Hardness of SIS and LWE with Small Parameters Crypto 2013 (Santa Barbara, CA, USA. August 2013.)

Books and Chapters

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

  2. D. Micciancio
    Closest Vector Problem, Lattice Based Cryptography, Shortest Vector Problem (pp. 79-80, 347-349, 569-570).
    In Encyclopedia of Cryptography and Security, H. C. A. van Tilborg ed. Springer, (2005)

  3. D. Micciancio
    Shortest Vector Problem
    In Encyclopedia of Algorithms, M.-Y. Kao ed. Springer, pp. 841-843 (2008).

  4. D. Micciancio, O. Regev
    Lattice-Based Cryptography
    In Post Quantum Cryptography, D.J. Bernstein; J. Buchmann; E. Dahmen (eds.), pp. 147-191, Springer (February 2009)

  5. D. Micciancio
    Cryptographic functions from worst-case complexity assumptions
    In The LLL Algorithm: Survey and Applications, Springer (December 2009)

  6. D. Micciancio
    The Geometry of Lattice Cryptography
    In FOSAD 2011 (August 2011)