KD-Finder: A Karatsuba Decomposition Optimization Finder for NTT-Friendly Montgomery Modular Multiplication

Fully homomorphic encryption (FHE) allows operations to be performed directly on encrypted data, and has attracted massive attention in data security scenarios. Numerous resource-efficient FHE acceleration methods have been proposed, including many on the optimization of modular multiplication (MM), a fundamental operation in FHE, by leveraging Karatsuba multiplication and number-theoretic transform (NTT)-friendly moduli for montgomery MM (MMM). However, FHE is not yet practical due to its significant resource overheads. In this article, we report an automated Karatsuba decomposition search strategy that drastically improves the efficiency of MM implementation. Our key idea is to integrate NTT-friendly moduli into Karatsuba decomposition within parallel MMM, and incorporate optimization features such as truncated multiplication AB/R and MM AB mod R. After a careful analysis of the optimization space, we propose an automated Karatsuba decomposition optimization search algorithm based on a greedy strategy to enhance efficiency and effectiveness. Theoretical analysis shows that, under the mainstream NTT-friendly modulus conditions, the optimized two, three, and four-term Karatsuba decomposition schemes achieve an average area reduction of 18% for MMM over the basic Karatsuba method and 57% over the classical Schoolbook method. Furthermore, hardware implementations on FPGA demonstrate 29%-79% improvement, with an average of 59%, in area/throughput compared to the state-of-the-art implementations.