Area-Efficient Barrett Modular Multiplication With Optimized Karatsuba Algorithm

This article presents an area-efficient Barrett modular multiplication (BMM) algorithm, facilitating the development of cryptosystems like fully homomorphic encryption. Instead of implementing three normal multiplications required by classic BMM, our proposed BMM introduces optimizations for multiplication AB, truncated multiplication <tex-math notation="LaTeX">AB/2ᶠ </tex-math>, and modular multiplication (MM) <tex-math notation="LaTeX">AB ~mod~2ᶠ </tex-math>. Taking the 4-term Karatsuba algorithm as an example, an N-bit multiplication AB can be decomposed into <tex-math notation="LaTeX">$9~(N/4)$ </tex-math>-bit multiplications. Our optimized approaches for truncated multiplication and MM require an area equivalent to only <tex-math notation="LaTeX">$6.5~(N/4)$ </tex-math>-bit multiplications when <tex-math notation="LaTeX">f≈ N </tex-math>. Furthermore, our optimized Karatsuba multiplications introduce efficient (E, I) matrix pairs, circumventing area overhead from complex I matrices and sign extension in multiplication. We also employ encode algorithm to eliminate many additions needed in BMM and inside multiplications, significantly shortening critical path. Experimental results demonstrate the advantages of our proposed BMM in terms of throughput and area efficiency.