Modular arithmetic optimization in Kyber KEM

Kyber is a post-quantum key encapsulation mechanism that is a finalist in the third round of the NIST Post-Quantum Cryptography Competition. A key encapsulation mechanism belongs to public key cryptography and is used to securely transmit a cryptography secret key over a public channel. However modern widespread public key cryptography schemes are vulnerable to quantum computer attacks. In recent years, quantum-resistant cryptography, called post-quantum cryptography, has been actively developing. For today, Kyber is the only post-quantum key encapsulation mechanism recommended for standardization by NIST. This paper presents a new approach to optimize arithmetic operations in Kyber. It reduces the number of modular reductions by increasing the bit size of numbers. The proposed optimization is appropriate for the general purpose systems with 32 or 64-bit CPUs. According to the benchmarking, our optimization speeds up the decapsulation algorithm by up to 1.83 times, the encapsulation algorithm—by up to 1.58 times, and the key generation—by up to 1.41 times. We also generalize our optimization and propose a strategy for applying it to other post-quantum cryptography schemes that have a similar design to Kyber.