💻 computer science

Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

This paper proposes a novel polynomial-based method to accurately approximate the mod function over the entire input domain for CKKS homomorphic encryption, enabling efficient data packing schemes, homomorphic rounding, and the conversion of additive secret shares to ciphertexts with high precision.

Original authors: Yufei Zhou

Published 2026-04-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yufei Zhou

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 have a super-secure digital safe (Homomorphic Encryption) that allows you to do math on data without ever opening it. You can add and multiply numbers inside the safe, but there's a catch: the safe is terrible at doing one specific thing—finding the remainder (the "mod" operation).

Think of the "mod" operation like a clock. If it's 14:00, what time is it on a 12-hour clock? It's 2:00. The math is simple for us, but for this digital safe, the "clock" function is broken because it involves jumping back and forth (discontinuities), which the safe's math engine hates.

This paper is about fixing that broken clock so we can do more useful things with our encrypted data, especially when dealing with small numbers like images, genetic codes, or simple sensor data.

Here is the breakdown of their solution using everyday analogies:

1. The Problem: The "Broken Clock" in the Safe

The authors point out that while the safe (CKKS encryption) is great at smooth math, it struggles with the "Mod" function because it jumps around. Existing attempts to fix this were like trying to draw a perfect circle using only a few straight lines; it worked okay in one corner, but looked terrible everywhere else.

2. The Solution: A "Smooth Curve" Trick

The authors invented a new way to approximate the "Mod" function using polynomials (mathematical curves).

The Analogy: Imagine trying to trace a jagged, saw-tooth wave (the Mod function) with a smooth, flexible ruler. Previous methods tried to bend the ruler only a little bit, so it only fit the top of the saw.
The Innovation: These researchers used a special type of ruler called a Chebyshev series. It's like a super-flexible, high-quality ruler that can hug the jagged saw-tooth wave perfectly across the entire range, not just a small part. They also figured out how to keep the ruler from getting too wobbly (numerical instability) by scaling it down.

3. The Superpower: "Data Stacking" (BitStack & CRTStack)

Once they fixed the "Mod" function, they realized they could use it to pack more data into the safe.

The Problem: Usually, if you have 100 small items (like pixels in an image), you might need 100 separate safes to store them, or you have to leave huge empty spaces in one safe. This is wasteful and slow to send over the internet.
The Fix (BitStack): Imagine stacking Lego bricks. Instead of putting each brick in its own box, you stack them vertically into one tall tower. The "Mod" function acts like a laser cutter that can slice the tower apart later to get the individual bricks back.
The Fix (CRTStack): Imagine a puzzle. You take 100 small pieces and mix them together into one big, complex shape using a special recipe (Chinese Remainder Theorem). Later, you use the "Mod" function as a set of keys to unlock and separate the pieces.
Why it matters: This allows users to send much less data to the server. It's like mailing a single, dense brick instead of a box full of air and a few bricks.

4. Real-World Applications

With this new "Mod" tool, the authors showed how to do two cool things:

Rounding Numbers: They can now tell the safe to round numbers (e.g., turning 3.7 into 4) accurately, which is crucial for things like image processing.
The "Secret Handshake" Converter: Imagine a group of people holding pieces of a secret (Secret Sharing). Usually, they can't easily turn those pieces into an encrypted format for the safe. The authors built a bridge that lets them convert those pieces directly into the safe's format without needing to reveal the secret first.

5. The Results: Faster and Smarter

Speed: Their method is much faster than previous "Transcipher" methods (which are like using a heavy, slow truck to move data). Their method is like using a high-speed drone.
Accuracy: They achieved an accuracy so high (errors as small as 0.00000001) that for all practical purposes, the math is perfect.
Efficiency: They reduced the amount of data users need to upload by nearly 100 times in some cases.

Summary

In short, the authors found a way to teach a "dumb" encryption safe how to do the "Mod" (remainder) math perfectly. Once the safe could do that, they figured out how to pack data tightly (like Tetris) and unpack it easily, making encrypted computing much faster, cheaper, and more practical for things like medical data and AI on your phone.

1. Problem Statement

The CKKS homomorphic encryption (HE) scheme is widely used for approximate arithmetic on encrypted real numbers but natively supports only addition and multiplication. It lacks direct support for non-linear or discontinuous operations, specifically the modulus function ( $x \mod p$ ).

The Challenge: The modulus function is periodic and discontinuous, making it extremely difficult to approximate accurately across a wide input domain using polynomials.
Limitations of Existing Work: Previous methods (e.g., using sine series or composite functions) can only approximate the modulus function accurately within restricted sub-ranges of the input. They fail to provide high accuracy across the entire domain, which is critical for applications like data packing, rounding, and secret sharing conversion.
Practical Bottleneck: In privacy-preserving scenarios (e.g., IoT, smart homes), uploading large ciphertexts for small integer data is inefficient due to high communication costs and computational overhead.

2. Methodology

The authors propose a novel framework centered on a high-accuracy polynomial approximation of the modulus function, which serves as the foundation for efficient data packing and other cryptographic transformations.

A. Accurate Mod Function Approximation

