OSKR/OKAI: Systematic Optimization of Key Encapsulation Mechanisms from Module Lattice

In this work, we make systematic optimizations of key encapsulation mechanisms based on module learning-with-errors, covering algorithmic design, fundamental operation of number-theoretic transform, approaches to expanding the encapsulated key size, and AVX2/ARM implementations. We observe that the decryption can be simplified, leading to a both faster and less error-prone decryption process. Based on a systematic study of the variants of NTT, we present a new variant named hybrid-NTT that combines the advantages of existing NTT methods, and derive its optimality in computational complexity. We analyze and compare the different approaches to expand the size of key to be encapsulated and conclude with the most economic approach. Each above optimization technique is of independent value, and we apply all of them to KYBER and Aigis, resulting in new scheme variants named OSKR and OKAI respectively. For all new schemes proposed in this work, we provide optimized AVX2 and ARM Cortex-M4 implementations and present the performance benchmarks. Our AVX2 implementation provides up to 19.7% and 26.4% speedups compared to KYBER and Aigis, respectively. Meanwhile, with our new parameter set and optimization techniques, we show up to 17% improvement compared to KYBER on the ARM Cortex-M4 platform.