CROSS: Code-Based Digital Signature

15 Apr 2026

Introduction

In 2022, NIST launched a second standardization process for post-quantum digital signature schemes, with the goal of diversifying the mathematical foundations of the cryptographic portfolio with respect to the schemes already selected for standardization, namely ML-DSA (CRYSTALS-Dilithium), SLH-DSA (SPHINCS+) and FALCON. Among the proposed schemes, notable alternatives emerged based on isogenies, multivariate systems and linear codes.

In this context, in October 2024 NIST announced the 14 candidates selected for the second round of the process. Among these is CROSS (Codes and Restricted Objects Signature Scheme)¹, a digital signature scheme whose security is founded on a structured variant of the classical Syndrome Decoding Problem (SDP) applied to linear codes over finite fields. The scheme was designed by an international team of researchers, with a significant Italian component, including the author of this article.

Code-based cryptography has a long tradition in the construction of encryption and key encapsulation schemes (see Classic McEliece and HQC), but the design of efficient digital signatures starting from SDP has historically proven more difficult. In the context of codes, the approach typically employed to construct signatures is to define an identification protocol and subsequently apply the Fiat-Shamir transform. This paradigm is analogous to what is found in the case of Dilithium and some multivariate schemes. Similarly to the latter, identification protocols built directly on SDP exhibit a very high soundness error (i.e., the cheating probability of an adversary), requiring many parallel repetitions of the protocol to achieve the desired security level. Each repetition contributes to the signature size, leading to values significantly larger than the already standardized schemes. CROSS addresses this issue by introducing a “restricted” variant of the Syndrome Decoding problem, an algebraic structure that leads to a reduction in parameters with respect to the classical version and, consequently, in signature size.

“Restricted” Syndrome Decoding

A linear code $[n, k]_q$ over a finite field $\mathbb{F}_q$ is a vector subspace of dimension $k$ in $\mathbb{F}_q^n$ . It is equivalently described by its parity-check matrix $H \in \mathbb{F}_q^{r \times n}$ (with $r = n - k$ ), such that a word $\mathbf{c} \in \mathbb{F}_q^n$ belongs to the code if and only if $\mathbf{c}H^\top = \mathbf{0}$ . Given a generic vector $\mathbf{e} \in \mathbb{F}_q^n$ , the vector $\mathbf{s} = \mathbf{e}H^\top \in \mathbb{F}_q^r$ is called the syndrome of $\mathbf{e}$ .

The Syndrome Decoding Problem (SDP) asks: given $H$ and a syndrome $\mathbf{s}$ , find a vector $\mathbf{e} \in \mathbb{F}_q^n$ of Hamming weight exactly $w$ (i.e., with exactly $w$ non-zero coordinates) such that $\mathbf{e}H^\top = \mathbf{s}$ . This problem has been proven to be NP-complete in the general case and some of its formulations underlie important post-quantum KEM schemes, such as the aforementioned Classic McEliece and HQC.

As mentioned in the introduction, CROSS is not based directly on the classical SDP, but rather on a variant called the Restricted Syndrome Decoding Problem (R-SDP), introduced with the aim of constructing a more efficient zero-knowledge (ZK) protocol and supporting very compact key sizes.

R-SDP

Let $p$ be a prime number and $\mathbb{F}_p$ the finite field with $p$ elements. Let $g \in \mathbb{F}_p^*$ be an element of prime order $z$ , and let

$E = \langle g \rangle = \{g,\, g^2,\, \ldots,\, g^z\} \subseteq \mathbb{F}_p^*$

be the cyclic subgroup of $\mathbb{F}_p^*$ generated by $g$ , of order $|E| = z$ . A vector $\mathbf{e} \in \mathbb{F}_p^n$ is called restricted if all its coordinates belong to $E$ , i.e., $\mathbf{e} \in E^n$ .

R-SDP $(n, k, p, z)$ :Given a parity-check matrix $H \in \mathbb{F}_p^{r \times n}$ (with $r = n - k$ ), a syndrome $\mathbf{s} \in \mathbb{F}_p^r$ and a restricted set $E$ , find $\mathbf{e} \in E^n$ such that

$\mathbf{e} H^\top = \mathbf{s}.$

Unlike classical SDP, where one seeks a sparse vector (low Hamming weight), in R-SDP the solution has full support (all coordinates are non-zero) since all coordinates must belong to the subgroup $E$ . The restriction imposes a tight constraint on the problem, as typically $z = |E| \ll p - 1 = |\mathbb{F}_p^*|$ is chosen, substantially reducing the number of valid solutions. Despite this constraint, it has been proven that the decisional version of the problem is NP-complete for any restriction $E$ .

One of the key points justifying the use of this variant in the construction of CROSS is the group isomorphism

$(E^n,\, \star) \;\cong\; (\mathbb{F}_z^n,\, +),$

where $\star$ denotes component-wise multiplication. Every restricted vector $\mathbf{e} = (g^{\bar{e}_1}, \ldots, g^{\bar{e}_n})$ is indeed uniquely described by its exponent vector $\bar{\mathbf{e}} = (\bar{e}_1, \ldots, \bar{e}_n) \in \mathbb{F}_z^n$ , and component-wise multiplication in $E^n$ corresponds to addition in $\mathbb{F}_z^n$ . This correspondence allows the ZK protocol operations to be performed entirely in $\mathbb{F}_z^n$ , where the arithmetic is simple and efficient. Furthermore, the representation of a vector $\mathbf{e}$ is handled entirely through the exponent vector in $\mathbb{F}_z^n$ , enabling a compact representation.

R-SDP(G)

In CROSS, a variant with an additional restriction is also considered. In this case, the solution must belong not to the entire group $E^n$ , but to a proper subgroup $G < (E^n, \star)$ , structured as a linear code in the exponent space. This variant is denoted R-SDP(G).

More precisely, let $M \in \mathbb{F}_z^{m \times n}$ be a public matrix of rank $m < n$ . The subgroup $G$ is defined as the image of the map

$\mathbb{F}_z^m \to E^n, \qquad \bar{\mathbf{u}} \mapsto \mathbf{e} = \Bigl(g^{(\bar{\mathbf{u}} M)_1},\, \ldots,\, g^{(\bar{\mathbf{u}} M)_n}\Bigr),$

where $(\mathbf{x})_i$ denotes the projection onto the $i$ -th coordinate of the vector $\mathbf{x}$ . In other words, the elements of $G$ are the restricted vectors whose exponent vector belongs to the subspace $\operatorname{Im}(M) \subseteq \mathbb{F}_z^n$ . It follows that $|G| = z^m$ .

R-SDP(G) $(n, k, m, p, z)$ :Given $H \in \mathbb{F}_p^{r \times n}$ , a matrix $M \in \mathbb{F}_z^{m \times n}$ of rank $m < n$ , and a syndrome $\mathbf{s} \in \mathbb{F}_p^r$ , find $\mathbf{e}_G \in \mathbb{F}_z^m$ such that, setting $\bar{\mathbf{e}} = \mathbf{e}_G M \in \mathbb{F}_z^n$ and $\mathbf{e} = g^{\bar{\mathbf{e}}} = \bigl(g^{\bar{e}_1}, \ldots, g^{\bar{e}_n}\bigr) \in G \subset \mathbb{F}_p^n$ ,

$\mathbf{e} H^\top = \mathbf{s}.$

The advantage of this approach concerns the use of the isomorphism $G \cong \mathbb{F}_z^m$ with $m < n$ , which allows an even more compact representation of restricted vectors. However, the additional algebraic structure can be exploited by an adversary to mount more efficient collision attacks, requiring a more careful parameter analysis.

CROSS

CROSS follows the classical paradigm of identification-scheme-based signatures: a hard problem is defined as a relation, a zero-knowledge identification protocol is built upon it, and it is converted into a non-interactive signature via the Fiat-Shamir transform. For further details on the structure of such constructions, we refer to the article on multivariate signatures based on identification schemes.

Key Generation

In identification protocols, the starting point is the definition of a relation $\mathcal{R} \subseteq \mathcal{X} \times \mathcal{W}$ associated with a hard problem: a set of pairs $(x, w)$ where $x$ is called the statement and $w$ is called the witness. The statement is public and describes the problem instance; the witness is secret and constitutes its solution. The goal of the protocol is for the prover to convince the verifier of knowing a valid witness for the public statement, without revealing it.

In the case of CROSS, the relation is that of R-SDP (resp. R-SDP(G)): the statement is the pair $(\mathbf{s}, H)$ specifying the problem instance, while the witness is the restricted vector $\mathbf{e} \in E^n$ (resp. $G$ ) that solves it. This translates directly into the public/private key pair.

The 5-Round Identification Protocol

The protocol underlying CROSS is a 5-round identification protocol. The high-level structure between the prover (P) and the verifier (V), illustrated in the figure below, is as follows.

