Base Conversion RNS using Hybrid Barret-Karatsuba-Based Modulus Prime Cores for Homomorphic Multiplication
Muhammad Ogin Hasanuddin, Rafael Aditya Cahyo W, Infall Syafalni, Nana Sutisna, Hanho Lee, Trio Adiono · 2025
Residue Number Systems (RNS) offer a promising approach to enhancing the computational efficiency of Fully Homomorphic Encryption (FHE). This paper proposes an efficient base conversion method for RNS, leveraging parallel Processing Unit (PU) cores, where each PU core operates under different moduli, along with a Karatsuba-based Barrett modular multiplier to accelerate modular arithmetic in homomorphic encryption schemes. Our approach addresses the computational bottleneck of base conversions in FHE by utilizing optimized parallelism and efficient multiplication methods. Experimental results show that, with nearly the same latency for the computing unit, the proposed design can achieve higher throughput for implementing base conversion (BConv). The performance is further evaluated with different parallel core configurations (2, 3, and 6 cores), and these scenarios are compared against a single-core implementation. The design with 6 parallel cores achieves more than 5Gbps, demonstrating the significant benefit of increased parallelism for BConv in FHE operations.