USENIX Security2025Top-tier venue
Efficient Batchable Secure Outsourced Computation: Depth-Aware Arithmetization of Common Primitives for BFV & BGV
Jelle Vos, Mauro Conti, Zekeriya Erkin
Abstract
Homomorphic encryption enables secure outsourced computation, in which computations on sensitive data can be confidentially outsourced to another party. Homomorphic encryption cryptographically guarantees confidentiality while allowing an evaluator to manipulate the encrypted data using additions and multiplications. However, a remaining challenge is to translate complex computations into efficient circuits consisting of only additions and multiplications. We refer to this problem as arithmetization. The objective in arithmetization has typically been to minimize the number of multiplications (multiplicative size), as multiplications in most secure computation techniques are significantly more expensive than additions. However, the multiplicative depth of a circuit arguably plays an even more important role in deciding the computational cost: For homomorphic encryption schemes like BFV and BGV, it determines the choice of cryptographic parameters that allow evaluating the circuit without requiring expensive bootstrapping operations. We argue that arithmetization should be treated as a multi-objective minimization problem, in which a trade-off can be made between a circuit's multiplicative size and depth. We present efficient depth-aware arithmetization methods for many primitive operations such as exponentiation, univariate functions, equality checks, comparisons, and ANDs and ORs, which further take into account that squaring can be cheaper than multiplying, and we study how to compose these operations. We show that our circuits can outperform more recent homomorphic encryption schemes like TFHE, which can perform significantly faster homomorphic operations but only on one input at a time by batching several inputs into one ciphertext.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Porcupine: a synthesizing compiler for vectorized homomorphic encryption cites Optimizing homomorphic evaluation circuits by program synthesis and term rewriting
- SoK: Fully Homomorphic Encryption Compilers cites Optimizing homomorphic evaluation circuits by program synthesis and term rewriting
Builds on4
- SoK: Fully Homomorphic Encryption CompilersAlexander Viand, Patrick Jattke, Anwar HithnawiS&P 2021 · 117 citations
- Porcupine: a synthesizing compiler for vectorized homomorphic encryptionMeghan Cowan, Deeksha Dangwal, Armin Alaghi, Caroline Trippel et al.PLDI 2021 · 41 citations
- Optimizing homomorphic evaluation circuits by program synthesis and term rewritingDongKwon Lee, Woosuk Lee, Hakjoo Oh, Kwangkeun YiPLDI 2020 · 30 citations
- SoK: Efficient Design and Implementation of Polynomial Hash Functions over Prime FieldsJean Paul Degabriele, Jan Gilcher, Jérôme Govinden, Kenneth G. PatersonS&P 2024 · 8 citations
Related papers
- New Techniques for Fast and Shallow FHE Bootstrapping and BeyondAayush Jain, Huijia Lin, Zeyu Liu, Sagnik SahaCRYPTO 2026
- Efficient Multi-Key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network InferenceHao Chen, Wei Dai, Miran Kim, Yongsoo SongCCS 2019 · 235 citations
- Efficient Arithmetic-and-Comparison Homomorphic Encryption with Space SwitchingErwin Eko Wahyudi, Yan Solihin, Qian LouS&P 2026
- Coyote: A Compiler for Vectorizing Encrypted Arithmetic CircuitsRaghav Malik, Kabir Sheth, Milind KulkarniASPLOS 2023 · 22 citations
- REFHE: Fully Homomorphic ALUZvika Brakerski, Offir Friedman, Daniel Golan, Alon Gurny et al.EUROCRYPT 2026 · 2 citations
