High-Performance GPU Implementation of Key Generation in Post-quantum SNOVA Digital Signature Algorithm
摘要
SNOVA is a post-quantum digital signature scheme based on multivariate quadratic equations. It can effectively resist quantum attacks. However, SNOVA faces computational efficiency bottlenecks in practical deployment due to the extensive matrix operations required during key generation. To address this issue, this paper proposes a GPU-accelerated scheme for SNOVA key generation. First, we adopt a multi-dimensional grid mapping strategy to optimize thread allocation. We design specialized 2D and 3D grid configurations to achieve efficient parallelization of matrix operations. Second, we design a three-tier memory optimization system that effectively reduces memory access latency. Finally, we construct a batch processing framework for key generation. Through pipeline and reuse mechanisms, we implement batch key generation for SNOVA. Experimental results demonstrate that compared to the basic CPU implementation, the key generation speed achieves up to 12.30 \(\times \) improvement. In batch processing mode, GPU-SNOVA achieves up to 3.0 \(\times \) improvement in key generation time compared to the AVX2 version, and up to 58.44 \(\times \) improvement compared to the CPU version, meeting the requirements of high-throughput applications.