Compact and Simple RLWE-Based Key Encapsulation Mechanism

Abstract

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.