Multi-way High-Throughput Implementation of Kyber

This paper presents a novel approach to implement a multi-way Key Encapsulation Mechanism (KEM) that takes full advantage of the parallelism provided by SIMD instructions. Specifically, our multi-way KeyGen() function is capable of generating multiple unique key pairs simultaneously. To start, we introduce a multi-way data format to support the proposed multi-way KEM implementation. We then introduce a multi-way NTT implementation based on this novel data format. Compared to traditional one-way NTT implementation, our multi-way NTT significantly reduces the complicated permutation operations, leading to overall performance improvements. In terms of SHA3-related computations, while previous one-way Kyber implementations have used multi-way SHAKE to speed up the matrix and vector generation, the inherent execution flow of the one-way KEM cannot fully utilize the parallelism of the multi-way SHA3 implementation. On the contrary, our multi-way implementation effectively parallelizes these SHA3 computations, resulting in substantial speed enhancements. We have applied this methodology to Kyber on AVX2 and AVX-512, developing a 16-way Kyber implementation for AVX2 and a 32-way implementation for AVX-512. With faster multi-way NTT and fully parallelized SHA3 computations, the key generation, encapsulation, and decapsulation in Kyber on AVX2 and AVX-512 achieve impressive speed-ups of 36.0%/54.6%/25.9% and 80.6%/130.3%/51.3%, respectively, compared to traditional one-way AVX2 implementation. Lastly, we demonstrate the versatility of our multi-way approach in real-world applications. For example, the multi-way KeyGen() function can be seamlessly integrated into the TLS protocol using OpenSSL ENGINE APIs, extending its advantages to a wide range of TLS applications. Additionally, the multi-recipient KEM (mKEM) protocols used for secure group messaging can also benefit from our multi-way approach to enhance their performance.