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 - 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 -