{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:04:50Z","timestamp":1784199890076,"version":"3.55.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":3,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2216987, CCF-1919197, CCF-1908504"],"award-info":[{"award-number":["CCF-2216987, CCF-1919197, CCF-1908504"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>\n                    Fully Homomorphic Encryption (FHE) is a cryptographic technique that enables privacy-preserving computation. State-of-the-art Boolean FHE implementations provide a very low-level interface, usually exposing a limited set of Boolean gates that programmers must use to write their FHE applications. This programming model is unnecessarily restrictive: many Boolean FHE schemes support\n                    <jats:italic toggle=\"yes\">programmable bootstrapping<\/jats:italic>\n                    , an operation that allows evaluation of an arbitrary fixed-size lookup table. However, most modern FHE compilers are only capable of reasoning about traditional Boolean circuits, and therefore struggle to take full advantage of programmable bootstrapping.\n                  <\/jats:p>\n                  <jats:p>\n                    We present COATL, an FHE compiler that makes use of programmable bootstrapping to produce circuits that are smaller and more efficient than their traditional Boolean counterparts. COATL generates circuits using\n                    <jats:italic toggle=\"yes\">arithmetic lookup tables<\/jats:italic>\n                    , a novel abstraction we introduce for reasoning about computations in Boolean FHE programs. We demonstrate on a variety of benchmarks that COATL can generate circuits that run up to 1.5\u00d7 faster than those generated by other state-of-the-art compilation strategies.\n                  <\/jats:p>","DOI":"10.1145\/3729258","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"301-323","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Circuit Optimization using Arithmetic Table Lookups"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6660-6609","authenticated-orcid":false,"given":"Raghav","family":"Malik","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3411-4634","authenticated-orcid":false,"given":"Vedant","family":"Paranjape","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6827-345X","authenticated-orcid":false,"given":"Milind","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54807-9_8"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338469.3358945"},{"key":"e_1_3_2_4_2","unstructured":"Ahmad Al Badawi Andreea Alexandru Jack Bates Flavio Bergamaschi David Bruce Cousins Saroja Erabelli Nicholas Genise Shai Halevi Hamish Hunt Andrey Kim Yongwoo Lee Zeyu Liu Daniele Micciancio Carlo Pascoe Yuriy Polyakov Ian Quah Saraswathy R.V. Kurt Rohloff Jonathan Saylor Dmitriy Suponitsky Matthew Triplett Vinod Vaikuntanathan and Vincent Zucca. 2022. OpenFHE: Open-SourceFullyHomomorphicEncryptionLibrary. Cryptology ePrint Archive Paper 2022\/915. https:\/\/eprint.iacr.org\/2022\/915 https:\/\/eprint.iacr.org\/2022\/915."},{"key":"e_1_3_2_5_2","unstructured":"Fattaneh Bayatbabolghani Marina Blanton Mehrdad Aliasgari and Michael T. Goodrich. 2017. Secure Fingerprint Alignment and Matching Protocols. CoRR abs\/1702.03379 (2017). arXiv:1702.03379 http:\/\/arxiv.org\/abs\/1702.03379"},{"key":"e_1_3_2_6_2","unstructured":"Marina Blanton Ahreum Kang and Chen Yuan. 2019. Improved Building Blocks for Secure Multi-Party Computation based on Secret Sharing with Honest Majority. Cryptology ePrint Archive Paper 2019\/718. https:\/\/eprint.iacr.org\/2019\/718 https:\/\/eprint.iacr.org\/2019\/718."},{"key":"e_1_3_2_7_2","unstructured":"Fabien Boemer Karl Tarbe and Rehan Rishi. 2024. Announcing Swift Homomorphic Encryption. https:\/\/www.swift.org\/blog\/announcing-swift-homomorphic-encryption\/"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2732516.2732520"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","unstructured":"Hao Chen Zhicong Huang Kim Laine and Peter Rindal. 2018. Labeled PSI from Fully Homomorphic Encryption with Malicious Security. Cryptology ePrint Archive Paper 2018\/787. doi:10.1145\/3243734.3243836","DOI":"10.1145\/3243734.3243836"},{"key":"e_1_3_2_10_2","article-title":"Fast Private Set Intersection from Homomorphic Encryption","author":"Chen Hao","year":"2017","unstructured":"Hao Chen, Kim Laine, and Peter Rindal. 2017. Fast Private Set Intersection from Homomorphic Encryption. Cryptology ePrint Archive, Paper 2017\/299. https:\/\/eprint.iacr.org\/2017\/299","journal-title":"Cryptology ePrint Archive"},{"key":"e_1_3_2_11_2","unstructured":"Ilaria Chillotti Nicolas Gama Mariya Georgieva and Malika Izabach\u00e8ne. August 2016. TFHE: Fast Fully Homomorphic Encryption Library. https:\/\/tfhe.github.io\/tfhe\/."},{"key":"e_1_3_2_12_2","unstructured":"HEIR Contributors. 2023. HEIR: Homomorphic Encryption Intermediate Representation. https:\/\/github.com\/google\/heir."},{"key":"e_1_3_2_13_2","unstructured":"XLS Contributors. 2024. XLS: Accelerated HW Synthesis. https:\/\/github.com\/google\/xls."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454050"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243828"},{"key":"e_1_3_2_16_2","volume-title":"A Fully Homomorphic Encryption Scheme. Ph. D. Dissertation","author":"Gentry Craig","year":"2009","unstructured":"Craig Gentry. 2009. A Fully Homomorphic Encryption Scheme. Ph. D. Dissertation. Stanford, CA, USA. Advisor(s) Boneh, Dan. AAI3382729."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30057-8_1"},{"key":"e_1_3_2_18_2","unstructured":"Shruthi Gorantala Rob Springer Sean Purser-Haskell William Lam Royce Wilson Asra Ali Eric P. Astor Itai Zukerman Sam Ruth Christoph Dibak Phillipp Schoppmann Sasha Kulankhina Alain Forget David Marn Cameron Tew Rafael Misoczki Bernat Guillen Xinyu Ye Dennis Kraft Damien Desfontaines Aishe Krishnamurthy Miguel Guevara Irippuge Milinda Perera Yurii Sushko and Bryant Gipson. 2021. A General Purpose Transpiler for Fully Homomorphic Encryption. Cryptology ePrint Archive Paper 2021\/811. https:\/\/eprint.iacr.org\/2021\/811 https:\/\/eprint.iacr.org\/2021\/811."},{"key":"e_1_3_2_19_2","unstructured":"Charles Gouert Vinu Joseph Steven Dalton Cedric Augonnet Michael Garland and Nektarios Georgios Tsoutsos. 2023. Accelerated Encrypted Execution of General-Purpose Applications. Cryptology ePrint Archive Paper 2023\/641. https:\/\/eprint.iacr.org\/2023\/641 https:\/\/eprint.iacr.org\/2023\/641."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656382"},{"key":"e_1_3_2_21_2","unstructured":"Chris Lattner and Jacques Pienaar. 2019. MLIR Primer: A Compiler Infrastructure for the End of Moore\u2019s Law."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385996"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","unstructured":"Raghav Malik Vedant Paranjape and Milind Kulkarni. [n. d.]. Circuit Optimization Using Arithmetic Table Lookups (artifact). doi:10.5281\/zenodo.15048490","DOI":"10.5281\/zenodo.15048490"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582016.3582057"},{"key":"e_1_3_2_25_2","unstructured":"Daniele Micciancio and Yuriy Polyakov. 2020. Bootstrapping in FHEW-like Cryptosystems. Cryptology ePrint Archive Paper 2020\/086. https:\/\/eprint.iacr.org\/2020\/086"},{"key":"e_1_3_2_26_2","unstructured":"Alan Mishchenko. 2024. ABC: A System for Sequential Synthesis and Verification. https:\/\/people.eecs.berkeley.edu\/~alanmi\/abc."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192413"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CP.2023.3"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480915"},{"key":"e_1_3_2_30_2","unstructured":"Alexander Viand Patrick Jattke Miro Haller and Anwar Hithnawi. 2023. HECO: Fully Homomorphic Encryption Compiler. arXiv:2202.01649 [cs.CR]"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_2_32_2","unstructured":"Claire Wolf. [n. d.]. Yosys Open SYnthesis Suite. https:\/\/yosyshq.net\/yosys\/."},{"key":"e_1_3_2_33_2","unstructured":"Zama. 2022. Concrete: TFHE Compiler that converts python programs into FHE equivalent. https:\/\/github.com\/zamaai\/concrete."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729258","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:05:10Z","timestamp":1784196310000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":32,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729258"],"URL":"https:\/\/doi.org\/10.1145\/3729258","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}