Modular arithmetic optimization in Kyber KEM

Kyber is a post-quantum key encapsulation mechanism that has been selected as a finalist in the third round of the NIST Post-Quantum Cryptography Competition. Today, Kyber is the only post-quantum key encapsulation mechanism recommended for standardization by NIST. The paper presents a new approach to optimize arithmetic operations in Kyber KEM. 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.