Multiplicative Depth Reduction for Efficient Homomorphic Encryption

This direction is merged into another direction: homomorphic encryption overhead. Its last version stays readable and citable here.

Version 1 of 127 papers35 conceptsfrozen 2026-10-04

In standard computing, we optimize for the total number of operations. A program that performs 100 additions is generally slower than one that performs 10. However, in the world of Homomorphic Encryption (HE)—where we compute on data while it remains encrypted—this intuition fails.

The fundamental constraint of HE is the noise budget. Every time two ciphertexts are multiplied, the noise within the resulting ciphertext grows. If the noise exceeds a certain threshold, the data becomes unrecoverable upon decryption. To prevent this, researchers use "bootstrapping" to refresh the noise, but this operation is computationally grueling, often taking orders of magnitude longer than the actual calculation.

To make private computation practical, a new design philosophy has emerged: Multiplicative Depth Reduction. Instead of minimizing the total operation count, researchers prioritize shortening the longest sequence of consecutive multiplications. By keeping this "depth" shallow, we can stay within the noise budget, use smaller (and thus faster) cryptographic parameters, and avoid bootstrapping entirely.

The Depth versus Operation Trade-off

In traditional neural network design, we often use deep architectures with many layers to achieve high accuracy. However, Qian Lou and Lei Jiang demonstrate in HEMET that this is counterproductive for encrypted inference. They found that shallow networks with more total operations are often significantly faster than deep networks with fewer operations.

This is because the multiplicative depth determines the size of the encryption parameters. A shallower circuit allows for a smaller ciphertext modulus, which accelerates every single addition and multiplication in the network. As Andrew Trask and colleagues note in Syft 0.5, reducing the number of layers processed via HE allows for smaller polynomial moduli, lowering both computational latency and network bandwidth.

Restructuring Algorithms for Logarithmic Depth

A common strategy for reducing depth is moving from linear to logarithmic complexity. In Non-Interactive Private Decision Tree Evaluation, Anselme Tueno and Florian Kerschbaum apply a divide-and-conquer approach to path evaluation. By restructuring how the tree is traversed, they reduced the multiplicative depth from linear to logarithmic relative to the tree depth, enabling the evaluation of complex trees in seconds.

Similarly, in the realm of verifiable computation, Xinxuan Zhang and Zeyu Liu 0004 developed Phalanx. They achieved a 7x–24x speedup by restructuring the sumcheck protocol to use direct linear combinations rather than sequential rounds, slashing the depth required to generate proofs inside an encrypted environment.

Approximating Complex Functions

HE natively supports only addition and multiplication. Complex functions like comparisons ($x < y$), activations (ReLU), or square roots must be approximated using polynomials. The challenge is that high-accuracy approximations usually require high-degree polynomials, which translate to high multiplicative depth.

Researchers have found several ways to bypass this:

  • Composite Polynomials: Dongwoo Kim and Duhyeong Kim show in Efficient Homomorphic Comparison Methods with Optimal Complexity that composing several low-degree polynomials is much more depth-efficient than using one large polynomial.
  • Probabilistic Relaxations: In Secure k-ish Nearest Neighbors Classifier, Hayim Shaul and Dan Feldman trade exactness for speed. By approximating the "k" in k-NN, they decoupled the circuit depth from the database size, reducing computation time from weeks to hours.
  • Alternative Primitives: The CutMax algorithm, developed by Itamar Zimerman and colleagues, replaces comparison-heavy operations in LLMs with "polynomial stretching." They found that inverse square roots are computationally shallower and more efficient than approximating sign functions for comparisons.

Compiler and Architecture Level Optimizations

Beyond individual algorithms, the "depth-first" mindset is being integrated into compilers and automated frameworks. nGraph-HE, developed by Fabian Boemer and Casimir Wierzynski, automatically folds batch normalization layers into model weights. This simple algebraic shift removes an entire layer of multiplications from the live inference path.

For more complex models, AutoFHE by Vishnu Naresh Boddeti uses multi-objective search to find the optimal balance between polynomial degree and bootstrapping placement. By aligning the computational depth with the available noise budget, it reduces latency by 1.8x.

This shift in focus—from counting operations to measuring depth—is what allows Linhan Yang and the team behind encrypted DASHformer to run entire Transformer inferences within the noise budget of a leveled HE scheme. By reordering layers and optimizing matrix multiplications specifically for depth, they eliminate the need for bootstrapping, proving that privacy-preserving machine learning can be both secure and performant.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multiplicative_depth_reduction_for_effic_36043b91,
  title = {Multiplicative Depth Reduction for Efficient Homomorphic Encryption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiplicative-depth-reduction-for-efficient-homomorphic-encryption/rdr_36043b91957d4bebb2b7defafa43e37d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_multiplicative_depth_reduction_for_effic_36043b91_v1,
  title = {Multiplicative Depth Reduction for Efficient Homomorphic Encryption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multiplicative-depth-reduction-for-efficient-homomorphic-encryption/rdr_36043b91957d4bebb2b7defafa43e37d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}