Compact and Simple RLWE Based Key Encapsulation Mechanism

Alkim E., Bilgin Y. A., CENK M.

6th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT), Santiago de Cuba, Küba, 2 - 04 Ekim 2019, cilt.11774, ss.237-256 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 11774
  • Doi Numarası: 10.1007/978-3-030-30530-7_12
  • Basıldığı Şehir: Santiago de Cuba
  • Basıldığı Ülke: Küba
  • Sayfa Sayıları: ss.237-256
  • Anahtar Kelimeler: Post-quantum key encapsulation, Lattice-based cryptography, RLWE, NTT
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we propose a key encapsulation scheme based on NewHope and Kyber, two NIST post-quantum standardization project candidates. Our scheme is based on NewHope, thus it is simple and has fast implementation while it is making use of smaller key sizes and easily changeable security level advantages of Kyber. The scheme heavily use recent advances on Number Theoretic Transform (NTT) in a way that transformation from one degree polynomial to another is easy. To make it possible, we changed the definition of component in component-wise multiplication during polynomial multiplication and show that changing security level only requires to change the size of polynomial and the definition of component. Our scheme has 11.5% smaller communication cost for the same security level comparing with NewHope. In addition, it is at least 17% faster C implementation comparing with non-optimized Kyber implementation from the first round of the NIST standardization process.