Commit (P $\to$ V): The prover randomly chooses $\mathbf{e}' \in G$ and $\mathbf{u}' \in \mathbb{F}_p^n$ . It then computes the transformation $\mathbf{v} \in G$ such that $\mathbf{v} \star \mathbf{e}' = \mathbf{e}$ and sets $\mathbf{u} = \mathbf{v} \star \mathbf{u}'$ . The prover then computes the cryptographic commitments $c_0 = \operatorname{Hash}(\mathbf{u}H^\top, \mathbf{v})$ associated with the syndrome $\mathbf{u}H^\top$ and the transformation $\mathbf{v}$ , and $c_1=\operatorname{Hash}(\mathbf{e}', \mathbf{u}')$ associated with the random values $\mathbf{e}'$ and $\mathbf{u}'$ .
First challenge (V $\to$ P): The verifier sends $z \xleftarrow{$} \mathbb{F}_p^*$ , a scalar challenge over the entire multiplicative group of $\mathbb{F}_p$ .
Response (P $\to$ V): The prover computes and sends the response $\mathbf{y} = \mathbf{u}' + z \cdot \mathbf{e}' = \mathbf{v}^{-1}\star(\mathbf{u} + z \cdot \mathbf{e}).$
Second challenge (V $\to$ P): The verifier sends a binary challenge $b \xleftarrow{$} \{0, 1\}$ .
Opening (P $\to$ V): If $b=0$ , the prover reveals $\mathbf{v}$ ; if $b=1$ , the prover reveals the random elements $\mathbf{e}'$ and $\mathbf{u}'$ .
Verification (V): If $b=0$ , the verifier can check $c_0$ by computing $\operatorname{Hash}((\mathbf{v} \star \mathbf{y})H^\top - z \cdot \mathbf{s}, \mathbf{v})$ since $\mathbf{v} \star \mathbf{y} = \mathbf{u} + z\cdot \mathbf{e}$ . If $b=1$ , the verifier can check $c_1$ by computing $\operatorname{Hash}(\mathbf{e}', \mathbf{u}')$ and subsequently verify that $\mathbf{y}$ was computed honestly.

The protocol satisfies the security properties required to be converted into a digital signature. In particular, it is zero-knowledge (there exists a public algorithm that produces indistinguishable transcripts without knowing $\mathbf{e}$ ) and it is sound (a dishonest prover cannot convince the verifier except with bounded probability). The soundness error in a single execution is $\frac{p}{2(p-1)}$ . To achieve the required security level, the protocol is repeated in parallel, applying several optimizations capable of reducing the overall size of the transmitted proof.

Finally, the Fiat-Shamir transform is applied to the protocol, where the two verifier challenges are replaced by values derived via hashing the message to be signed and the partial transcript.

Simplified diagram of the 5-round identification protocol underlying CROSS (single execution).

Performance

CROSS is submitted to NIST in two main variants, based on R-SDP and R-SDP(G) respectively, each available in three configurations (fast, balanced, small) that trade off signature size and execution speed. The following charts compare the balanced variant of CROSS with the already standardized post-quantum schemes and with two classical non-post-quantum references. All parameters are chosen within Category I of the security levels defined by NIST.

The fast variant of CROSS has signatures between 12 and 18 kB; the small variant reaches 9.0 kB for CROSS-RSDP(G)-s and 12.4 kB for CROSS-RSDP-s, at the cost of execution times 3–4 times higher. In both families, R-SDP(G) is always more compact and faster than R-SDP, thanks to the compressed representation of the witness in $\mathbb{F}_z^m$ with $m < n$ .

The charts highlight how CROSS achieves extremely compact public keys (54–77 B), at the cost of signatures on the order of 9–18 kB for Category I. The latter are significantly larger than ML-DSA but comparable to SLH-DSA. On the other hand, the signing and verification times of the balanced variant fall within a competitive range, being much more efficient than SLH-DSA-128s.

The relevance of CROSS also lies in the underlying problems, whose cryptographic foundations are completely disjoint from the already standardized schemes. However, R-SDP remains a relatively recent problem compared to LWE and the symmetric primitives on which ML-DSA and SLH-DSA are built. Furthermore, the reference implementation presents a non-negligible memory footprint² on highly resource-constrained embedded devices. The NIST second-round evaluation process is still ongoing and will determine its fate towards possible standardization.

https://www.cross-crypto.com/↩︎
The total amount of memory (RAM and/or Flash) occupied by a program during its execution.↩︎

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The author

Edoardo Signorini, Cryptography Specialist at Telsy, where he has been part of the Cryptography Research Group since 2020. He received his PhD in Pure and Applied Mathematics from the Polytechnic University of Turin in 2024 with a thesis on Post-Quantum Digital Signature Aggregation. His work focuses on research in the area of Post-Quantum Cryptography and the analysis and development of cryptographic protocols.