Public Key Compression and Fast Polynomial Multiplication for NTRU using the Corrected Hybridized NTT-Karatsuba Method
(2022) 8th International Conference on Information Systems Security and Privacy, ICISSP 2022 p.145-153- Abstract
- NTRU is a lattice-based public-key cryptosystem that has been selected as one of the Round III finalists at the NIST Post-Quantum Cryptography Standardization. Compressing the key sizes to increase efficiency has been a long-standing open question for lattice-based cryptosystems. In this paper we provide a solution to three seemingly opposite demands for NTRU cryptosystem: compress the key size, increase the security level, optimize performance by implementing fast polynomial multiplications. We consider a specific variant of NTRU known as NTRU-NTT. To perform polynomial optimization, we make use of the Number-Theoretic Transformation (NTT) and hybridize it with the Karatsuba Algorithm. Previous work done in providing 2-part Hybridized... (More)
- NTRU is a lattice-based public-key cryptosystem that has been selected as one of the Round III finalists at the NIST Post-Quantum Cryptography Standardization. Compressing the key sizes to increase efficiency has been a long-standing open question for lattice-based cryptosystems. In this paper we provide a solution to three seemingly opposite demands for NTRU cryptosystem: compress the key size, increase the security level, optimize performance by implementing fast polynomial multiplications. We consider a specific variant of NTRU known as NTRU-NTT. To perform polynomial optimization, we make use of the Number-Theoretic Transformation (NTT) and hybridize it with the Karatsuba Algorithm. Previous work done in providing 2-part Hybridized NTT-Karatsuba Algorithm contained some operational errors in the product expression, which have been detected in this paper. Further, we conjectured the corrected expression and gave a detailed mathematical proof of correctness. In this paper, for the first time, we optimize NTRU-NTT using the corrected Hybridized NTT-Karatsuba Algorithm. The significance of compressing the value of the prime modulus q lies with decreasing the key sizes. We achieve a 128-bit post-quantum security level for a modulus value of 83,969 which is smaller than the previously known modulus value of 1,061,093,377, while keeping n constant at 2048. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/8750f1d8-8a92-414f-88c9-6eac430dc730
- author
- Kundu, Rohon LU ; De Piccoli, Alessandro and Visconti, Andrea
- organization
- publishing date
- 2022
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Post-Quantum Cryptography, Lattice-based Cryptography, Ring-learning with Errors Problem, NTRU Algorithm, Number Theoretic Transformation, Hybridized NTT-Karatsuba Algorithm, Key Size
- host publication
- Proceedings of the 8th International Conference on Information Systems Security and Privacy
- pages
- 9 pages
- publisher
- SciTePress
- conference name
- 8th International Conference on Information Systems Security and Privacy, ICISSP 2022
- conference location
- Online Streaming
- conference dates
- 2022-02-09 - 2022-02-11
- external identifiers
-
- scopus:85176356214
- ISBN
- 978-989-758-553-1
- DOI
- 10.5220/0010881300003120
- project
- Säkra mjukvaruuppdateringar för den smarta staden
- language
- English
- LU publication?
- yes
- id
- 8750f1d8-8a92-414f-88c9-6eac430dc730
- date added to LUP
- 2022-01-11 17:49:57
- date last changed
- 2024-05-10 07:45:41
@inproceedings{8750f1d8-8a92-414f-88c9-6eac430dc730, abstract = {{NTRU is a lattice-based public-key cryptosystem that has been selected as one of the Round III finalists at the NIST Post-Quantum Cryptography Standardization. Compressing the key sizes to increase efficiency has been a long-standing open question for lattice-based cryptosystems. In this paper we provide a solution to three seemingly opposite demands for NTRU cryptosystem: compress the key size, increase the security level, optimize performance by implementing fast polynomial multiplications. We consider a specific variant of NTRU known as NTRU-NTT. To perform polynomial optimization, we make use of the Number-Theoretic Transformation (NTT) and hybridize it with the Karatsuba Algorithm. Previous work done in providing 2-part Hybridized NTT-Karatsuba Algorithm contained some operational errors in the product expression, which have been detected in this paper. Further, we conjectured the corrected expression and gave a detailed mathematical proof of correctness. In this paper, for the first time, we optimize NTRU-NTT using the corrected Hybridized NTT-Karatsuba Algorithm. The significance of compressing the value of the prime modulus q lies with decreasing the key sizes. We achieve a 128-bit post-quantum security level for a modulus value of 83,969 which is smaller than the previously known modulus value of 1,061,093,377, while keeping n constant at 2048.}}, author = {{Kundu, Rohon and De Piccoli, Alessandro and Visconti, Andrea}}, booktitle = {{Proceedings of the 8th International Conference on Information Systems Security and Privacy}}, isbn = {{978-989-758-553-1}}, keywords = {{Post-Quantum Cryptography, Lattice-based Cryptography, Ring-learning with Errors Problem, NTRU Algorithm, Number Theoretic Transformation, Hybridized NTT-Karatsuba Algorithm, Key Size}}, language = {{eng}}, pages = {{145--153}}, publisher = {{SciTePress}}, title = {{Public Key Compression and Fast Polynomial Multiplication for NTRU using the Corrected Hybridized NTT-Karatsuba Method}}, url = {{http://dx.doi.org/10.5220/0010881300003120}}, doi = {{10.5220/0010881300003120}}, year = {{2022}}, }