Area-Efficient Barrett Modular Multiplication With Optimized Karatsuba Algorithm
Bo Zhang, Shoumeng Yan
Abstract
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\lfloor AB/2^{f} \rfloor $ </tex-math></inline-formula>, and modular multiplication (MM) <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$AB ~\text {mod}~2^{f}$ </tex-math></inline-formula>. Taking the 4-term Karatsuba algorithm as an example, an N-bit multiplication AB can be decomposed into <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$9~(N/4)$ </tex-math></inline-formula>-bit multiplications. Our optimized approaches for truncated multiplication and MM require an area equivalent to only <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$6.5~(N/4)$ </tex-math></inline-formula>-bit multiplications when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$f\approx N$ </tex-math></inline-formula>. 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.