{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T16:34:38Z","timestamp":1788626078473,"version":"build-2803163510"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2022,9,11]],"date-time":"2022-09-11T00:00:00Z","timestamp":1662854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872355"],"award-info":[{"award-number":["61872355"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12026427"],"award-info":[{"award-number":["12026427"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Advanced Manufacturing and Engineering","award":["A19E3b0099"],"award-info":[{"award-number":["A19E3b0099"]}]},{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education","doi-asserted-by":"crossref","award":["MOE2019-T2-2-083"],"award-info":[{"award-number":["MOE2019-T2-2-083"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,12,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Homomorphic Encryption (HE) supports computation on encrypted data without the need to decrypt, enabling secure outsourcing of computing to an untrusted cloud. Motivated by application scenarios where private information is offered by different data owners, Multi-Key Homomorphic Encryption (MKHE) and Threshold Homomorphic Encryption (ThHE) were proposed. Unlike MKHE, ThHE schemes do not require expensive ciphertext extension procedures and are therefore as efficient as their underlying single-key HE schemes. In this work, we propose a novel NTRU-type ThHE scheme which caters to the computation scenarios with pre-defined participants. In addition to inheriting the simplicity of NTRU scheme, our construction has no expensive relinearization and correspondingly no costly evaluation keys. Controlling noise to make it increase linearly and then using a wide key distribution, our scheme is immune to the subfield lattice attacks and its security follows from the hardness of the standard R-LWE problem. Finally, based on the {0,1}-linear secret sharing and noise flooding techniques, we design a single round distributed threshold decryption protocol, where the decryption is able to be completed even when only given a subset (say $t$-out-of-$k$) of partial decryptions. To the best of our knowledge, our construction is the first NTRU-type ThHE scheme.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac126","type":"journal-article","created":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T15:58:03Z","timestamp":1662998283000},"page":"2861-2873","source":"Crossref","is-referenced-by-count":4,"title":["Threshold Homomorphic Encryption From Provably Secure NTRU"],"prefix":"10.1093","volume":"66","author":[{"given":"Kexin","family":"Xu","sequence":"first","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering , CAS, Beijing, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences , Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Hong Meng Tan","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research , A*STAR, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li-Ping","family":"Wang","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Information Security, Institute of Information Engineering , CAS, Beijing, China"},{"name":"School of Cyber Security, University of Chinese Academy of Sciences , Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Khin","family":"Mi Mi Aung","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research , A*STAR, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huaxiong","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Physical and Mathematical Sciences, Nanyang Technological University , Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2022,9,11]]},"reference":[{"key":"2023121811453093600_ref1","first-page":"169","article-title":"On data banks and privacy homomorphisms","volume":"4","author":"Rivest","year":"1978","journal-title":"Foundations of secure computation"},{"key":"2023121811453093600_ref2","volume-title":"A fully homomorphic encryption scheme","author":"Gentry","year":"2009"},{"key":"2023121811453093600_ref3","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1145\/1536414.1536440","volume-title":"Proceedings of the forty-first annual ACM symposium on Theory of computing","author":"Gentry","year":"2009"},{"key":"2023121811453093600_ref4","first-page":"309","volume-title":"Innovations in Theoretical Computer Science","author":"Brakerski","year":"2012"},{"key":"2023121811453093600_ref5","first-page":"868","volume-title":"Annual Cryptology Conference","author":"Brakerski","year":"2012"},{"key":"2023121811453093600_ref6","first-page":"144","article-title":"Somewhat practical fully homomorphic encryption","volume":"2012","author":"Fan","year":"2012","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2023121811453093600_ref7","first-page":"617","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Ducas","year":"2015"},{"key":"2023121811453093600_ref8","first-page":"3","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security","author":"Chillotti","year":"2016"},{"key":"2023121811453093600_ref9","first-page":"377","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security","author":"Chillotti","year":"2017"},{"key":"2023121811453093600_ref10","first-page":"75","volume-title":"Annual Cryptology Conference","author":"Gentry","year":"2013"},{"key":"2023121811453093600_ref11","first-page":"409","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security","author":"Cheon","year":"2017"},{"key":"2023121811453093600_ref12","first-page":"483","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Asharov","year":"2012"},{"key":"2023121811453093600_ref13","first-page":"1219","volume-title":"Proceedings of the forty-fourth annual ACM symposium on Theory of computing","author":"L\u00f3pez-Alt","year":"2012"},{"key":"2023121811453093600_ref14","first-page":"735","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Mukherjee","year":"2016"},{"key":"2023121811453093600_ref15","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/978-3-319-70503-3_20","volume-title":"Theory of Cryptography Conference","author":"Chen","year":"2017"},{"key":"2023121811453093600_ref16","first-page":"446","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security","author":"Chen","year":"2019"},{"key":"2023121811453093600_ref17","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1145\/3319535.3363207","volume-title":"Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security","author":"Chen","year":"2019"},{"key":"2023121811453093600_ref18","doi-asserted-by":"crossref","first-page":"291","DOI":"10.2478\/popets-2021-0071","article-title":"Multiparty homomorphic encryption from ring-learning-with-errors","volume":"2021","author":"Mouchet","year":"2021","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"2023121811453093600_ref19","doi-asserted-by":"crossref","first-page":"135915","DOI":"10.1109\/ACCESS.2021.3117029","article-title":"Homomorphic encryption for multiple users with less communications","volume":"9","author":"Park","year":"2021","journal-title":"IEEE Access"},{"key":"2023121811453093600_ref20","first-page":"325","volume-title":"Cryptographers\u2019 Track at the RSA Conference","author":"Costache","year":"2016"},{"key":"2023121811453093600_ref21","first-page":"241","volume-title":"IACR International Workshop on Public Key Cryptography","author":"Chongchitmate","year":"2017"},{"key":"2023121811453093600_ref22","first-page":"153","volume-title":"Annual International Cryptology Conference","author":"Albrecht","year":"2016"},{"key":"2023121811453093600_ref23","first-page":"3","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Kirchner","year":"2017"},{"key":"2023121811453093600_ref24","first-page":"27","volume-title":"Annual international conference on the theory and applications of cryptographic techniques","author":"Stehl\u00e9","year":"2011"},{"key":"2023121811453093600_ref25","first-page":"565","volume-title":"Annual International Cryptology Conference","author":"Boneh","year":"2018"},{"key":"2023121811453093600_ref26","first-page":"630","volume-title":"Annual Cryptology Conference","author":"Clear","year":"2015"},{"key":"2023121811453093600_ref27","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-3-662-53644-5_9","volume-title":"Theory of Cryptography Conference","author":"Peikert","year":"2016"},{"key":"2023121811453093600_ref28","first-page":"190","volume-title":"Annual International Cryptology Conference","author":"Brakerski","year":"2016"},{"key":"2023121811453093600_ref29","first-page":"1249","article-title":"Two round multiparty computation via multi-key fully homomorphic encryption with faster homomorphic evaluations","volume":"2018","author":"Li","year":"2018","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"2023121811453093600_ref30","doi-asserted-by":"crossref","first-page":"564","DOI":"10.26599\/TST.2019.9010076","article-title":"Modified multi-key fully homomorphic encryption based on ntru cryptosystem without key-switching","volume":"25","author":"Che","year":"2020","journal-title":"Tsinghua Science and Technology"},{"key":"2023121811453093600_ref31","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1515\/jmc-2015-0052","article-title":"Flattening ntru for evaluation key free homomorphic encryption","volume":"14","author":"Dor\u00f6z","year":"2020","journal-title":"Journal of Mathematical Cryptology"},{"key":"2023121811453093600_ref32","first-page":"700","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Micciancio","year":"2012"},{"key":"2023121811453093600_ref33","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/2488608.2488680","volume-title":"Proceedings of the forty-fifth annual ACM symposium on Theory of computing","author":"Brakerski","year":"2013"},{"key":"2023121811453093600_ref34","first-page":"655","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Genise","year":"2019"},{"key":"2023121811453093600_ref35","doi-asserted-by":"crossref","first-page":"17429","DOI":"10.1109\/ACCESS.2021.3053288","article-title":"Efficient lattice gadget decomposition algorithm with bounded uniform distribution","volume":"9","author":"Jeon","year":"2021","journal-title":"Ieee Access"},{"key":"2023121811453093600_ref36","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BFb0054868","volume-title":"International Algorithmic Number Theory Symposium","author":"Hoffstein","year":"1998"},{"key":"2023121811453093600_ref37","first-page":"1","volume-title":"Annual international conference on the theory and applications of cryptographic techniques","author":"Lyubashevsky","year":"2010"},{"key":"2023121811453093600_ref38","first-page":"297","volume-title":"Annual Cryptology Conference","author":"Alperin-Sheriff","year":"2014"},{"key":"2023121811453093600_ref39","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1112\/S1461157016000371","article-title":"An algorithm for ntru problems and cryptanalysis of the ggh multilinear map without a low-level encoding of zero","volume":"19","author":"Cheon","year":"2016","journal-title":"LMS Journal of Computation and Mathematics"},{"key":"2023121811453093600_ref40","first-page":"299","volume-title":"International conference on the theory and applications of cryptographic techniques","author":"Gentry","year":"2002"},{"key":"2023121811453093600_ref41","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/978-3-642-45239-0_4","volume-title":"IMA International Conference on Cryptography and Coding","author":"Bos","year":"2013"},{"key":"2023121811453093600_ref42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2633600","article-title":"(leveled) fully homomorphic encryption without bootstrapping","volume":"6","author":"Brakerski","year":"2014","journal-title":"ACM Transactions on Computation Theory (TOCT)"},{"key":"2023121811453093600_ref43","article-title":"Collaborative homomorphic computation on data encrypted under multiple keys","volume":"abs\/1911.04101","author":"Aloufi","year":"2019","journal-title":"CoRR"},{"key":"2023121811453093600_ref44","first-page":"1821","article-title":"Blindfolded evaluation of random forests with multi-key homomorphic encryption","volume":"18","author":"Aloufi","year":"2021","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"2023121811453093600_ref45","first-page":"1412","article-title":"A unified framework of homomorphic encryption for multiple parties with non-interactive setup","volume":"2021","author":"Kwak","year":"2021","journal-title":"IACR Cryptol. ePrint Arch."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/12\/2861\/54446554\/bxac126.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/12\/2861\/54446554\/bxac126.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T11:46:09Z","timestamp":1702899969000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/12\/2861\/6695522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,11]]},"references-count":45,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,9,11]]},"published-print":{"date-parts":[[2023,12,14]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac126","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,12]]},"published":{"date-parts":[[2022,9,11]]}}}