X 2 O: Cross Parallel Optimization of the CROSS Post-Quantum Scheme on GPU

The CROSS Digital Signature Algorithm (DSA), currently a second-round candidate in the NIST standardization process for additional post-quantum digital signatures, offers compact public keys and strong security guarantees rooted in the code-based Restricted Syndrome Decoding Problem (R-SDP) and its variant R-SDP(G). Despite its strong theoretical foundation and practical significance, existing CPU-based implementations of CROSS exhibit evident performance limitations, while its potential for high-throughput acceleration on GPU architectures remains insufficiently investigated. In this work, we present X2O, the first systematically optimized GPU implementation framework for CROSS on NVIDIA GPUs. X2O introduces a novel cross-parallel architecture that integrates both horizontal and vertical parallelism to fully exploit the massive concurrency of modern GPU platforms. The framework incorporates a series of targeted optimizations, including fine-grained thread scheduling, optimized memory access patterns, hash function tuning, and GPU-efficient tree construction. Experimental results on a NVIDIA RTX 4090 demonstrate the efficiency of our design, achieving up to 1,082,904 signature generations and 1,589,595 verifications per second at NIST security level 1. Compared to the official AVX-optimized CPU implementation, our GPU-based approach achieves up to 120× speedup, establishing a new performance benchmark for CROSS and demonstrating the viability of high-throughput, post-quantum digital signatures on parallel computing platforms.