Reduced-complexity modular polynomial multiplication for R-LWE cryptosystems

Xinmiao Zhang, Keshab K. Parhi

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations


The ring-learning with errors (R-LWR) problem is utilized to build many ciphers resisting quantum-computing attacks and fully homomorphic encryption that allows computations to be carried out on encrypted data. Modular multiplication of long polynomials with large coefficients is the most critical operation in these schemes. The polynomial multiplication complexity can be reduced by the Karatsuba formula. In this paper, a new method is proposed to integrate the modular reduction into the Karatsuba polynomial multiplication. Modular reduction is applied to intermediate segment products instead of the final product. As a result, additional substructure sharing is enabled and the number of coefficient additions needed for assembling the segment products to get the final result is substantially reduced. For polynomial multiplications with decomposition factors 2, 3, and 4, the proposed scheme reduces the number of additions by 13-17%.

Original languageEnglish (US)
Pages (from-to)7853-7857
Number of pages5
JournalICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
StatePublished - Jun 6 2021
Event2021 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2021 - Virtual, Toronto, Canada
Duration: Jun 6 2021Jun 11 2021

Bibliographical note

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

Publisher Copyright:
© 2021 IEEE


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


Dive into the research topics of 'Reduced-complexity modular polynomial multiplication for R-LWE cryptosystems'. Together they form a unique fingerprint.

Cite this