{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T14:37:54Z","timestamp":1781534274037,"version":"3.54.5"},"reference-count":25,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T00:00:00Z","timestamp":1720137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Research Foundation - Flanders, Oddysseus Project","doi-asserted-by":"publisher","award":["GOH9718N"],"award-info":[{"award-number":["GOH9718N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002913","name":"Cyber Security Research Flanders, Flemish Government","doi-asserted-by":"publisher","award":["VR20192203"],"award-info":[{"award-number":["VR20192203"]}],"id":[{"id":"10.13039\/501100002913","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>Multi-key fully homomorphic encryption (MKFHE), a generalization         of fully homomorphic encryption (FHE), enables a computation over encrypted         data under multiple keys. The first MKFHE schemes were based         on the NTRU primitive, however these early NTRU based FHE schemes         were found to be insecure due to the problem of over-stretched         parameters. Recently, in the case of standard (non-multi key) FHE         a secure version, called FINAL, of NTRU has been found. In this work         we extend FINAL to an MKFHE scheme, this allows us to benefit         from some of the performance advantages provided by NTRU based         primitives. Thus, our scheme provides competitive performance against         current state-of-the-art multi-key TFHE, in particular reducing the         computational  complexity from quadratic to linear in the number of         keys.<\/jats:p>","DOI":"10.62056\/aebn-4c2h","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T11:13:33Z","timestamp":1728299613000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":6,"title":["FINALLY: A Multi-Key FHE Scheme Based on NTRU and LWE"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0557-3540","authenticated-orcid":false,"given":"Jeongeun","family":"Park","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05xg72x27","id-type":"ROR","asserted-by":"publisher"}],"name":"Norwegian University of Science and Technology","place":["Trondheim, Norway"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3792-4042","authenticated-orcid":false,"given":"Barry","family":"van Leeuwen","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"KU Leuven","place":["Leuven, Flemish Brabant, 3001, Belgium"],"department":["COSIC, ESAT"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9714-928X","authenticated-orcid":false,"given":"Oliver","family":"Zajonc","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"KU Leuven","place":["Leuven, Flemish Brabant, 3001, Belgium"],"department":["COSIC, ESAT"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:AC:CheChiSon19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-030-34621-8_16","article-title":"Multi-Key Homomorphic Encryption from TFHE","volume":"11922","author":"Hao Chen","year":"2019"},{"key":"ref2:cryptoeprint:2021\/1412","volume-title":"A Unified Framework of Homomorphic Encryption for Multiple\n  Parties with Non-Interactive Setup","author":"Hyesun Kwak","year":"2021"},{"key":"ref3:LTV12","series-title":"STOC '12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1219","DOI":"10.1145\/2213977.2214086","article-title":"On-the-Fly Multiparty Computation on the Cloud via Multikey\n  Fully Homomorphic Encryption","author":"Adriana L\u00f3pez-Alt","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450312455"},{"key":"ref4:C:AlbBaiDuc16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-662-53018-4_6","article-title":"A Subfield Lattice Attack on Overstretched NTRU\n  Assumptions - Cryptanalysis of Some FHE and Graded Encoding Schemes","volume":"9814","author":"Martin R. Albrecht","year":"2016"},{"key":"ref5:CJL16","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1112\/S1461157016000371","article-title":"An algorithm for NTRU problems and cryptanalysis of the GGH\n  multilinear map without a low-level encoding of zero","volume":"19","author":"Jung Hee Cheon","year":"2016","journal-title":"LMS Journal of Computation and Mathematics"},{"key":"ref6:AC:Ducvan21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-92068-5_1","article-title":"NTRU Fatigue: How Stretched is Overstretched?","volume":"13093","author":"L\u00e9o Ducas","year":"2021"},{"key":"ref7:IMA:LeePar19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-030-35199-1_12","article-title":"On the Security of Multikey Homomorphic Encryption","volume":"11929","author":"Hyang-Sook Lee","year":"2019"},{"key":"ref8:cryptoeprint:2022\/347","series-title":"CCS '23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"726","DOI":"10.1145\/3576915.3623176","article-title":"Asymptotically Faster Multi-Key Homomorphic Encryption from\n  Homomorphic Gadget Decomposition","author":"Taechan Kim","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9798400700507"},{"key":"ref9:AC:BIPPS22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-031-22966-4_7","article-title":"FINAL: Faster FHE Instantiated with NTRU and LWE","volume":"13792","author":"Charlotte Bonte","year":"2022"},{"key":"ref10:EC:DucMic15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-662-46800-5_24","article-title":"FHEW: Bootstrapping Homomorphic Encryption in Less Than a\n  Second","volume":"9056","author":"L\u00e9o Ducas","year":"2015"},{"key":"ref11:CCS:CDKS19","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/3319535.3363207","article-title":"Efficient Multi-Key Homomorphic Encryption with Packed\n  Ciphertexts with Application to Oblivious Neural Network Inference","author":"Hao Chen","year":"2019"},{"key":"ref12:aloufi2019collaborative","volume-title":"Collaborative Homomorphic Computation on Data Encrypted\n  under Multiple Keys","author":"Asma Aloufi","year":"2019"},{"key":"ref13:PKC:KwaMinSon24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/978-3-031-57728-4_12","article-title":"Towards Practical Multi-key TFHE: Parallelizable,\n  Key-Compatible, Quasi-linear Complexity","volume":"14604","author":"Hyesun Kwak","year":"2024"},{"key":"ref14:XU2023114026","doi-asserted-by":"publisher","first-page":"114026","DOI":"10.1016\/j.tcs.2023.114026","article-title":"Multi-key fully homomorphic encryption from NTRU and (R)LWE\n  with faster bootstrapping","volume":"968","author":"Kexin Xu","year":"2023","journal-title":"Theoretical Computer Science","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"electronic"},{"key":"ref15:DCC:KimLee23","doi-asserted-by":"publisher","first-page":"2779","DOI":"10.1007\/s10623-023-01233-5","article-title":"A polynomial time algorithm for breaking NTRU encryption\n  with multiple keys","volume":"91","author":"Jiseung Kim","year":"2023","journal-title":"DCC"},{"key":"ref16:ESORICS:AkiKleOne23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-031-50594-2_1","article-title":"A Practical TFHE-Based Multi-Key Homomorphic Encryption\n  with Linear Complexity and Low Noise Growth","volume":"14344","author":"Yavuz Akin","year":"2023"},{"key":"ref17:EC:AJLTVW12","series-title":"LNCS","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"},{"key":"ref18:Park21","doi-asserted-by":"publisher","first-page":"135915","DOI":"10.1109\/ACCESS.2021.3117029","article-title":"Homomorphic Encryption for Multiple Users With Less\n  Communications","volume":"9","author":"Jeongeun Park","year":"2021","journal-title":"IEEE Access"},{"key":"ref19:JC:CGGI20","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/s00145-019-09319-x","article-title":"TFHE: Fast Fully Homomorphic Encryption Over the Torus","volume":"33","author":"Ilaria Chillotti","year":"2020","journal-title":"Journal of Cryptology"},{"key":"ref20:EC:MukWic16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/978-3-662-49896-5_26","article-title":"Two Round Multiparty Computation via Multi-key FHE","volume":"9666","author":"Pratyay Mukherjee","year":"2016"},{"key":"ref21:TCC:PeiShi16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-662-53644-5_9","article-title":"Multi-key FHE from LWE, Revisited","volume":"9986","author":"Chris Peikert","year":"2016"},{"key":"ref22:AC:GuiPerVan23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-981-99-8736-8_1","article-title":"Amortized Bootstrapping Revisited: Simpler,\n  Asymptotically-Faster, Implemented","volume":"14443","author":"Antonio Guimar\u00e3es","year":"2023"},{"key":"ref23:ICALP:MicSor18","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.100","article-title":"Ring Packing and Amortized FHEW Bootstrapping","volume":"107","author":"Daniele Micciancio","year":"2018"},{"key":"ref24:APS15","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":"ref25:EPRINT:KwaMinSon22","volume-title":"Towards Practical Multi-key TFHE: Parallelizable,\n  Key-Compatible, Quasi-linear Complexity","author":"Hyesun Kwak","year":"2022"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T16:28:16Z","timestamp":1733848096000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":25,"URL":"https:\/\/doi.org\/10.62056\/aebn-4c2h","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-47"}}