In standard computing, performance is largely a function of the total number of operations (FLOPs). A deeper neural network or a longer loop is perfectly acceptable as long as the total operation count remains within the hardware's processing capacity.
In Homomorphic Encryption (HE) and Secure Multi-Party Computation (MPC), this intuition breaks down completely. The primary bottleneck is not the total number of operations, but the multiplicative depth—the maximum number of sequential multiplications performed along any computational path.
To understand why, we must look at how encrypted data behaves. As Shiyu Shen 0001 et al. demonstrate in their work on leveled homomorphic encryption (Leveraging GPU in Homomorphic Encryption: Framework Design and Analysis of BFV Variants), ciphertexts accumulate cryptographic noise with each sequential multiplication. To prevent this noise from corrupting the data, the ciphertext modulus must be progressively reduced or initialized at a massive scale.
As Qian Lou points out in HEMET: A Homomorphic-Encryption-Friendly Privacy-Preserving Mobile Neural Network Architecture, deeper architectures require larger encryption parameters to handle this noise growth. These larger parameters drastically slow down every single individual operation across the entire network. Consequently, a circuit with fewer total operations but greater depth can be significantly slower than a wider, shallower circuit with a higher total operation count.
To make secure computation practical, researchers across the field are redesigning algorithms to minimize multiplicative depth through several key strategies.
Logarithmic Restructuring via Divide-and-Conquer
The most direct way to minimize depth is to restructure sequential operations into parallel trees. For instance, computing the product of $N$ numbers sequentially yields a depth of $O(N)$. By restructuring this into a binary tree, the depth drops to $O(\log N)$.
This strategy underpins several domain-specific optimizations:
- Genomic Studies: Wenrui Dai et al. (FORESEE: Fully Outsourced secuRe gEnome Study basEd on homomorphic Encryption) mitigate computational overhead in secure division protocols by structuring sequential multiplications into a binary tree rather than a linear sequence.
- Market Matching: For matrix exponentiation in matching markets, James Hsin-yu Chiang et al. (Securely Computing One-Sided Matching Markets) employ repeated squaring to ensure the multiplicative depth scales logarithmically with the number of participants.
- Decision Trees: When evaluating complex structures like decision trees, Anselme Tueno et al. (Non-Interactive Private Decision Tree Evaluation) apply a divide-and-conquer strategy to the path dependency graph, successfully compressing linear path evaluations into logarithmic depth.
This trade-off is explicitly formalized by Ehud Aharoni et al. (Generating One-Hot Maps under Encryption), who note that system designers must choose between depth-minimized tree structures (which preserve noise budget) and operation-minimized structures (which optimize raw server throughput). In distributed settings like MPC, this restructuring can also happen at the gate level. S. Rasoul Faraji et al. (Trifecta: Faster High-Throughput Three-Party Computation over WAN Using Multi-Fan-In Logic Gates) reduce depth by leveraging multi-fan-in logic gates that process up to eight inputs simultaneously, minimizing the sequential communication layers that cause network latency bottlenecks.
Constant-Weight Encodings for Comparisons
Beyond restructuring arithmetic, researchers have found that changing how data is represented can fundamentally alter the depth of fundamental operations like equality testing ($x == y$) and comparisons ($x < y$). Normally, comparing two $n$-bit integers homomorphically requires a circuit whose depth scales with the total bit-length $n$, as shown by early optimization efforts from Miran Kim et al. (Search-and-compute on Encrypted Data).
To bypass this bit-length bottleneck, Florian Kerschbaum et al. (Constant-weight PIR: Single-round Keyword PIR via Constant-weight Equality Operators) introduce the concept of mapping input values to constant-weight codewords. Because every valid codeword has an identical, fixed number of active bits (the Hamming weight $w$), homomorphic equality circuits can scale their multiplicative depth based entirely on $w$ rather than the total bit-length of the domain.
This insight is extended to high-throughput private set operations by Nils Lukas et al. (PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting), who design equality operators with a logarithmic multiplicative depth relative to the Hamming weight. By restricting the number of sequential multiplications to this fixed weight, the authors significantly reduce noise growth, allowing for smaller ciphertext sizes and faster execution times.
Exponential Degree via Polynomial Composition
Non-linear functions (such as comparison operators or activation functions) cannot be evaluated directly in HE and must be approximated using polynomials. Evaluating a high-degree polynomial normally requires a deep chain of multiplications. However, an elegant mathematical loophole exists: polynomial composition.
Dongwoo Kim et al. (Efficient Homomorphic Comparison Methods with Optimal Complexity) demonstrate that by composing a base polynomial of degree $d$ for $k$ iterations, one can compute a resulting approximation of degree $d^k$. Crucially, the multiplicative depth of this evaluation is proportional only to $k$. This provides an exponential reduction in depth compared to evaluating a standard polynomial of equivalent degree, minimizing noise accumulation in approximate homomorphic encryption schemes.
Other algebraic properties can also be exploited to keep depth low. For instance, Hyung Tae Lee (Efficient Private Comparison Queries over Encrypted Databases using Fully Homomorphic Encryption with Finite Fields) utilizes depth-free automorphisms, such as the Frobenius map, to evaluate comparison polynomials over finite fields without consuming the precious multiplication depth budget.
Algorithmic and Architectural Co-Design
Minimizing depth ultimately requires rethinking high-level algorithm design and neural network architectures. In machine learning, standard optimization techniques must be reframed around the noise budget. For example, Andrey Kim et al. (Logistic regression model training based on the approximate homomorphic encryption) leverage accelerated gradient methods specifically because they reduce the number of iterations needed for convergence, minimizing the total depth of the training circuit.
Even the handling of intermediate noise can be optimized structurally. Itamar Zimerman et al. (Efficient Skip Connections Realization for Secure Inference on Encrypted Data) show that by strategically adding a cryptographically fresh ciphertext from an early layer to a noisy ciphertext from a deeper layer, one can reduce the frequency of expensive noise-clearing procedures.
Similarly, the underlying complexity of maintenance operations can be bounded; Kyoohyung Han et al. (Bootstrapping for Approximate Homomorphic Encryption) demonstrate that the bootstrapping procedure itself can be optimized to scale its complexity relative to the depth of the decryption circuit.
Finally, in non-interactive decision tree evaluation, Rasoul Akhavan Mahdavi et al. (Level Up: Private Non-Interactive Decision Tree Evaluation using Levelled Homomorphic Encryption) substitute multiplicative edge evaluations with additive operations to locate target leaf nodes. This preserves the noise budget for downstream tasks and increases evaluation speed for deep tree structures.
Key Foundational Work
Search-and-compute on Encrypted Data (2014) — contributed 1 concept elements to this direction.
FORESEE: Fully Outsourced secuRe gEnome Study basEd on homomorphic Encryption (2015) — contributed 1 concept elements to this direction.