Daniele Micciancio: Publications


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). DOI, pdf.

  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). DOI, pdf.
    [Preliminary version in FOCS 1998, Machtey Award for best student paper.]

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

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

  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). DOI, pdf.
    [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). pdf.
    [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). DOI, pdf
    [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). DOI, pdf.
    [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). DOI, pdf.
    [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). DOI, pdf.
    [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). DOI, pdf.
    [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). DOI, pdf.
    [Preliminary version in Eurocrypt 2004.]

  13. D. Micciancio
    The RSA group is pseudo-free
    J. of Cryptology 23(2):169-186 (April 2010). DOI, pdf.
    [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. 42(3):1364-1391 (2013). DOI, ECCC 2010/014, slides.
    [Invited paper, special issue on STOC 2010]


Conference Papers


  1. G. Levi, D. Micciancio  Analysis of Pure PROLOG Programs
    GULP-PRODE 1995, pp. 521-532 (1995).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  45. 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). doi,
    Slides from Barriers II workshop talk.
    [Journal version in SICOMP 2013.]

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

  47. D. Micciancio
    The Geometry of Lattice Cryptography
    FOSAD 2011 (Bertinoro, Italy. August 2011.) Springer LNCS 6858, pp. 185-210. doi.

  48. D. Micciancio, C. Peikert
    Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
    Eurocrypt 2012 (Cambridge, UK. April 2012.) Springer LNCS 7237, pp. 700-718. doi.
    [Invited to J. Cryptology]

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

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

  51. D. Micciancio, C. Peikert
    Hardness of SIS and LWE with Small Parameters
    Crypto 2013 (Santa Barbara, CA, USA. August 2013.) Springer LNCS 8042, pp. 21-39. doi.
    [Invited to J. Cryptology.]

  52. D. Micciancio
    Locally Dense Codes
    CCC 2014 (Vancouver, BC, Canada. June 2014.) doi

  53. L. Ducas, D. Micciancio
    Improved Short Lattice Signatures in the Standard Model
    CRYPTO 2014 (Santa Barbara, CA, USA. August 2014.) Springer LNCS 8616, pp. 335-352. doi

  54. D. Micciancio, M. Walter
    Fast Lattice Point Enumeration with Minimal Overhead
    SODA 2015 (to appear)


Manuscripts

  1. D. Micciancio
    [Pseudo-randomness and partial information in symbolic security analysis]
    IACR Cryptology ePrint Archive 2009/249

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)