Polynomial Multiplication Architecture with Integrated Modular Reduction for R-LWE Cryptosystems

Xinmiao Zhang, Zheang Huai, Keshab K. Parhi

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The ring-learning with errors (R-LWE) problem is the basic building block of many ciphers resisting quantum-computing attacks and homomorphic encryption enabling computations on encrypted data. The most critical operation in these schemes is modular multiplication of long polynomials with large coefficients. The polynomial multiplication complexity can be reduced by the Karatsuba formula. In this work, a new method is proposed to integrate modular reduction into the Karatsuba polynomial multiplication. Modular reduction is carried out on intermediate segment products instead of the final product so that more substructure sharing is enabled. Moreover, this paper develops a complete architecture for the modular polynomial multiplication. Computation scheduling optimizations are proposed to reduce the memory access and number of clock cycles needed. Taking advantage of the additional shareable substructures, the proposed scheme reduces the size of the memories, which account for the majority of the modular polynomial multiplier silicon area, by 20% and 12.5%, when the Karatsuba decomposition factor is 2 and 3, respectively, and achieves shorter latency compared to prior designs.

Original languageEnglish (US)
Pages (from-to)799-809
Number of pages11
JournalJournal of Signal Processing Systems
Issue number8
StatePublished - Aug 2022
Externally publishedYes

Bibliographical note

Funding Information:
This work is supported in part by Semiconductor Research Corporation under contract number 2020-HW-2988.

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.


  • Homomorphic encryption
  • Karatsuba multiplication
  • Modular polynomial multiplication
  • Ring-learning with errors (R-LWE)
  • Substructure sharing


Dive into the research topics of 'Polynomial Multiplication Architecture with Integrated Modular Reduction for R-LWE Cryptosystems'. Together they form a unique fingerprint.

Cite this