Simulation-Secure Threshold PKE from LWE with Polynomial Modulus
Authors
Daniele Micciancio, Adam Suhl
Daniele Micciancio
UC San Diego, United States
daniele at cs dot ucsd dot edu
daniele at cs dot ucsd dot edu
Abstract
In LWE based cryptosystems, using small (polynomially large) ciphertext modulus improves both efficiency and security. In threshold encryption, one often needs simulation security: the ability to simulate decryption shares without the secret key. Existing lattice-based threshold encryption schemes provide one or the other but not both. Simulation security has seemed to require superpolynomial flooding noise, and the schemes with polynomial modulus use Renyi divergence based analyses that are sufficient for game-based but not simulation security.
In this work, we give the first construction of simulation-secure lattice-based threshold PKE with polynomially large modulus. The construction itself is relatively standard, but we use an improved analysis, proving that when the ciphertext noise and flooding noise are both Gaussian, simulation is possible even with very small flooding noise. Our modulus is small not just asymptotically but also concretely: this technique gives parameters roughly comparable to those of highly optimized non-threshold schemes like FrodoKEM. As part of our proof, we show that LWE remains hard in the presence of some types of leakage; these results and techniques may also be useful in other contexts where noise flooding is used.
References
[ACC+18]
Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. Homomorphic Encryption Security Standard. Technical report, HomomorphicEncryption.org. November 2018.
[AJL+12]
Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 483-501. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_29
[APS15]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. DOI: doi:10.1515/jmc-2015-0016
[ASY22]
Shweta Agrawal, Damien Stehlé, and Anshu Yadav. Round-Optimal Lattice-Based Threshold Signatures, Revisited. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:20, Dagstuhl, Germany. 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ICALP.2022.8
[Ban93]
W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296:625–635, 1993. DOI: 10.1007/BF01445125
[BD10]
Rikke Bendlin and Ivan Damgård. Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems. In Daniele Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings, volume 5978 of Lecture Notes in Computer Science, pages 201-218. 2010. Springer. DOI: 10.1007/978-3-642-11799-2_13
[BD20a]
Zvika Brakerski and Nico Döttling. Hardness of LWE on General Entropic Distributions. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science, pages 551-575. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_19
[BD20b]
Zvika Brakerski and Nico Döttling. Lossiness and Entropic Hardness for Ring-LWE. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part I, volume 12550 of Lecture Notes in Computer Science, pages 1-27. 2020. Springer. DOI: 10.1007/978-3-030-64375-1_1
[BGG+18]
Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold Cryptosystems from Threshold Fully Homomorphic Encryption. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I, volume 10991 of Lecture Notes in Computer Science, pages 565-596. 2018. Springer. DOI: 10.1007/978-3-319-96884-1_19
[BJKL21]
Fabrice Benhamouda, Aayush Jain, Ilan Komargodski, and Huijia Lin. Multiparty Reusable Non-interactive Secure Computation from LWE. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II, volume 12697 of Lecture Notes in Computer Science, pages 724-753. 2021. Springer. DOI: 10.1007/978-3-030-77886-6_25
[BKP13]
Rikke Bendlin, Sara Krehbiel, and Chris Peikert. How to Share a Lattice Trapdoor: Threshold Protocols for Signatures and (H)IBE. In Michael J. Jacobson Jr., Michael E. Locasto, Payman Mohassel, and Reihaneh Safavi-Naini, editors, Applied Cryptography and Network Security - 11th International Conference, ACNS 2013, Banff, AB, Canada, June 25-28, 2013. Proceedings, volume 7954 of Lecture Notes in Computer Science, pages 218–236. 2013. Springer. DOI: 10.1007/978-3-642-38980-1_14
[BP23]
Luís T. A. N. Brandão and René Peralta. NIST First Call for Multi-Party Threshold Schemes (Initial Public Draft). Technical report, National Institute of Standards and Technology. 2023.
[BPMW16]
Florian Bourse, Rafaël Del Pino, Michele Minelli, and Hoeteck Wee. FHE Circuit Privacy Almost for Free. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II, volume 9815 of Lecture Notes in Computer Science, pages 62-89. 2016. Springer. DOI: 10.1007/978-3-662-53008-5_3
[BS23]
Katharina Boudgoust and Peter Scholl. Simple Threshold (Fully Homomorphic) Encryption from LWE with Polynomial Modulus. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part I, volume 14438 of Lecture Notes in Computer Science, pages 371–404. 2023. Springer. DOI: 10.1007/978-981-99-8721-4_12
[CSS+22]
Siddhartha Chowdhury, Sayani Sinha, Animesh Singh, Shubham Mishra, Chandan Chaudhary, Sikhar Patranabis, Pratyay Mukherjee, Ayantika Chatterjee, and Debdeep Mukhopadhyay. Efficient Threshold FHE with Application to Real-Time Systems. IACR Cryptol. ePrint Arch., 2022.
[dCHI+22]
Leo de Castro, Carmit Hazay, Yuval Ishai, Vinod Vaikuntanathan, and Muthu Venkitasubramaniam. Asymptotically Quasi-Optimal Cryptography. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part I, volume 13275 of Lecture Notes in Computer Science, pages 303-334. 2022. Springer. DOI: 10.1007/978-3-031-06944-4_11
[DDK+23]
Morten Dahl, Daniel Demmler, Sarah El Kazdadi, Arthur Meyre, Jean-Baptiste Orfila, Dragos Rotaru, Nigel P. Smart, Samuel Tap, and Michael Walter. Noah's Ark: Efficient Threshold-FHE Using Noise Flooding. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Copenhagen, Denmark, 26 November 2023, pages 35–46. 2023. ACM. DOI: 10.1145/3605759.3625259
[DLN+21]
Julien Devevey, Benoît Libert, Khoa Nguyen, Thomas Peters, and Moti Yung. Non-Interactive CCA2-Secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model Without Pairings. https://eprint.iacr.org/2021/630. Cryptology ePrint Archive, Paper 2021/630. 2021.
[GMPW20]
Nicholas Genise, Daniele Micciancio, Chris Peikert, and Michael Walter. Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, Public-Key Cryptography - PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part I, volume 12110 of Lecture Notes in Computer Science, pages 623–651. 2020. Springer. DOI: 10.1007/978-3-030-45374-9_21
[KLO+19]
Michael Kraitsberg, Yehuda Lindell, Valery Osheter, Nigel P. Smart, and Younes Talibi Alaoui. Adding Distributed Decryption and Key Generation to a Ring-LWE Based CCA Encryption Scheme. In Julian Jang-Jaccard and Fuchun Guo, editors, Information Security and Privacy - 24th Australasian Conference, ACISP 2019, Christchurch, New Zealand, July 3-5, 2019, Proceedings, volume 11547 of Lecture Notes in Computer Science, pages 192-210. 2019. Springer. DOI: 10.1007/978-3-030-21548-4_11
[KLSS23]
Duhyeong Kim, Dongwon Lee, Jinyeong Seo, and Yongsoo Song. Toward Practical Lattice-Based Proof of Knowledge from Hint-MLWE. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V, volume 14085 of Lecture Notes in Computer Science, pages 549–580. 2023. Springer. DOI: 10.1007/978-3-031-38554-4_18
[KM16]
Veronika Kuchta and Olivier Markowitch. Identity-Based Threshold Encryption on Lattices with Application to Searchable Encryption. In Lynn Batten and Gang Li, editors, Applications and Techniques in Information Security - 6th International Conference, ATIS 2016, Cairns, QLD, Australia, October 26-28, 2016, Proceedings, volume 651 of Communications in Computer and Information Science, pages 117–129. 2016. DOI: 10.1007/978-981-10-2741-3_10
[KY16]
Shuichi Katsumata and Shota Yamada. Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II, volume 10032 of Lecture Notes in Computer Science, pages 682–712. 2016. DOI: 10.1007/978-3-662-53890-6_23
[LP11]
Richard Lindner and Chris Peikert. Better Key Sizes (and Attacks) for LWE-Based Encryption. In Aggelos Kiayias, editor, Topics in Cryptology - CT-RSA 2011 - The Cryptographers' Track at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings, volume 6558 of Lecture Notes in Computer Science, pages 319–339. 2011. Springer. DOI: 10.1007/978-3-642-19074-2_21
[LPR10]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 1–23. 2010. Springer. DOI: 10.1007/978-3-642-13190-5_1
[MM11]
Daniele Micciancio and Petros Mol. Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, pages 465–484. 2011. Springer. DOI: 10.1007/978-3-642-22792-9_26
[MR07]
Daniele Micciancio and Oded Regev. Worst-Case to Average-Case Reductions Based on Gaussian Measures. SIAM J. Comput., 37(1):267–302, 2007. DOI: 10.1137/S0097539705447360
[NAB+20]
Michael Naehrig, Erdem Alkim, Joppe Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Valeria Nikolaenko, Christopher Peikert, Ananth Raghunathan, and Douglas Stebila. FrodoKEM. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[Reg09]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1–34:40, 2009. DOI: 10.1145/1568318.1568324
[Shi22]
Sina Shiehian. mrNISC from LWE with Polynomial Modulus. In Clemente Galdi and Stanislaw Jarecki, editors, Security and Cryptography for Networks - 13th International Conference, SCN 2022, Amalfi, Italy, September 12-14, 2022, Proceedings, volume 13409 of Lecture Notes in Computer Science, pages 481-493. 2022. Springer. DOI: 10.1007/978-3-031-14791-3_21
[SRB13]
Kunwar Singh, C. Pandu Rangan, and A. K. Banerjee. Lattice Based Efficient Threshold Public Key Encryption Scheme. J. Wirel. Mob. Networks Ubiquitous Comput. Dependable Appl., 4(4):93–107, 2013. DOI: 10.22667/JOWUA.2013.12.31.093
[SSTX09]
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient Public Key Encryption Based on Ideal Lattices. In Mitsuru Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings, volume 5912 of Lecture Notes in Computer Science, pages 617–635. 2009. Springer. DOI: 10.1007/978-3-642-10366-7_36
PDF
History
Submitted: 2024-07-02
Accepted: 2024-12-03
Published: 2025-01-13
Accepted: 2024-12-03
Published: 2025-01-13
How to cite
Daniele Micciancio and Adam Suhl, Simulation-Secure Threshold PKE from LWE with Polynomial Modulus. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a0zogy4e-.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.