Lune

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

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 onCited byLeft to right by year; the more cited, the higher.

Builds on4

  1. SoK: Fully Homomorphic Encryption CompilersAlexander Viand, Patrick Jattke, Anwar HithnawiS&P 2021 · 117 citations
  2. Porcupine: a synthesizing compiler for vectorized homomorphic encryptionMeghan Cowan, Deeksha Dangwal, Armin Alaghi, Caroline Trippel et al.PLDI 2021 · 41 citations
  3. Optimizing homomorphic evaluation circuits by program synthesis and term rewritingDongKwon Lee, Woosuk Lee, Hakjoo Oh, Kwangkeun YiPLDI 2020 · 30 citations
  4. 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

  1. New Techniques for Fast and Shallow FHE Bootstrapping and BeyondAayush Jain, Huijia Lin, Zeyu Liu, Sagnik SahaCRYPTO 2026
  2. 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
  3. Efficient Arithmetic-and-Comparison Homomorphic Encryption with Space SwitchingErwin Eko Wahyudi, Yan Solihin, Qian LouS&P 2026
  4. Coyote: A Compiler for Vectorizing Encrypted Arithmetic CircuitsRaghav Malik, Kabir Sheth, Milind KulkarniASPLOS 2023 · 22 citations
  5. REFHE: Fully Homomorphic ALUZvika Brakerski, Offir Friedman, Daniel Golan, Alon Gurny et al.EUROCRYPT 2026 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines