Area-Efficient Hardware Design for Approximate Basis Conversion in RNS-Variant CKKS Schemes

Residue number system (RNS) is a fundamental optimization widely employed in cryptography. In applications such as homomorphic encryption (HE) schemes, the required modulus size can reach several thousand bits. By using RNS decomposition, modular multiplication under a large modulus is performed in parallel over smaller moduli. During the HE procedure, the modulus size is dynamically scaled up or down through basis conversion in the RNS domain. This paper focuses on basis conversion within the Cheon-Kim-Kim-Song (CKKS) scheme, a popular candidate for privacy-preserving machine learning. Due to its approximate nature, fast basis conversion (FBC) is used to accelerate switching between RNS bases, as small errors can be tolerated. However, the pre-processing stage of the FBC algorithm involves unavoidable modular reductions, resulting in significant area overhead and low utilization. In this work, we present a novel approximate basis conversion (ABC) method that eliminates the need for modular reductions while enabling reuse of the dot product hardware structure. Experimental results demonstrate that the proposed ABC achieves a 64.4% reduction in area-time products under various usage scenarios compared to FBC in CKKS-based computations.