{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T14:31:10Z","timestamp":1781533870113,"version":"3.54.5"},"reference-count":42,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:00:00Z","timestamp":1719878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100014553","name":"Samsung Advanced Institute of Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100014553","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100020304","name":"Intel Labs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100020304","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1936703"],"award-info":[{"award-number":["1936703"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,12,3]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.62056\/a0zogy4e-","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T12:00:52Z","timestamp":1736769652000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":7,"title":["Simulation-Secure Threshold PKE from LWE with Polynomial Modulus"],"prefix":"10.62056","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3323-9985","authenticated-orcid":false,"given":"Daniele","family":"Micciancio","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0168r3w48","id-type":"ROR","asserted-by":"publisher"}],"name":"UC San Diego","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Suhl","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0168r3w48","id-type":"ROR","asserted-by":"publisher"}],"name":"UC San Diego","place":["United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"ref1:DBLP:conf\/eurocrypt\/AsharovJLTVW12","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-29011-4_29","article-title":"Multiparty Computation with Low Communication, Computation\n  and Interaction via Threshold FHE","volume":"7237","author":"Gilad Asharov","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642290107"},{"key":"ref2:NIST-threshold","volume-title":"NIST First Call for Multi-Party Threshold Schemes (Initial\n  Public Draft)","author":"Lu\u00eds T. A. N. Brand\u00e3o","year":"2023"},{"key":"ref3:DBLP:journals\/jacm\/Regev09","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and\n  cryptography","volume":"56","author":"Oded Regev","year":"2009","journal-title":"J. ACM"},{"key":"ref4:DBLP:conf\/tcc\/BendlinD10","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-11799-2_13","article-title":"Threshold Decryption and Zero-Knowledge Proofs for\n  Lattice-Based Cryptosystems","volume":"5978","author":"Rikke Bendlin","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642117985"},{"key":"ref5:DBLP:journals\/iacr\/ChowdhurySSMCPM22","first-page":"1625","article-title":"Efficient Threshold FHE with Application to Real-Time\n  Systems","author":"Siddhartha Chowdhury","year":"2022","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref6:DBLP:journals\/iacr\/BoudgoustS23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-981-99-8721-4_12","article-title":"Simple Threshold (Fully Homomorphic) Encryption from LWE\n  with Polynomial Modulus","volume":"14438","author":"Katharina Boudgoust","year":"2023"},{"key":"ref7:LP11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-19074-2_21","article-title":"Better Key Sizes (and Attacks) for LWE-Based Encryption","volume":"6558","author":"Richard Lindner","year":"2011"},{"key":"ref8:NISTPQC-R3:FrodoKEM20","volume-title":"FrodoKEM","author":"Michael Naehrig","year":"2020"},{"key":"ref9:SSTX09","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-10366-7_36","article-title":"Efficient Public Key Encryption Based on Ideal Lattices","volume":"5912","author":"Damien Stehl\u00e9","year":"2009"},{"key":"ref10:LPR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13190-5_1","article-title":"On Ideal Lattices and Learning with Errors over Rings","volume":"6110","author":"Vadim Lyubashevsky","year":"2010"},{"key":"ref11:KY16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1007\/978-3-662-53890-6_23","article-title":"Partitioning via Non-linear Polynomial Functions: More\n  Compact IBEs from Ideal Lattices and Bilinear Maps","volume":"10032","author":"Shuichi Katsumata","year":"2016"},{"key":"ref12:hintmlwe","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/978-3-031-38554-4_18","article-title":"Toward Practical Lattice-Based Proof of Knowledge from\n  Hint-MLWE","volume":"14085","author":"Duhyeong Kim","year":"2023"},{"key":"ref13:subgaussian","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/978-3-030-45374-9_21","article-title":"Improved Discrete Gaussian and Subgaussian Analysis for\n  Lattice Cryptography","volume":"12110","author":"Nicholas Genise","year":"2020"},{"key":"ref14:DBLP:journals\/jowua\/SinghRB13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.22667\/JOWUA.2013.12.31.093","article-title":"Lattice Based Efficient Threshold Public Key Encryption\n  Scheme","volume":"4","author":"Kunwar Singh","year":"2013","journal-title":"J. Wirel. Mob. Networks Ubiquitous Comput. Dependable\n  Appl."},{"key":"ref15:DBLP:conf\/acns\/BendlinKP13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-642-38980-1_14","article-title":"How to Share a Lattice Trapdoor: Threshold Protocols for\n  Signatures and (H)IBE","volume":"7954","author":"Rikke Bendlin","year":"2013"},{"key":"ref16:DBLP:conf\/atis\/KuchtaM16","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-981-10-2741-3_10","article-title":"Identity-Based Threshold Encryption on Lattices with\n  Application to Searchable Encryption","volume":"651","author":"Veronika Kuchta","year":"2016"},{"key":"ref17:DBLP:journals\/iacr\/DahlDEMORSTW23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/3605759.3625259","article-title":"Noah's Ark: Efficient Threshold-FHE Using Noise Flooding","author":"Morten Dahl","year":"2023"},{"key":"ref18:DBLP:conf\/crypto\/BonehGGJKRS18","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-319-96884-1_19","article-title":"Threshold Cryptosystems from Threshold Fully Homomorphic\n  Encryption","volume":"10991","author":"Dan Boneh","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319968834"},{"key":"ref19:cryptoeprint:2021\/630","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-75245-3_24","volume-title":"Non-Interactive CCA2-Secure Threshold Cryptosystems:\n  Achieving Adaptive Security in the Standard Model Without Pairings","author":"Julien Devevey","year":"2021"},{"key":"ref20:DBLP:conf\/crypto\/BoursePMW16","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-662-53008-5_3","article-title":"FHE Circuit Privacy Almost for Free","volume":"9815","author":"Florian Bourse","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662530078"},{"key":"ref21:DBLP:conf\/tcc\/BrakerskiD20","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-64375-1_1","article-title":"Lossiness and Entropic Hardness for Ring-LWE","volume":"12550","author":"Zvika Brakerski","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030643744"},{"key":"ref22:DBLP:conf\/eurocrypt\/BrakerskiD20","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/978-3-030-45724-2_19","article-title":"Hardness of LWE on General Entropic Distributions","volume":"12106","author":"Zvika Brakerski","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030457235"},{"key":"ref23:DBLP:conf\/eurocrypt\/CastroHIVV22","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-031-06944-4_11","article-title":"Asymptotically Quasi-Optimal Cryptography","volume":"13275","author":"Leo de Castro","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031069437"},{"key":"ref24:DBLP:conf\/acisp\/KraitsbergLOSA19","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-030-21548-4_11","article-title":"Adding Distributed Decryption and Key Generation to a\n  Ring-LWE Based CCA Encryption Scheme","volume":"11547","author":"Michael Kraitsberg","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030215477"},{"key":"ref25:DBLP:conf\/eurocrypt\/Benhamouda0KL21","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1007\/978-3-030-77886-6_25","article-title":"Multiparty Reusable Non-interactive Secure Computation from\n  LWE","volume":"12697","author":"Fabrice Benhamouda","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030778859"},{"key":"ref26:DBLP:conf\/scn\/Shiehian22","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-031-14791-3_21","article-title":"mrNISC from LWE with Polynomial Modulus","volume":"13409","author":"Sina Shiehian","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031147906"},{"key":"ref27:MR07","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","article-title":"Worst-Case to Average-Case Reductions Based on Gaussian\n  Measures","volume":"37","author":"Daniele Micciancio","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref28:Ban93","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/BF01445125","article-title":"New bounds in some transference theorems in the geometry of\n  numbers","volume":"296","author":"W. Banaszczyk","year":"1993","journal-title":"Mathematische Annalen"},{"key":"ref29:MM11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-22792-9_26","article-title":"Pseudorandom Knapsacks and the Sample Complexity of LWE\n  Search-to-Decision Reductions","volume":"6841","author":"Daniele Micciancio","year":"2011"},{"key":"ref30:ASY22","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.8","article-title":"Round-Optimal Lattice-Based Threshold Signatures,\n  Revisited","volume":"229","author":"Shweta Agrawal","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959772358","ISSN":"https:\/\/id.crossref.org\/issn\/1868-8969","issn-type":"electronic"},{"key":"ref31:HomomorphicEncryptionSecurityStandard","volume-title":"Homomorphic Encryption Security Standard","author":"Martin Albrecht","year":"2018"},{"key":"ref32:estimator","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of Learning with Errors","volume":"9","author":"Martin R. Albrecht","year":"2015","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref33:DBLP:conf\/eurocrypt\/2012","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4","volume-title":"Advances in Cryptology - EUROCRYPT 2012 - 31st Annual\n  International Conference on the Theory and Applications of Cryptographic\n  Techniques, Cambridge, UK, April 15-19, 2012. Proceedings","volume":"7237","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642290107"},{"key":"ref34:DBLP:conf\/tcc\/2010","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11799-2","volume-title":"Theory of Cryptography, 7th Theory of Cryptography\n  Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010.\n  Proceedings","volume":"5978","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642117985"},{"key":"ref35:DBLP:conf\/tcc\/2020-1","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64375-1","volume-title":"Theory of Cryptography - 18th International Conference,\n  TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part I","volume":"12550","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030643744"},{"key":"ref36:DBLP:conf\/eurocrypt\/2020-2","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2","volume-title":"Advances in Cryptology - EUROCRYPT 2020 - 39th Annual\n  International Conference on the Theory and Applications of Cryptographic\n  Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II","volume":"12106","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030457235"},{"key":"ref37:DBLP:conf\/crypto\/2018-1","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1","volume-title":"Advances in Cryptology - CRYPTO 2018 - 38th Annual\n  International Cryptology Conference, Santa Barbara, CA, USA, August 19-23,\n  2018, Proceedings, Part I","volume":"10991","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319968834"},{"key":"ref38:DBLP:conf\/eurocrypt\/2022-1","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06944-4","volume-title":"Advances in Cryptology - EUROCRYPT 2022 - 41st Annual\n  International Conference on the Theory and Applications of Cryptographic\n  Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part I","volume":"13275","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031069437"},{"key":"ref39:DBLP:conf\/acisp\/2019","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-21548-4","volume-title":"Information Security and Privacy - 24th Australasian\n  Conference, ACISP 2019, Christchurch, New Zealand, July 3-5, 2019,\n  Proceedings","volume":"11547","year":"2019","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030215477"},{"key":"ref40:DBLP:conf\/scn\/2022","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-14791-3","volume-title":"Security and Cryptography for Networks - 13th International\n  Conference, SCN 2022, Amalfi, Italy, September 12-14, 2022, Proceedings","volume":"13409","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031147906"},{"key":"ref41:DBLP:conf\/eurocrypt\/2021-2","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77886-6","volume-title":"Advances in Cryptology - EUROCRYPT 2021 - 40th Annual\n  International Conference on the Theory and Applications of Cryptographic\n  Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II","volume":"12697","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030778859"},{"key":"ref42:DBLP:conf\/crypto\/2016-2","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5","volume-title":"Advances in Cryptology - CRYPTO 2016 - 36th Annual\n  International Cryptology Conference, Santa Barbara, CA, USA, August 14-18,\n  2016, Proceedings, Part II","volume":"9815","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783662530078"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T12:10:49Z","timestamp":1736770249000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/4\/2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":42,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,1,13]]}},"URL":"https:\/\/doi.org\/10.62056\/a0zogy4e-","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2024-07-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-24"}}