Paper 2022/108
Public Key Compression and Fast Polynomial Multiplication for NTRU using the Corrected Hybridized NTT-Karatsuba Method
Rohon Kundu, Alessandro de Piccoli, and Andrea Visconti
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. Proceedings of the 8th International Conference on Information Systems Security and Privacy, ISBN 978-989-758-553-1
- Keywords
- Post-Quantum CryptographyLattice-based CryptographyRing-learning with Errors ProblemNTRU AlgorithmNumber Theoretic TransformationHybridized NTT-Karatsuba AlgorithmKey Size
- Contact author(s)
-
rohon kundu @ eit lth se
alessandro depiccoli @ unimi it
andrea visconti @ unimi it - History
- 2022-01-31: received
- Short URL
- https://ia.cr/2022/108
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/108,
author = {Rohon Kundu and Alessandro de Piccoli and Andrea Visconti},
title = {Public Key Compression and Fast Polynomial Multiplication for {NTRU} using the Corrected Hybridized {NTT}-Karatsuba Method},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/108},
year = {2022},
url = {https://eprint.iacr.org/2022/108}
}