Approach: Instead of relying on trigonometric approximations valid only in small intervals, the authors use polynomial interpolation combined with Chebyshev series expansion.
Discrete Sampling: The method treats the modulus function as a set of discrete sample points $(i, i \mod p)$ for integer inputs in the interval $[0, B]$ .
Chebyshev Series: To avoid the Runge phenomenon and numerical instability associated with high-degree Lagrange interpolation, the authors fit the data using a Chebyshev series of the first kind.
- The input range is mapped to $[-1, 1]$ .
- Coefficients are solved via a least-squares method, selecting the solution with the minimal $\ell_2$ -norm to ensure stability.
Scaling Factor ( $\delta$ ): To prevent error amplification during homomorphic evaluation (where coefficients $>1$ cause rapid noise growth), the authors introduce a scaling factor $\delta$ . They iteratively adjust $\delta$ to ensure all intermediate polynomial evaluation values remain strictly below 1, ensuring numerical stability without requiring bootstrapping.
Evaluation: The Paterson–Stockmeyer method is used to efficiently evaluate the high-degree Chebyshev polynomials within the CKKS circuit.

B. Data Packing Schemes

Based on the efficient homomorphic mod operation, two new data packing schemes are designed to maximize the utilization of CKKS plaintext slots for small-integer inputs:

BitStack:
- Mechanism: Concatenates binary representations of multiple data items into a single large integer.
- Unpacking: Uses the homomorphic mod function to extract layers sequentially (e.g., $x \mod 2^{l_1}$ extracts the first layer).
- Pros: Highly compact; no redundancy in bit representation.
- Cons: Unpacking is serial, leading to error accumulation and higher multiplicative depth usage.
CRTStack (Chinese Remainder Theorem Stack):
- Mechanism: Packs data by solving a system of congruences $x \equiv a_i \pmod{P_i}$ , where $P_i$ are pairwise coprime moduli.
- Unpacking: Uses homomorphic mod operations with different moduli ( $P_i$ ) to extract layers in parallel.
- Pros: Parallel unpacking reduces latency; errors in each layer are independent (no accumulation).
- Cons: Requires selection of coprime moduli, potentially introducing slight range redundancy.

C. Additional Applications

Homomorphic Rounding: The mod function enables the implementation of Floor, Ceil, and Round functions for small integers using the relation: $\text{Floor}(x, p) = (x - \text{Mod}(x, p)) / p$ .
Secret Share to HE Conversion: A general transformation scheme is proposed to convert additive secret shares (from Multi-Party Computation) directly into CKKS ciphertexts without modifying the underlying secret sharing scheme. This is achieved by summing encrypted shares and applying the homomorphic mod function to reconstruct the secret.

3. Key Contributions

Novel Mod Approximation: A polynomial approximation method using Chebyshev series that achieves high accuracy (up to $10^{-8}$ ) across the entire bounded integer input domain, overcoming the limitations of previous partial-range approximations.
Efficient Data Packing: Introduction of BitStack and CRTStack, which significantly reduce the communication overhead and encryption time for small-integer inputs by packing multiple values into a single ciphertext.
Homomorphic Rounding: Implementation of accurate rounding operations for CKKS ciphertexts, enabling integer-like processing on approximate HE.
Secret Share Conversion: The first complete scheme to convert additive secret shares to CKKS ciphertexts using only CKKS operations, bridging the gap between MPC and HE.

4. Experimental Results

Experiments were conducted using the OpenFHE library on an Intel Xeon Gold CPU.

Approximation Accuracy: The proposed method achieved average absolute errors as low as $10^{-8}$ (with polynomial degree 45+), significantly outperforming baselines like Lee et al. [LLL+21] (error $\approx 2.0$ ) and standard OpenFHE approximations.
Data Packing Efficiency:
- Communication: The proposed packing methods reduced upload traffic by nearly two orders of magnitude compared to standard CKKS encryption.
- Speed: Compared to the Rubato Transcipher framework, the proposed method was 1.6x faster in unpacking (156s vs. 407s) and achieved 10x lower error ( $4.0 \times 10^{-6}$ vs. $7.5 \times 10^{-5}$ ).
- Latency: Under moderate bandwidth (400–600 KB/s), the total latency (encryption + upload + unpacking) was lower than both standard CKKS and Transcipher schemes.
Rounding & Conversion: The homomorphic rounding achieved errors on the order of $10^{-10}$ . Secret share conversion maintained errors around $10^{-8}$ even with increasing numbers of parties.

5. Significance

This work addresses a critical gap in the practicality of CKKS for real-world applications involving small integers (e.g., genomic data, image processing, IoT sensor data).

Scalability: By drastically reducing the number of ciphertexts required to upload data, it alleviates the communication bottleneck that currently limits HE adoption in bandwidth-constrained environments.
Functional Expansion: It extends the functional expressiveness of CKKS beyond linear arithmetic, enabling essential non-linear operations like rounding and modular reduction.
Interoperability: The secret share conversion scheme provides a seamless bridge between Secure Multi-Party Computation (MPC) and Homomorphic Encryption, allowing for hybrid privacy-preserving architectures.
Limitation: The method is currently optimized for small integer inputs (bounded intervals, typically $B < 100$ ) and is not intended for large-scale bootstrapping where the input range is vast. However, this covers a wide array of practical use cases in data analytics and machine learning.