Paper 2024/1929 Original: eprint.iacr.org/2024/1929 ↗

LightCROSS: A Secure and Memory Optimized Post-Quantum Digital Signature CROSS

Abstract

Digital signature schemes derived from non-interactive zero-knowledge (NIZK) proofs are rapidly gaining prominence within post-quantum cryptography. CROSS is a promising new code-based post-quantum digital signature scheme based on the NIZK framework. It is currently in the second round of the NIST's additional call for standardization for post-quantum digital signatures. However, CROSS's reference implementation has a substantially large memory footprint. This makes its deployment on resource-constrained platforms prohibitively difficult. In particular, we identified several mechanisms, such as Merkle tree and GGM tree structures, commitment generation process, which are part of the zero-knowledge proof generation, are one of the most memory-intensive operations. We propose several novel algorithms and implementation strategies to reduce the memory requirement of these components. Apart from these, we also propose several memory optimization techniques, such as just-in-time hashing and execution flow analysis. As a result, our implementation reduces the memory footprint of Key Generation, Signature Generation, and Verification of the CROSS reference code by as much as 95%, 92%, and 85%, respectively. This results in a suite of implementations in which all variants are under 128kB (for all security levels of KeyGen/Sign/Verify) and six variants under 32kB. Our memory optimization techniques are not specific to CROSS, but can be applied to other NIZK-based signature schemes. Regarding efficiency, matrix multiplications are crucial to the performance of CROSS. We show how the Digital Signal Processing (DSP) instructions on ARM Cortex-M4, specifically packing and multiplying, can be utilized to efficiently implement matrix operations over finite fields. The DSP optimizations combined with the memory reductions improve the efficiency of CROSS by up to 32% and 33% in Signature Generation and Verification respectively.