Fast and compact interleaved modular multiplication based on carry save addition

Oleg Mazonka, Eduardo Chielle, Deepraj Soni, Michail Maniatakos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450392174
DOIs
StatePublished - Oct 30 2022
Event41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022 - San Diego, United States
Duration: Oct 30 2022Nov 4 2022

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Conference

Conference41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
Country/TerritoryUnited States
CitySan Diego
Period10/30/2211/4/22

Keywords

  • modular multiplication

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Fast and compact interleaved modular multiplication based on carry save addition'. Together they form a unique fingerprint.

Cite this