💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

This paper proposes an optimized multi-input ciphertext multiplication method for Homomorphic Encryption that extends beyond two inputs through reformulated computations, additional evaluation keys, and a multi-level rescaling approach, resulting in hardware architectures that significantly reduce logic area and latency compared to prior designs.

Original authors: Sajjad Akherati, Xinmiao Zhang

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sajjad Akherati, Xinmiao Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef trying to bake a cake, but there's a catch: you must do all the mixing and baking while wearing thick, heavy oven mitts that prevent you from feeling the ingredients or seeing the bowl. This is Homomorphic Encryption (HE). It allows computers to perform math on "encrypted" data (the cake batter in the mitts) without ever decrypting it (taking the mitts off). This keeps secrets safe, whether it's your medical records or your bank balance.

However, doing math with these "mitts" is incredibly slow and messy. The biggest bottleneck is multiplication. In standard encryption, you can only multiply two ingredients at a time. But many modern tasks, like training an AI to recognize a disease or analyzing complex financial trends, require multiplying many ingredients (ciphertexts) together at once.

This paper introduces a new, super-efficient way to multiply these encrypted ingredients, specifically for a popular encryption method called CKKS. Here is the breakdown of their breakthrough using simple analogies:

1. The Problem: The "Messy Kitchen"

When you multiply encrypted numbers, the "noise" (the messiness created by the oven mitts) gets louder and louder. If you multiply too many numbers at once without cleaning up, the noise drowns out the actual data, and the result becomes garbage.

To fix this, the encryption system has to perform a "clean-up" step called Rescaling after every multiplication. Think of this as stopping to wipe the counter and put the ingredients back in order.

The Old Way: If you needed to multiply 10 ingredients, the old method was like a conveyor belt where you multiplied two, stopped to clean, multiplied two more, stopped to clean, and so on. It was slow and required a lot of cleaning supplies (hardware resources).
The Previous "Three-Ingredient" Attempt: The authors' earlier work showed you could multiply three ingredients at once, which was faster. But it still had a lot of unnecessary cleaning steps.

2. The Solution: The "Smart Assembly Line"

The authors propose two major upgrades to make this process faster and smaller:

A. The "One-Step Clean-Up" (Improved 3-Input Multiplication)

In their new design for multiplying three ingredients, they realized they were doing the cleaning (Rescaling) and re-arranging (Relinearization) in a clumsy, roundabout way.

The Analogy: Imagine you have three bowls of batter. The old method was to mix them, pour the mix into a new bowl, clean the old bowls, pour the mix again, and clean again.
The Fix: They redesigned the process so you can mix and clean in one smooth motion. They figured out how to combine the cleaning steps so you don't have to stop and wipe the counter as many times.
The Result: Their new "three-bowl mixer" is 50% faster (latency) and takes up 15% less space on the chip (area) compared to their previous best design.

B. The "Group Cleaning" (Multi-Input Multiplication)

What if you need to multiply four, five, or even twelve ingredients at once?

The Old Way: You would build a long line of "two-bowl mixers." You mix two, clean, mix two more, clean, then mix the results, clean again. This creates a very long line (high "multiplicative depth"), meaning the noise builds up too fast.
The New Strategy: The authors realized that if you group your ingredients differently, you can do a "Group Clean."
- Instead of cleaning after every single step, they developed a mathematical trick (called Multi-Rescaling) that allows you to wait and clean multiple layers of mess at once.
- The Analogy: Imagine you are washing dishes. Instead of washing a plate, drying it, and putting it away, then washing a cup, drying it, and putting it away, you wash a whole stack of dishes, then dry the whole stack, then put them all away. You do the "drying" (the expensive, slow part) only once for the whole group.
The Result: By rearranging how they group the ingredients (the "partitioning"), they can combine these cleaning steps. For multiplying between 4 and 12 ingredients, their new method saves 32% of the space and cuts the time in half (45% faster) compared to the old "two-by-two" line.

3. Why This Matters (According to the Paper)

The paper focuses strictly on the hardware architecture—the physical design of the computer chip that does this math.

They proved that by changing how the math is organized (the algorithm) and how the chip is built (the architecture), you can do complex encrypted math much faster.
They specifically mention that this helps with applications like machine learning, medical diagnosis, and financial analysis, because these fields often require multiplying many encrypted data points together.

Summary

Think of this paper as inventing a new, super-efficient kitchen for a chef who can't take off their oven mitts.

They figured out how to mix three ingredients at once without making a mess.
They invented a way to clean up multiple layers of mess at the same time, rather than one by one.
The result is a kitchen that is smaller, faster, and requires less energy to keep secrets safe while doing complex math.

The authors did not test this on real patients or real bank accounts in this paper; they only proved that the machine designed to do this work is significantly better than the machines we had before.

Technical Summary: Multi-Input Ciphertext Multiplication for Homomorphic Encryption

