TY - GEN
T1 - Fast and compact interleaved modular multiplication based on carry save addition
AU - Mazonka, Oleg
AU - Chielle, Eduardo
AU - Soni, Deepraj
AU - Maniatakos, Michail
N1 - Funding Information:
In this work we presented an iterative modular multiplier that uses carry save adders. Instead of subtracting the modulus during iterations, the multiplier adds specific values at the same time dropping high bits of the accumulator. The specific values are pre-computed in such way so that the accumulator at each iteration preserves the modulo remainder. By avoiding the subtraction operation, the multiplier can utilize carry save adders. This novel approach results in improving the efficiency of modular multiplication by up to 47% compared to the Interleaved multiplier. The pipelined version further improves efficiency by 2x. At the same time, our design does not need transformation to and from a different domain, which is the case for Montgomery. Our design outperforms Montgomery for bit sizes above 64 when the extra calls to the multiplier are taken into account. The proposed multiplier is suitable for FHE computation, since the iterative design is much smaller than full multipliers followed by a reduction enabling the instantiation of many of them on-chip to support FHE operations. Pipelining options allow a balance between the size and speed of the multiplier. We open source [24] the hardware design. Acknowledgements: This work has been partially funded by the Defense Advanced Research Projects Agency (DARPA) under the Data Protection in Virtual Environments (DPRIVE) program, contract no. HR0011-21-9-0003.
Publisher Copyright:
© 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2022/10/30
Y1 - 2022/10/30
N2 - Improving fully homomorphic encryption computation by designing specialized hardware is an active topic of research. The most prominent encryption schemes operate on long polynomials requiring many concurrent modular multiplications of very big numbers. Thus, it is crucial to use many small and efficient multipliers. Interleaved and Montgomery iterative multipliers are the best candidates for the task. Interleaved designs, however, suffer from longer latency as they require a number comparison within each iteration; Montgomery designs, on the other hand, need extra conversion of the operands or the result. In this work, we propose a novel hardware design that combines the best of both worlds: Exhibiting the carry save addition of Montgomery designs without the need for any domain conversions. Experimental results demonstrate improved latency-area product efficiency by up to 47% when compared to the standard Interleaved multiplier for large arithmetic word sizes.
AB - Improving fully homomorphic encryption computation by designing specialized hardware is an active topic of research. The most prominent encryption schemes operate on long polynomials requiring many concurrent modular multiplications of very big numbers. Thus, it is crucial to use many small and efficient multipliers. Interleaved and Montgomery iterative multipliers are the best candidates for the task. Interleaved designs, however, suffer from longer latency as they require a number comparison within each iteration; Montgomery designs, on the other hand, need extra conversion of the operands or the result. In this work, we propose a novel hardware design that combines the best of both worlds: Exhibiting the carry save addition of Montgomery designs without the need for any domain conversions. Experimental results demonstrate improved latency-area product efficiency by up to 47% when compared to the standard Interleaved multiplier for large arithmetic word sizes.
KW - modular multiplication
UR - http://www.scopus.com/inward/record.url?scp=85145649779&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85145649779&partnerID=8YFLogxK
U2 - 10.1145/3508352.3549414
DO - 10.1145/3508352.3549414
M3 - Conference contribution
AN - SCOPUS:85145649779
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
BT - Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
Y2 - 30 October 2022 through 4 November 2022
ER -