Efficient Mod Approximation and Its Applications to CKKS Ciphertexts
About
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}$).