The National Institute of Standards and Technology (NIST) approved XMSS as part of the post-quantum cryptography (PQC) development effort in 2018. XMSS is currently one of only two standardized PQC algorithms, but its performance limits its use. For example, the fastest record for some standardized parameters still takes more than a minute to generate a keypair. In this article, we present the first GPU implementation for XMSS and its variant XMSS $^{\mathsf {MT}}$ . The high parallelism of GPUs is especially effective for reducing latency in key generation and improving throughput for signing and verifying. In order to meet various application scenarios, we provide three parallel XMSS schemes: algorithmic parallelism , multi-keypair data parallelism , and single-keypair data parallelism . For these schemes, we design custom parallel strategies that use more than 10,000 cores for all parameters provided by NIST. In addition, we analyze the availability of most previous serial optimizations and explore numerous techniques to fully exploit GPU performance. Our evaluations are made with the XMSSMT-SHA2_20/2_256 parameter set on a GeForce RTX 3090. The result shows the key generation latency is 3.20 ms, a speedup of 21,899× compared to the GPU ported version, which is also 54× speedup faster than the fastest work (174 ms). When 16384 tasks are executed, the throughput (task/s) for signing/verifying in the single-key and multi-key cases is 311,424/415,100 and 145,100/419,887, respectively. Compared to the throughput for signing/verifying (1695/4000) of the fastest work, we obtain a speedup of 184×/104× and 86×/105× in single-key and multi-key cases, respectively.
11 September 2024 in IEEE Transactions on Computers
Quantum computers pose a serious threat to existing cryptographic systems. While Post-Quantum Cryptography (PQC) offers resilience against quantum attacks, its performance limitations often hinder widespread adoption. Among the three National Institute of Standards and Technology (NIST)-selected general-purpose PQC schemes, SPHINCS ${}^{+}$ is particularly susceptible to these limitations. We introduce CUSPX ( CU DA SP HIN CS ${}^{+}$ ), the first large-scale parallel implementation of SPHINCS ${}^{+}$ capable of running across 10,000 cores. CUSPX leverages a novel three-level parallelism framework, applying it to algorithmic parallelism , data parallelism , and hybrid parallelism . Notably, CUSPX introduces parallel Merkle tree construction algorithms for arbitrary parallel scales and several load-balancing solutions, further enhancing performance. By treating tasks parallelism as the top level of parallelism, CUSPX provides a four-level parallel scheme that can run with any number of tasks. Evaluated on a single GeForce RTX 3090 using the SPHINCS ${}^{+}$ -SHA-256-128s-simple parameter set, CUSPX achieves a single task's signature generation latency of 0.67 ms, demonstrating a 5,105 $\times$ speedup over a single-thread version and an 18.50 $\times$ speedup over the previous fastest implementation.
The hash-based signature (HBS) is the most conservative and time-consuming among many post-quantum cryptography (PQC) algorithms. Two HBSs, LMS and XMSS, are the only PQC algorithms standardised by the National Institute of Standards and Technology (NIST) now. Existing HBSs are designed based on serial Merkle tree traversal, which is not conducive to taking full advantage of the computing power of parallel architectures such as CPUs and GPUs. We propose a parallel Merkle tree traversal (PMTT), which is tested by implementing LMS on the GPU. This is the first work accelerating LMS on the GPU, which performs well even with over 10,000 cores. Considering different scenarios of algorithmic parallelism and data parallelism, we implement corresponding variants for PMTT. The design of PMTT for algorithmic parallelism mainly considers the execution efficiency of a single task, while that for data parallelism starts with the full utilisation of GPU performance. In addition, we are the first to design a CPU-GPU collaborative processing solution for traversal algorithms to reduce the communication overhead between CPU and GPU. For algorithmic parallelism, our implementation is still 4.48× faster than the ideal time of the state-of-the-art traversal algorithm. For data parallelism, when the number of cores increases from 1 to 8,192, the parallel efficiency is 78.39%. In comparison, our LMS implementation outperforms most existing LMS and XMSS implementations.
In Wireless Sensor Networks (WSNs), server clusters, and other systems requiring secure transmission, the overhead of data encryption and transmission is often not negligible. Unfortunately, a conflict exists between security and efficiency in processing data. Therefore, this paper proposes a strategy to overcome this conflict, called Client-Aware Negotiation for Secure and Efficient Data Transmission (CAN-SEAT). This strategy allows a client with different security transmission requirements to use the appropriate data security transmission without modifying the client. Two methods are designed for different clients. The first method is based on two-way authentication and renegotiation. After handshakes, the appropriate data security transmission scheme is selected according to the client requirements. Another method is based on redirection, which can be applied when the client does not support two-way authentication or renegotiation. For the characteristics of different architecture, this paper classifies and discusses symmetric key algorithms, asymmetric key algorithms, and hardware encryption instructions. In four application scenarios, the CAN-SEAT strategy is tested. Compared with the general transmission strategy, when only software encryption is used, the data processing and transmission cost can be reduced by 89.41% in the best case and by 15.40% in the worst case. When supporting hardware encryption, the cost can be reduced by 85.30% and 24.63%, respectively. A good effect was produced on the experimental platforms XiLinx, FT-2000+, and Intel processors. To the best of our knowledge, for Client-Aware Negotiation (CAN), this is the first method to be successfully deployed on a general system. CAN-SEAT can be easily combined with other energy-efficient strategies.
16 February 2022 in Future Generation Computer Systems