Problem Statement
Homomorphic encryption (HE), particularly the RNS-CKKS scheme, enables arithmetic operations on encrypted data, which is critical for privacy-preserving applications like machine learning and medical diagnosis. However, standard HE schemes define ciphertext multiplication only for two inputs. Many practical applications, such as high-order polynomial approximations for neural network activation functions (e.g., ReLU), decision trees, and genome sequencing, require the multiplication of multiple ciphertexts ( $n > 2$ ).

Existing approaches to handle multi-input multiplication typically chain multiple two-input multipliers in a binary tree structure. This method suffers from two primary inefficiencies:

High Latency and Area: Sequentially multiplying $n$ ciphertexts using two-input units results in significant hardware overhead and latency.
Noise Growth and Rescaling Overhead: Each multiplication increases the noise level, necessitating a rescaling operation to restore the message scale. In a standard binary tree, rescaling must occur after every multiplication step to prevent exponential noise growth. This results in a large number of rescaling units, each requiring expensive Number Theoretic Transform (NTT) and Inverse NTT (INTT) operations, significantly increasing computational complexity and hardware resource usage.

Methodology
The paper proposes a framework for direct $n$ -input ciphertext multiplication that minimizes multiplicative depth and hardware complexity. The methodology is divided into two main contributions:

Improved Three-Input Multiplier:
The authors first reformulate the three-input multiplication process. In the preliminary work [26], relinearization and rescaling were performed separately, requiring multiple ModUp/ModDown operations and numerous (I)NTT blocks. The new design:
- Reformulates Relinearization: By moving the $P^{-1}$ scaling factor into the basis conversion (BConv) and evaluation key multiplication, the design eliminates separate scaling steps.
- Optimizes Rescaling: The authors restructure the data path to perform rescaling in the original domain before the final NTT, rather than in the NTT domain. This allows the elimination of redundant (I)NTT operations.
- Result: These changes reduce the number of (I)NTT blocks in the data path from eight to four, effectively halving the data path length.
Multi-Input Extension with Combined Rescaling:
To extend multiplication to $n > 3$ inputs without increasing multiplicative depth, the paper introduces:
- Generalized Evaluation Keys: New evaluation keys ( $ek_t$ ) are introduced to relinearize the higher-degree polynomial terms ( $d_t s^t$ ) generated by multiplying $n$ ciphertexts, reducing the result back to a two-polynomial format.
- Multi-Rescaling (Multi-RS) Algorithm: A theoretical analysis identifies conditions under which multiple rescaling operations can be delayed and combined. The authors propose an algorithm that performs $\mu$ concatenated rescaling operations using the same number of (I)NTT operations as a single rescaling. This is achieved by transforming the input to the INTT domain, performing iterative rescaling in the coefficient domain, and transforming back, utilizing precomputed constants to merge the operations.
- Input Partitioning Guidelines: The paper provides guidelines for partitioning $n$ inputs into groups (e.g., $(n_1, n_2, \dots, n_m)$ ) to maximize the number of combined rescaling operations while maintaining the optimal multiplicative depth of $\lceil \log_2 n \rceil$ . This involves creating unbalanced tree structures where possible to group more inputs before a rescaling step.

Key Contributions

Algorithmic Reformulation: A new formulation for three-input multiplication that combines intermediate computations, reducing the number of (I)NTT operations and shortening the data path.
Multi-Input Framework: An extension of ciphertext multiplication to arbitrary $n$ inputs using generalized evaluation keys and a tree-structured multiplier.
Combined Rescaling: A novel multi-rescaling algorithm that reduces the complexity of performing multiple rescalings to that of a single rescaling, regardless of the number of combined steps ( $\mu$ ).
Hardware Architecture: Design of fully-pipelined hardware architectures for the proposed multipliers, including optimized ModUp, ModDown, and rescaling units.

Results
The proposed designs were synthesized using the GlobalFoundries 22FDX process with parameters $N=2^{16}$ , $L=K=24$ , and $w=64$ .

Three-Input Multiplier: Compared to the prior work [26], the improved three-input multiplier achieves a 15% reduction in logic area and a 50% reduction in latency. It also reduces memory requirements by approximately 20% due to fewer (I)NTT units.
Multi-Input Multipliers ( $n=4$ to $12$): Compared to a baseline implementation using a binary tree of two-input multipliers, the proposed method achieves an average 32% reduction in total area and a 45% reduction in latency.
Rescaling Efficiency: For non-power-of-two inputs (e.g., $n=17$ ), the optimized partitioning combined with multi-rescaling reduces the total number of rescaling units (and associated (I)NTT operations) by approximately 47% compared to the standard binary tree approach.

Significance
The paper claims that these improvements address the bottleneck of multi-input multiplication in HE, which is essential for complex privacy-preserving applications. By reducing the hardware complexity and latency of ciphertext multiplication, the proposed architecture makes the deployment of HE in resource-constrained or high-throughput environments more feasible. The work demonstrates that through algorithmic reformulation and careful input partitioning, the overhead of noise management (rescaling) can be significantly minimized without compromising the security or correctness of the encryption scheme. The authors note that future work will focus on further simplifying multipliers for even larger numbers of inputs.