{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T09:01:55Z","timestamp":1776157315768,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-11-C-0096"],"award-info":[{"award-number":["FA8750-11-C-0096"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-11-2-0225"],"award-info":[{"award-number":["FA8750-11-2-0225"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits of a-priori bounded depth), without Gentry\u2019s bootstrapping procedure.<\/jats:p>\n          <jats:p>\n            Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or Ring LWE (RLWE) problems that have 2\n            <jats:italic>\u03bb<\/jats:italic>\n            security against known attacks. We construct the following.\n          <\/jats:p>\n          <jats:p>\n            (1) A leveled FHE scheme that can evaluate depth-\n            <jats:italic>L<\/jats:italic>\n            arithmetic circuits (composed of fan-in 2 gates) using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03bb<\/jats:italic>\n            .\n            <jats:italic>L<\/jats:italic>\n            3) per-gate computation, quasilinear in the security parameter. Security is based on RLWE for an approximation factor exponential in\n            <jats:italic>L<\/jats:italic>\n            . This construction does not use the bootstrapping procedure.\n          <\/jats:p>\n          <jats:p>\n            (2) A leveled FHE scheme that can evaluate depth-\n            <jats:italic>L<\/jats:italic>\n            arithmetic circuits (composed of fan-in 2 gates) using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03bb<\/jats:italic>\n            2) per-gate computation, which is independent of\n            <jats:italic>L<\/jats:italic>\n            . Security is based on RLWE for quasipolynomial factors. This construction uses bootstrapping as an optimization.\n          <\/jats:p>\n          <jats:p>\n            We obtain similar results for LWE, but with worse performance. All previous (leveled) FHE schemes required a per-gate computation of\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>\u03bb<\/jats:italic>\n            3.5), and all of them relied on subexponential hardness assumptions.\n          <\/jats:p>\n          <jats:p>\n            We introduce a number of further optimizations to our scheme based on the Ring LWE assumption. As an example, for circuits of large width (e.g., where a constant fraction of levels have width\n            <jats:italic>\u03a9<\/jats:italic>\n            (\n            <jats:italic>\u03bb<\/jats:italic>\n            )), we can reduce the per-gate computation of the bootstrapped version to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u03bb<\/jats:italic>\n            ), independent of\n            <jats:italic>L<\/jats:italic>\n            , by batching the bootstrapping operation. At the core of our construction is a new approach for managing the noise in lattice-based ciphertexts, significantly extending the techniques of Brakerski and Vaikuntanathan [2011b].\n          <\/jats:p>","DOI":"10.1145\/2633600","type":"journal-article","created":{"date-parts":[[2014,8,29]],"date-time":"2014-08-29T13:03:31Z","timestamp":1409317411000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1130,"title":["(Leveled) Fully Homomorphic Encryption without Bootstrapping"],"prefix":"10.1145","volume":"6","author":[{"given":"Zvika","family":"Brakerski","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science"}]},{"given":"Craig","family":"Gentry","sequence":"additional","affiliation":[{"name":"IBM Research"}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[{"name":"MIT and University of Toronto"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380857"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30576-7_18"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_50"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033075"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.12"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033074"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.94"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008684.2008697"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32928-9_2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30057-8_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_28"},{"key":"e_1_2_1_15_1","series-title":"Lecture Notes in Computer Science","volume-title":"Smart","author":"Gentry Craig","year":"2012","unstructured":"Craig Gentry , Shai Halevi , and Nigel P . Smart . 2012 d. Homomorphic evaluation of the AES circuit. In Proceedings of the 32nd Annual Cryptology Conference (CRYPTO\u201912). Reihaneh Safavi-Naini and Ran Canetti Eds., Lecture Notes in Computer Science , vol. 7417 , Springer , Berlin, 850--867. Craig Gentry, Shai Halevi, and Nigel P. Smart. 2012d. Homomorphic evaluation of the AES circuit. In Proceedings of the 32nd Annual Cryptology Conference (CRYPTO\u201912). Reihaneh Safavi-Naini and Ran Canetti Eds., Lecture Notes in Computer Science, vol. 7417, Springer, Berlin, 850--867."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881424"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_2_1_18_1","unstructured":"Shai Halevi and Victor Shoup. 2013. HElib: An implementation of homomorphic encryption. https:\/\/github.com\/shaih\/HElib.  Shai Halevi and Victor Shoup. 2013. HElib: An implementation of homomorphic encryption. https:\/\/github.com\/shaih\/HElib."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1760749.1760790"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2046660.2046682"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881423"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0234-9"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806739"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536461"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.26"},{"key":"e_1_2_1_28_1","volume-title":"Dertouzos","author":"Rivest Ron","year":"1978","unstructured":"Ron Rivest , Leonard Adleman , and Michael L . Dertouzos . 1978 . On data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press , Inc., Orlando, FL, 169--180. Ron Rivest, Leonard Adleman, and Michael L. Dertouzos. 1978. On data banks and privacy homomorphisms. In Foundations of Secure Computation. Academic Press, Inc., Orlando, FL, 169--180."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13013-7_25"},{"key":"e_1_2_1_31_1","first-page":"133","article-title":"Fully homomorphic SIMD operations","volume":"2011","author":"Smart Nigel P.","year":"2011","unstructured":"Nigel P. Smart and Frederik Vercauteren . 2011 . Fully homomorphic SIMD operations . IACR Cryptol. ePrint Archive 2011 , 133 . Nigel P. Smart and Frederik Vercauteren. 2011. Fully homomorphic SIMD operations. IACR Cryptol. ePrint Archive 2011, 133.","journal-title":"IACR Cryptol. ePrint Archive"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_22"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_2"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2633600","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2633600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:11Z","timestamp":1750229771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2633600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2633600"],"URL":"https:\/\/doi.org\/10.1145\/2633600","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2013-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}