Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

Yufei Zhou · 2025

Read Efficient Mod Approximation and Its Applications to CKKS Ciphertexts by Yufei Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-19951.txt.

Introduction

Yufei Zhou's submission on computing with encrypted data has been withdrawn by the author. The record gives the reason in the author's own words. The current version needs extensive modifications. What the withdrawn text presented was a way to run the modulo operation in the CKKS scheme. That scheme for homomorphic encryption supports only arithmetic. So remainder sums on ciphertexts are a standing hard problem.

The proposed fix approximated the mod function. It used polynomial interpolation and Chebyshev series. The aim was accuracy at each integer point of a bounded input range. Past methods were exact only on subranges. Two packing schemes for small-integer data were also described. So were uses in rounding and in turning secret shares into ciphertexts. Tests reported very high accuracy. All of it should be read as superseded, pending the author's revised version.

Catalog record

CREATORYufei Zhou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-19951

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Mod Approximation and Its Applications to CKKS Ciphertexts Yufei Zhou Abstract The mod function plays a critical role in numerous data encoding and cryptographic primitives. However, the widely used CKKS homomorphic encryption (HE) scheme supports only arithmetic operations, making it difficult to perform mod computations on encrypted data. Approximating the mod function with polynomials has therefore become an important yet challenging problem. The discontinuous and periodic characteristics of the mod function make it particularly difficult to approximate accurately under HE. Existing homomorphic mod constructions provide accurate results only within limited subranges of the input range, leaving the problem of achieving accurate approximation across the full input range unresolved. In this work, we propose a novel method based on polynomial interpolation and Chebyshev series to accurately approximate the mod function. Building upon this, we design two efficient data packing schemes, BitStack and CRTStack , tailored for small-integer inputs in CKKS. These schemes significantly improve the utilization of the CKKS plaintext space and enable efficient ciphertext uploads. Furthermore, we apply the proposed HE mod function to implement a homomorphic rounding operation and a general transformation from additive secret sharing to CKKS ciphertexts, achieving accurate ciphertext rounding and complete secret-share-to-CKKS conversion. Experimental results demonstrate that our approach achieves high approximation accuracy (up to 10 − 8 10^{-8} ). Overall, our work provides a practical and general solution for performing mod operations under CKKS, extending its applicability to a broader range of privacy-preserving computations. 1 Introduction Homomorphic encryption (HE) enables computation directly on encrypted data, providing strong privacy guarantees by allowing operations to be performed without decryption [ 12 , 41 ] . Despite its advantages in privacy-preserving computation, HE still faces significant practical challenges, particularly regarding computational overhead, memory usage, and communication costs [ 19 , 35 ] . These limitations are especially critical in resource-constrained environments such as smart home devices [ 46 ] , health monitoring systems [ 47 ] , and IoT platforms, where both computational and bandwidth resources are limited. Among various HE schemes, those based on the Ring Learning with Errors (RLWE) assumption—such as BFV [ 12 ] and CKKS [ 19 ] —enable efficient encrypted vector processing through Single Instruction Multiple Data (SIMD) operations. These schemes can encrypt multiple plaintext values into a single ciphertext, greatly improving throughput. However, ensuring strong security guarantees requires large ciphertext sizes and a substantial number of encrypted slots (up to 2^{15} in some cases) [ 35 ] . While SIMD operations reduce computation time per plaintext, the communication cost associated with transmitting large ciphertexts remains a major bottleneck, limiting the scalability and practicality of HE in real-world deployments. The CKKS scheme, in particular, has become widely adopted for approximate real-number arithmetic due to its efficiency in handling complex computations. However, CKKS natively supports only addition and multiplication, lacking direct support for non-linear or discontinuous operations such as the mod function, which are essential in many cryptographic protocols and data processing tasks. The discontinuous and periodic nature of the mod function makes it particularly challenging to approximate accurately in HE. Existing works typically provide approximations that are only valid within restricted subranges of the input, leaving the problem of accurate global approximation unresolved. To address this challenge, we propose a novel method for accurately approximating the mod function over the entire input range using polynomial interpolation and Chebyshev series expansion. Our approach enables precise mod operations on small integers directly within CKKS ciphertexts, effectively extending the functional expressiveness of CKKS. Building on this, we further propose two efficient data packing techniques, BitStack and CRTStack , which leverage the proposed homomorphic mod operation to significantly improve the utilization of the CKKS plaintext space. These techniques enable more efficient ciphertext uploading for small inputs. Beyond these improvements, we demonstrate additional applications of the proposed homomorphic mod function. In particular, we implement a homomorphic rounding function for CKKS that enables accurate rounding on ciphertexts of small integers, achieving an approximation error as low as 10^{-10} . Moreover, we present the first complete HE-based transformation scheme that converts additive secret shares into CKKS ciphertexts without any modification to the underlying secret sharing schemes, thereby bridging the gap between secret sharing and HE. In summary, our main contributions are as follows: 1. We propose an accurate polynomial approximation for the mod function using polynomial interpolation and Chebyshev series, overcoming the challenges posed by its discontinuous and periodic nature. 2. We design two efficient data packing methods, BitStack and CRTStack , tailored for small-integer inputs in CKKS, significantly reducing the computational and communication overhead of ciphertext uploading. 3. We implement a homomorphic rounding function based on the proposed mod approximation, enabling accurate rounding for CKKS ciphertexts of small integers. 4. We realize a general transformation from additive secret sharing to CKKS ciphertexts using the proposed homomorphic mod function. To the best of our knowledge, this is the first complete conversion scheme based only on CKKS operations. 2 Related Work 2.1 Mod Approximation The homomorphic mod function plays a crucial role in the study of leveled fully HE bootstrapping. Cheon et al. [ 16 ] approximates mod function using \frac{p}{2\pi}\times\sin\left(\frac{2\pi}{p}\times x\right) . By leveraging the double-angle formulas, they recursively approximate the sine function, thereby reducing the multiplicative depth required by the Taylor polynomial approximation. Following works [ 14 , 30 ] further explore how to use polynomials to more effectively approximate \sin or \cos . Lee et al. [ 37 ] uses composite functions and inverse trigonometric functions to achieve better approximations. Jutla et al. [ 32 ] approximates the mod function using the sine series. However, all of these researches have been on how to approximate mod function within a small interval. Among these methods, the approach proposed in [ 37 ] achieves the largest approximable range. However, more than half of the input domain still cannot be accurately approximated. Kim et al. in [ 34 ] introduced a novel modulus-1 algorithm. However, their method differs significantly from ours in both approach and application. They rely on modulus switching within CKKS ciphertexts, while our method uses polynomial approximation, which can be applied to any fully approximate HE scheme, not just CKKS. Their approach also depends on discrete bootstrapping for integer computations, whereas ours operates independently of bootstrapping, focusing on polynomial approximation of input integers. Our goal is not to compute on unpacked data, but to reduce the overhead of uploading encrypted ciphertexts, especially in image-based neural networks with real-number model parameters. Additionally, while [ 34 ] reports a modulus precision of 13.3, our method achieves a precision of 23.53. 2.2 Homomorphic Data Packing Smart et al. introduced a SIMD-based HE scheme [ 44 ] , later extended with polynomial decomposition [ 45 ] . Bonte et al. and others packed messages into Laurent polynomials [ 9 , 17 , 22 , 24 ] , and Castryck et al. [ 13 ] combined these with CRT, though limited by plaintext modulus and circuit depth. Aung et al. [ 6 ] improved parallelism via Reverse MFE; Angel et al. [ 4 ] used basis substitution but only for 1-bit messages; Zhang et al. [ 50 ] extended this but required O(n) substitutions and O(\log n) steps. Our scheme instead

Read the complete text