Circuit Optimization using Arithmetic Table Lookups
Open Access
- 10 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 301-323
Abstract
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 programmable bootstrapping , 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. 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 arithmetic lookup tables , 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× faster than those generated by other state-of-the-art compilation strategies.Keywords
Funding Information
- National Science Foundation (CCF-2216987, CCF-1919197, CCF-1908504)
This publication has 14 references indexed in Scilit:
- Porcupine: a synthesizing compiler for vectorized homomorphic encryption2021
- egg: Fast and extensible equality saturationProceedings of the ACM on Programming Languages, 2021
- Optimizing homomorphic evaluation circuits by program synthesis and term rewriting2020
- RAMPARTS2019
- Labeled PSI from Fully Homomorphic Encryption with Malicious Security2018
- ALCHEMY2018
- Partial control-flow linearization2018
- Fast Private Set Intersection from Homomorphic Encryption2017
- Armadillo2015
- Equality saturationACM SIGPLAN Notices, 2009