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

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1007/978-3-030-14234-6_7

Share

COinS