Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
12-2018
Abstract
The Number Theoretic Transform (NTT) provides efficient algorithm for multiplying large degree polynomials. It is commonly used in cryptographic schemes that are based on the hardness of the Ring Learning With Errors problem (RLWE), which is a popular basis for post-quantum key exchange, encryption and digital signature.To apply NTT, modulus q should satisfy that , RLWE-based schemes have to choose an oversized modulus, which leads to excessive bandwidth. In this work, we present “Preprocess-then-NTT (PtNTT)” technique which weakens the limitation of modulus q, i.e., we only require or . Based on this technique, we provide new parameter settings for KYBER and NEWHOPE (two NIST candidates). In these new schemes, we can reduce public key size and ciphertext size at a cost of very little efficiency loss.
Keywords
NTT, Preprocess-then-NTT, Kyber, NewHope, Ring Learning With Errors, Module Learning With Errors
Discipline
Information Security
Research Areas
Cybersecurity
Areas of Excellence
Digital transformation
Publication
Proceedings of the 14th International Conference, Inscrypt 2018, Fuzhou, China, December 14-17
Volume
11449
First Page
117
Last Page
137
ISBN
9783030142346
Identifier
10.1007/978-3-030-14234-6_7
Publisher
Springer
City or Country
Cham
Citation
ZHOU, Shuai; XUE, Haiyang; ZHANG, Daode; WANG, Kunpeng; LU, Xianhui; LI, Bao; and HE, Jingnan.
Preprocess-then-NTT technique and its applications to Kyber and NewHope. (2018). Proceedings of the 14th International Conference, Inscrypt 2018, Fuzhou, China, December 14-17. 11449, 117-137.
Available at: https://ink.library.smu.edu.sg/sis_research/9199
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/978-3-030-14234-6_7