Harry Hart
University of Surrey, UK

Puja Mondal
Department of Computer Science and Engineering, IIT Kanpur, India

Suparna Kundu
COSIC, KU Leuven, Kasteelpark Arenberg 10, Bus 2452, B-3001 Leuven-Heverlee, Belgium

Supriya Adhikary
Department of Computer Science and Engineering, IIT Kanpur, India

Angshuman Karmakar
Department of Computer Science and Engineering, IIT Kanpur, India

Chaoyun Li
University of Surrey, UK; COSIC, KU Leuven, Kasteelpark Arenberg 10, Bus 2452, B-3001 Leuven-Heverlee, Belgium

Keywords: Post-quantum cryptography, Digital signatures, Code-based digital signatures, CROSS, Software implementation, Memory footprint, ARM Cortex-M4

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 the most memory-intensive areas such as Merkle and GGM tree structures, and zero-knowledge proof commitment generation. 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.