Daniele Micciancio: Publications

• Journal papers and Books
• Conference papers
• Manuscripts
• Other

Journal papers and Books

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19. 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).
    
    [Invited paper, special issue on STOC 2010]

20. V. Lyubashevsky, D. Micciancio
    Asymptotically efficient lattice-based digital signatures
    J. Cryptology (2018).
    
    [Preliminary version in TCC 2008.]

21. D. Micciancio
    On the Hardness of Learning With Errors with Binary Secrets
    Theory of Computing, 14(13), 2018.
    

22. M. Kim, Y. Song, B. Li, D. Micciancio
    Semi-parallel Logistic Regression for GWAS on Encrypted Data
    BMC Medical Genomics 13(99), 2020
    First place at iDASH 2018 Track 2 (Homomorphic Encryption) competition.
    

23. D. Micciancio
    Interactive Proofs for Lattice Problems
    In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, O. Goldreich (ed.), pp. 565-597, ACM Books 2019
    

24. Geva, Gusev, Polyakov, Liram, Rosolio, Alexandru, Genise, Blatt, Duchin, Waissengreen, Mirelman, Bukstein, Blumenthal, Wolf, Pelles, Shaffer, Lavi, Micciancio, Vaikuntanathan, Al Badawi & Goldwasser
    Collaborative Privacy-Preserving Analysis of Oncological Data using Multiparty Homomorphic Encryption
    PNAS, 2023

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 algorithms: 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
   IEEE Symposium on Foundations of Computer Science - FOCS 1998, Palo Also, CA, USA, pp. 92-98 (Nov. 1998)
   
   Macthey Award for Best Student Paper
   Journal version in SIAM J. Comp.

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)
   
   Abstract in ISIT 2000, Sorrento, Italy. pp. 252 (June 2000)
   Journal version in IEEE Trans. on IT

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

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

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

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

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

19. 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)
    
    Journal version in Computational Complexity

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)
    
    Journal version in IEEE/ACM Trans. on Networking

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)
    
    Journal version in Computational Complexity

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)
    
    Journal version in SIAM J. Comp.

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)
    
    Journal version in J. Cryptology 2010

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).
    
    Journal version in J. Cryptology 2018.

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. July 2008) Springer LNCS 5134, pp. 24-43.
    

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

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

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

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).
    
    [Journal version in SIAM J. Comp. 2013.]

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

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

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

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.
    
    

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

50. 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.
    
    [Invited to J. Cryptology.]

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

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

53. D. Micciancio, M. Walter
    Fast Lattice Point Enumeration with Minimal Overhead
    SODA 2015 (San Diego, CA, USA, January 2015)
    

54. L. Ducas, D. Micciancio
    FHEW: Bootstrapping Homomorphic Encryption in less than a second
    Eurocrypt 2015 (Sofia, Bulgaria, April 2015)
    

55. D. Micciancio, M. Walter
    Practical, Predictable Lattice Basis Reduction
    Eurocrypt 2016 (Vienna, Austria, May 2016)
    

56. B. Li, D. Micciancio
    Compactness vs Collusion Resistance in Functional Encryption
    TCC 2016 (Beijing, China, October 2016)
    

57. J. Buchmann, N. Büscher, F. Göpfert, S. Katzenbeisser, J. Krämer, D. Micciancio, S. Siim, C. van Vredendaal, M. Walter
    Creating Cryptographic Challenges Using Multi-Party Computation: The LWE Challenge.
    AsiaPKC@AsiaCCS 2016 (Xi’an, China, May 2016)
    

58. D. Micciancio, M. Walter
    Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time
    Crypto 2017 (Santa Barbara, CA, USA, August 2017)
    

59. B. Li, D. Micciancio
    Equational Security Proofs of Oblivious Transfer Protocols
    PKC 2018 (Rio de Janeiro, Brazil, March 2018.)
    

60. N. Genise, D. Micciancio
    Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus
    Eurocrypt 2018 (Tel Aviv, Israel, April 2018.)
    
    

