Daniele Micciancio: Publications

Most recent

  1. Worst-case to average-case reductions based on Gaussian measure - SIAM J. on Computing 37(1):267-302 (2007).
  2. Generalized compact knapsaks, cyclic lattices, and efficient one-way functions - Computational Complexity 16(4):365-411 (2007).
  3. Cryptographic functions from worst-case complexity assumptions - LLL+25.
  4. Efficient reductions among lattice problems - SODA 2008.
  5. Asymptotically efficient lattice-based digital signatures - TCC 2008
  6. The round-complexity of black-box zero-knowledge: a combinatorial characterization - TCC 2008
  7. SWIFFT: a modest proposal for FFT hashing - FSE 2008
  8. Optimal communication complexity of generic multicast key distribution - IEEE/ACM Trans. on Networking, To appear (2008).
  9. Efficient bounded distance decoders for Barnes-Wall lattices - ISIT 2008.
  10. An indistinguishability-based characterization of anonymous channels - PETS 2008

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 (August 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:90-120 (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 (2007).
    [Invited paper. Preliminary version in FOCS 2004.]

  11. D. Micciancio
    Generalized compact knapsaks, cyclic lattices, and efficient one-way functions
    Computational Complexity, 16:365-411 (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, To appear.
    [Preliminary version in Eurocrypt 2004.]

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,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 (August 2006)

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

  35. D. Micciancio
    Cryptographic functions from worst-case complexity assumptions
    LLL+25, Caen, France (June 2007)

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

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
    In Encyclopedia of Cryptography and Security, H. C. A. van Tilborg ed. Springer, pp. 79-80 (2005)

  3. D. Micciancio
    Shortest Vector Problem
    In Encyclopedia of Cryptography and Security, H. C. A. van Tilborg ed. Springer, pp. 569-570 (2005)

  4. D. Micciancio
    Lattice Based Cryptography
    In Encyclopedia of Cryptography and Security, H. C. A. van Tilborg ed. Springer, pp. 347-349 (2005)

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