Paper 2026/2278

Masked CROSS: Masking the CROSS Digital Signature Scheme at Arbitrary Order

Abstract

CROSS is a code-based signature scheme built on the Restricted Syndrome Decoding Problem and is a second-round candidate in NIST's additional digital signature standardization process. Recent work shows that its reference implementation is vulnerable to side-channel analysis, allowing an attacker to recover the long-term secret key from a single power trace. No masking countermeasure has so far been designed for CROSS's restricted-syndrome framework, leaving its practical side-channel resistance unresolved. In this work, we present a full sensitivity analysis and a gadget-based masking schedule ($G_0-G_8$) for the CROSS signing algorithm of the R-SDP(G) variant. One gadget in this schedule, the restriction-lift exponentiation, has no counterpart in prior masked multivariate- or lattice-based signatures: it masks $g^{\bar{\mathbf v}[i]}$ via table lookup, share-serial conversion, and ISW-multiplication sub-gadgets rather than via a fixed linear or bilinear map. We rigorously prove $t_{\mathrm{mask}}$-probing security for each gadget individually and for their full composition, using the NI, SNI, and NIo frameworks. We implement the resulting masked signer for an arbitrary number of shares $d$ and evaluate it on an x86-64 platform, measuring cycle overheads of $21.73\times$ at first order and $78.05\times$ at second order relative to the unmasked baseline. At first order, our masked CROSS is cheaper than a comparably masked Dilithium-2 ($38\times$), but Dilithium-2 overtakes it at second order ($70\times$). This crossover cost is driven by the $O(d^3)$ chained-ISW cost of $G_3$/$G_7$ compared to Dilithium's cheaper $O(d^2)$ scaling.