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 the Number Theoretic Transform (NTT), approaches to expanding the encapsulated key size, and AVX2/ARM implementations. We observe that decryption can be simplified, leading to a both faster and less error-prone decryption process. Based on a systematic study of 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 the 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 with KYBER and Aigis, respectively. Meanwhile, with our new parameter set and optimization techniques, we show up to a 17% improvement compared with KYBER on the ARM Cortex-M4 platform.