61. D. Micciancio, M. Walter. On the Bit Security of Cryptographic Primitives
    Eurocrypt 2018 (Tel Aviv, Israel, April 2018.)
    

62. B. Li, D. Micciancio
    Symbolic Security of Garbled Circuits
    CSF 2018 (Oxford, UK. July 2018.)
    

63. D. Micciancio, J. Sorrell
    Ring packing and amortized FHEW bootstrapping
    ICALP 2018 (Prague, Czech Republic. July 2018.)
    

64. N. Genise, D. Micciancio, Y. Polyakov
    Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More
    Eurocrypt 2019 (Darmstadt, Germany. May 2019)
    

65. D. Micciancio
    Symbolic Encryption with Pseudorandom Keys
    Eurocrypt 2019 (Darmstadt, Germany. May 2019)
    

66. N. Genise, C. Gentry, S. Halevi, B. Li, D. Micciancio
    Homomorphic Encryption for Finite Automata
    Asiacrypt 2019 (Kobe, Japan)
    

67. N. Genise, D. Micciancio, C. Peikert and M. Walters
    Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
    PKC 2020
    

68. J. Sorrell and D. Micciancio
    Simpler Statistically Sender Private Oblivious Transfer from Ideals of Cyclotomic Integers
    Asiacrypt 2020
    

69. C. Chen, N. Genise, D. Micciancio, Y. Polyakov, K. Rohloff
    Implementing Token-Based Obfuscation under (Ring) LWE
    WAHC 2020
    

70. D. Micciancio, Y. Polyakov
    Bootstrapping in FHEW-like Cryptosystems
    WAHC 2021
    

71. B. Li, D. Micciancio
    On the Security of Homomorphic Encryption on Approximate Numbers
    Eurocrypt 2021
    

72. M. Chen, C. Hazay, Y. Ishai, Y. Kashnikov, D. Micciancio, T. Riviere, a. shelat, M. Venkitasubramaniam and R. Wang
    Diogenes: Lightweight Scalable RSA Modulus Generation with a Dishonest Majority
    SSP (Oakland) 2021
    

73. B. Li, D. Micciancio, M. Schultz, J. Sorrell.
    Securing Approximate Homomorphic Encryption using Differential Privacy
    Crypto 2022
    

74. A. Al Badawi, J. Bates, F. Bergamaschi, D. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee, Z. Liu, D. Micciancio, I. Quah, Y. Polyakov, R.V. Saraswathy, K. Rohloff, J. Saylor, D. Suponitsky, M. Triplett, V. Vaikuntanathan, V. Zucca
    OpenFHE: Open-Source Fully Homomorphic Encryption Library
    WAHC@CCS 2022
    

75. Z. Liu, D. Micciancio & Y. Polyakov
    Large-Precision Homomorphic Sign Evaluation using FHEW/TFHE Bootstrapping
    Asiacrypt 2022
    

76. Y. Lee, D. Micciancio, A. Kim, R. Choi, M. Deryabin, J. Eom & D. Yoo
    Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption
    Eurocrypt 2023
    

77. D. Micciancio & M. Schultz
    Error Correction and Ciphertext Quantization in Lattice Cryptography
    Crypto 2023
    

78. G. De Micheli, D. Micciancio, A. Pellet-Mary & N. Tran
    Reductions from Module Lattices to Free Module Lattices, and Application to Dequantizing Module-LLL
    Crypto 2023 (supersedes ePrint 2022/1356)
    

79. G. De Micheli, D. Kim, D. Micciancio & A. Suhl
    Faster Amortized FHEW bootstrapping using Ring Automorphisms
    PKC 2024 (to appear)
    

Manuscripts

1. G. De Micheli & D. Micciancio
   A fully classical LLL algorithm for modules
   IACR ePrint 2022/1356
   

2. M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai & V. Vaikuntanathan
   Homomorphic Encryption Standard
   IACR ePrint 2019/939
   

3. Fully Homomorphic Encryption from the ground up
   Invited talk at Eurocrypt 2019
   

Other

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

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