Reduced complexity modular polynomial multiplication for R-LWE cryptosystems
A method for integrating modular reduction into Karatsuba polynomial multiplication, used to optimize performance of R-LWR-based ciphers and other cryptographic systems.
- Post-quantum cryptography
- Homomorphic encryption
- Secure cloud computing
In post-quantum cryptography, ring-learning with errors (R-LWR) is a computational problem utilized to build new cryptographic ciphers that resist quantum-computing attacks. Modular multiplication of long polynomials with large coefficients is the most critical operation in these ciphers, and the complexity of these operations drives significant energy consumption.
Researchers at the University of Minnesota have developed a new method for integrating modular reduction into Karatsuba polynomial multiplication. Using this complexity reduction method, modular reduction is applied to intermediate segment products instead of the final product. As a result, additional sub-structure 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, this method reduces the number of additions by 13-17%. This innovative method optimizes the performance of R-LWR-based ciphers and other cryptographic systems reliant on polynomial multiplication. By integrating modular reduction into Karatsuba polynomial multiplication, this method achieves significant efficiency gains while ensuring continued security and resilience of these encryption techniques in the face of quantum computing threats.
Phase of DevelopmentTRL: 3-4
The researchers have tested this method to validate analytical predictions. For polynomial multiplications with decomposition factors 2, 3, and 4, this method reduces the number of additions by 13-17%.
Desired PartnershipsThis technology is now available for:
- Sponsored research
Please contact our office to share your business’ needs and learn more.
- Keshab Parhi, PhD Distinguished McKnight University Professor, Department of Electrical and Computer Engineering
- Xinmiao Zhang; Keshab K. Parhi (13 May 2021), Reduced-Complexity Modular Polynomial Multiplication for R-LWE Cryptosystems, IEEE Xplore
- Zhang, X., Huai, Z. & Parhi, K.K. (2022), Polynomial Multiplication Architecture with Integrated Modular Reduction for R-LWE Cryptosystems, J Sign Process Syst, 94, 799–809
swap_vertical_circlecloud_downloadSupporting documents (0)Additional files may be available once you've completed the transaction for this product. If you've already done so, please log into your account and visit My account / Downloads section to view them.