Circuit Optimization using Arithmetic Table Lookups
summary
COATL is a compiler that replaces low-level Boolean gates with arithmetic lookup tables that index small-modulus ciphertexts and use ILP-synthesized coefficients to pack symmetric functions into tiny lookup tables. The compiler merges gates by asking an ILP solver for expressible coefficient vectors, kernelizes repeated subcircuits (matrix multiply, PIR, set intersection) and emits circuits run on OpenFHE/OpenFHE‑style FHE backends. Results show up to ~50% fewer gates and measured speedups up to 1.5×.
AI-written summary · about
chapters (10)
- 0:00Homomorphic encryption intro
- 3:13FHE circuit challenges
- 5:37CGGI programming model
- 8:07Lookup tables for AND gates
- 10:13Optimal lookup coefficients
- 12:40Merging gates with ILP
- 14:45Circuit size reduction
- 15:49Compiler performance
- 17:11Conclusion and future
- 17:31Q&A: Table size vs performance
related talks
01h 03mBeyond Boolean Circuits in Garbled Circuits
20mHEaaN.MLIR: An Optimizing Compiler for Fast Ring-Based Homomorphic Encryption
21mCut Tracing with E-Graphs for Boolean FHE Circuit Synthesis
19mCryptOpt: Verified Compilation with Randomized Program Search for Cryptographic Primitives
01h 02mObfuscation II
01h 01mCircularity Based IO, Part 1
01h 06mSecure Computation and Low-Complexity Cryptography
26mA Core Calculus for Equational Proofs of Cryptographic Protocols