Efficient Mod Approximation and Its Applications to CKKS Ciphertexts
This work addresses a critical bottleneck in homomorphic encryption for secure data processing, enabling efficient ciphertext operations like rounding and conversion from secret shares, though it is incremental as it builds on existing mod approximation methods.
The paper tackles the challenge of approximating the mod function for CKKS homomorphic encryption, which only supports arithmetic operations, by proposing a method based on polynomial interpolation and Chebyshev series to achieve accurate approximation across the entire input domain, with experimental results showing high accuracy up to 10^{-8}.
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. Existing homomorphic mod constructions provide accurate results only within limited subranges of the input domain, leaving the problem of achieving accurate approximation across the entire input domain unresolved.In this work, we propose a novel method based on polynomial interpolation and Chebyshev series to accurately approximate the mod function over all integer points in the bounded input interval. 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 shares to CKKS ciphertexts, achieving accurate ciphertext rounding and complete conversion from secret shares to CKKS ciphertexts. Experimental results demonstrate that our approach achieves high approximation accuracy (up to $10^{-8}$).