Junhao Huang
Singapore Management University, Singapore

Yiteng Sun
Shandong University, Qingdao, China

Jipeng Zhang
National University of Singapore, Singapore

Weijia Wang
Shandong University, Qingdao, China

Donglong Chen
Guangdong Provincial Key Laboratory IRADS, Beijing Normal-Hong Kong Baptist University, Zhuhai, China

Haiyang Xue
Singapore Management University, Singapore

Guomin Yang
Singapore Management University, Singapore

Keywords: Raccoon signature, side-channel attacks, modular arithmetic, lattice-based cryptography

Abstract

Raccoon, presented at CRYPTO 2024, is a provably secure lattice-based signature scheme featuring an O(d log d) masking overhead. Although it did not advance beyond the first-round of NIST’s additional call for post-quantum digital signatures, Raccoon remains a promising candidate due to its low masking overhead and strong provable side-channel resistance. This paper proposes the first efficient and compact implementation of high-order Raccoon on the ARM Cortex-M4, with a focus on optimizing its polynomial multiplication, sampling, and memory consumption. 1) For polynomial multiplication, we present a consecutive 32-bit NTT/INTT implementation for the two moduli in Raccoon, enabling optimal 3+3+3 layer merging to reduce memory-access overhead, together with extensive lazy reduction to minimize modular reductions. As a side contribution, we propose a novel negative double Montgomery reduction technique to accelerate double modular reductions in multi-moduli NTT. 2) For polynomial sampling, we identify and resolve a previously overlooked performance bottleneck caused by frequent incremental SHAKE256 invocations for small data chunks on ARM Cortex-M4. By transitioning to the one-shot approach, we achieve speedups of at least 1.80x across all sampling routines in Raccoon. 3) Finally, we explore memory-saving techniques to enable the practical deployment of high-order masked Raccoon (up to 32 orders) on resource-constrained IoT devices. The proposed implementations outperform the Raccoon reference implementation by 1.86x–2.25x. Notably, high-order masked Raccoon-192 outperforms masked Dilithium3 by 3.11x, 8.07x, and 2.71x at masking orders d = 2, 4, and 8, respectively. Finally, the leakage evaluations confirm that the second-order Raccoon implementation provides strong resistance to differential power analysis (DPA) once micro-architectural transitional leakages are mitigated.