一句话：提出 FHE 编译器 COATL，利用可编程自举与算术查找表优化布尔电路，使生成电路最高快 1.5 倍。
全同态加密（FHE）支持隐私保护计算，但当前布尔 FHE 实现通常只暴露少量布尔门，编程模型受限。尽管许多方案支持可编程自举（programmable bootstrapping），可对任意固定大小查找表求值，现有编译器大多只理解传统布尔电路，难以利用该能力。本文提出 COATL 编译器，并引入算术查找表（arithmetic lookup table）这一抽象，用于在布尔 FHE 程序中推理计算，进而借助可编程自举生成更小更高效的电路。作者在多种基准上评估，COATL 生成的电路相比最先进编译策略最高快 1.5 倍。
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.
@article{paperbot3084,
title = {Circuit Optimization using Arithmetic Table Lookups},
author = {Raghav Malik and Vedant Paranjape and Milind Kulkarni},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729258}
}