2021 IEEE International Conference on Acoustics, Speech and Signal Processing

6-11 June 2021 • Toronto, Ontario, Canada

Extracting Knowledge from Information

2021 IEEE International Conference on Acoustics, Speech and Signal Processing

6-11 June 2021 • Toronto, Ontario, Canada

Extracting Knowledge from Information

Technical Program

Paper Detail

Paper IDASPS-1.1
Paper Title REDUCED-COMPLEXITY MODULAR POLYNOMIAL MULTIPLICATION FOR R-LWE CRYPTOSYSTEMS
Authors Xinmiao Zhang, The Ohio State University, United States; Keshab K. Parhi, University of Minnesota, United States
SessionASPS-1: Architectures
LocationGather.Town
Session Time:Tuesday, 08 June, 16:30 - 17:15
Presentation Time:Tuesday, 08 June, 16:30 - 17:15
Presentation Poster
Topic Applied Signal Processing Systems: Signal Processing Hardware [DIS-PROG, DIS-MLTC, DIS-SOCP]
IEEE Xplore Open Preview  Click here to view in IEEE Xplore
Virtual Presentation  Click here to watch in the Virtual Conference
Abstract 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%.