Hybrid-Grained GPU Implementations for the Classic McEliece

This paper studies the high-performance implementation of Classic McEliece Key Encapsulation Mechanism (KEM), one of the candidates in the fourth round NIST Post-Quantum Cryptography competition. Focusing on batched application scenarios, we first propose a baseline implementation. Building upon this foundation, we introduce an baseline-optimized implementation and subsequently propose a hybrid-grained implementation that significantly enhances performance. However, under high task loads, hybrid-grained implementation may lead to performance degradation in the encapsulation phase. To address this issue, we propose an optimized hybrid-grained implementation. We evaluate our implementation on both NVIDIA GeForce GTX 1660S and NVIDIA Jetson Tegra X2 platforms. Experimental results show that under low task loads, the baseline-optimized, hybrid-grained, and optimized hybrid-grained implementations of encaps reduce latency by up to $22.29 \%, 90.79 \%$, and 73.21 %, respectively, while the hybrid-grained implementation of decaps achieves up to an 89.28% reduction in latency. Under high task loads, the baseline-optimized implementation of encaps improves throughput by up to 20.01 %, and the optimized hybridgrained implementation achieves up to an 18.10 % throughput improvement over the hybrid-grained implementation.