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, Cuba, 2 - 04 October 2019, vol.11774, pp.237-256 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 11774
  • Doi Number: 10.1007/978-3-030-30530-7_12
  • City: Santiago de Cuba
  • Country: Cuba
  • Page Numbers: pp.237-256
  • Keywords: Post-quantum key encapsulation, Lattice-based cryptography, RLWE, NTT
  • Middle East Technical University Affiliated: Yes


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.