arXiv CSopen access

Digital signature schemes based on code equivalence and syndrome decoding from restricted errors

arXiv:2606.31601v1 [cs.CR] 30 Jun 2026

Digital signature schemes based on code equivalence and syndrome decoding from restricted errors * Sarah Arpin Hiram H. López

Jason T. LeGrow Gretchen L. Matthews

Abstract— Digital signature schemes are an important cryptographic tool to ensure data authenticity and integrity in many applications that must be resilient to attacks, including those facilitated by quantum computers. We consider the two digital signature schemes based on error-correcting codes that are second-round candidates in NIST’s call for Additional Signature Schemes, which is part of the Post-Quantum Cryptography Standardization Process. Specifically, we provide an overview of the Codes and Restricted Objects Signature Scheme (CROSS) and the Linear Equivalence Signature Scheme (LESS). We describe their underlying problems of syndrome decoding from restricted errors and code equivalence. We review sigma protocols and how they can be transformed into digital signature schemes via the Fiat-Shamir transform. Finally, we explain how this procedure yields code-based digital signatures believed to be post-quantum secure.

from the internet to blockchain (Table I). Given recent advances in quantum computing, which include period-finding algorithms (e.g., Shor’s Algorithm [30]) and search algorithms that demonstrate quantum speedup (e.g., Grover’s algorithm [17]), digital signatures must remain secure even against attacks enabled by the most modern or emerging technologies. In this work, we discuss recent developments in using error-correcting codes to design digital signature schemes believed to be quantumsafe, meaning they are resilient against attacks from both classical and quantum algorithms. In particular, we focus on the two code-based digital signature schemes being considered by the National Institute of Standards and Technology (NIST) in the second round of Additional Signature Schemes [24], which is part of the Post-Quantum Cryptography Standardization Process [23]. Coding theory and cryptography evolved largely in parallel, with error-correcting codes enabling reliable transmission over noisy channels and cryptosystems protecting data from unauthorized parties. Their intersection emerged with the public-key proposals of McEliece [20] and Niederreiter [25], which exploit noise, code structure, and decoding to achieve secure communication. Despite this promise, code-based schemes were not incorporated into international standards, largely due to their large key sizes and the availability of more efficient alternatives such as RSA [28], elliptic curve cryptography, and Diffie–Hellman [12]. Consequently, code-based schemes were long viewed as theoretically appealing but less practical than competing implementations. Post-quantum (also called quantum-safe or

I. I NTRODUCTION This article focuses on digital signature schemes based on error-correcting codes. Digital signatures are much like handwritten signatures but designed for technology. They support authentication, ensuring data origin; integrity, confirming that data has not been tampered with or modified; and accountability, also called non-repudiation, so that parties cannot later deny having sent or signed a message. Digital signatures underpin applications * The authors are with the Department of Mathematics, Virginia Tech (email: {sarpin, jlegrow, hhlopez, gmatthews}@vt.edu). The National Science Foundation partially supported the third (DMS-2401558 and 2502705) and fourth (DMS-2201075 and 2502705) authors. All four authors are partially supported by the Commonwealth Cyber Initiative.

1

Domain

Common Uses & Examples

Purpose

Blockchain

Transaction signing, wallets, and smart contract authorization. PDF signing, time-stamping authorities, and long-term validation. E-banking approvals, e-commerce payments, and transaction receipts. Secure boot, signed firmware updates, and device attestation. Contracts and agreements, tax filing, and digital notarization. Email (S/MIME), secure messaging, and digitally signed documents. Code signing, package signing, and firmware validation. TLS/HTTPS certificates, server/client authentication, and API trust.

Authorization of on-chain state changes.

Documents Finance & Transactions IoT / Embedded Systems Legal & Government Secure Communication Software & Content Web Security

Trusted timestamps and embedded revocation data. Non-repudiation and hardware tokens. Execution integrity, supply-chain security, and key protection. Regulatory compliance frameworks, qualified signatures, and audit trails. Certificates, message integrity, and signer authentication. Package manager signatures, verify publisher identity, and content integrity. PKI, certificate chains, and binding public keys to identities.

TABLE I: Common uses and purposes of digital signatures.

quantum-resistant) cryptosystems are designed to withstand attacks by both classical and quantum algorithms. In 1994, Shor introduced a quantum algorithm [30] that runs in polynomial time for integer factorization and for discrete logarithms (including the elliptic-curve variant), implying that widely deployed schemes such as RSA, Diffie–Hellman, and elliptic curve cryptography are not post-quantum. These results motivate new public-key primitives and have renewed interest in code-based constructions, where error-correcting codes remain among the most promising tools for post-quantum cryptography. Much of code-based cryptography targets key encapsulation mechanisms (KEMs) that let two parties establish a shared secret despite eavesdroppers, enabling secure communication. Several proposals—including Classic McEliece [1] and BIKE [2]—follow the McEliece/Niederreiter paradigm of hiding a structured, efficiently decodable code, while HQC [21] instead relies on syndrome decoding and was selected by NIST for standardization. The motivation for this expository paper is multifold. First, there is an urgency to transition to quantum-safe cryptography and infrastructure, given new requirements and recommendations such as those from the White House and the European Commission. The National Institute of Standards

Classical Digital Signatures

Post-Quantum Digital Signatures

mathematics underpinning security

mathematics underpinning security

RSA

Dilithium, Falcon

Integer Factorization

Module Learning with Errors / Lattices

DSA Discrete Logarithm Problem

Unbalanced Oil and Vinegar (UOV) Multivariate Polynomial Systems

ECDSA/EdDSA Elliptic Curve Discrete Logarithm Problem

CROSS Restricted Syndrome Decoding

LESS, MEDS Code Equivalence

Fig. 1: Examples of digital signature schemes.

and Technology (NIST) recommends transitioning by 2030 and requires it by 2035 [22]. Most current digital signatures are created using classical protocols such as those shown in Figure 1. Second, digital signature schemes are ubiquitous, and our digitally connected world, computing systems, and critical infrastructure relies on them. They support secure network communications, authentication of software and firmware updates, and control command verification and data within mission-critical cyber-physical systems. Third, this topic opens new problem spaces in which individuals with interests 2

3) Signing: Given a secret key, corresponding public key, and a message, outputs a signature on the message. 4) Verification: Given a public key, a message, and a signature, either accepts or rejects the validity of the signature.

in information theory and related topics may play a role. As most code-based cryptography literature focuses on public-key encapsulation mechanisms, we concentrate on code-based signature schemes. This article aims to fill a gap in the literature, providing a new point of entry for those curious about how error-correcting codes are used in digital signature schemes. We focus on code-based digital signatures, showcasing those that remain as candidates in Round 2 of NIST’s Standardization Process for Additional Digital Signatures, namely the Codes and Restricted Objects Signature Scheme (CROSS) [5] and the Linear Equivalence Signature Scheme (LESS) [7]. It is worth noting that NIST is specifically interested in signature schemes that are not based on structured lattices, likely because the lattice-based schemes CRYSTALS-Dilithium [13] and FALCON [27] have been approved for standardization. In the next section, we review digital signature schemes and zero-knowledge proofs followed by how they are used to provide digital signatures via the Fiat-Shamir transform. We survey the Restricted Syndrome Decoding Problem and the digital signature scheme CROSS. This is followed by an overview of the digital signature scheme LESS, which is based on the code equivalence problem. The article concludes with a brief summary.

The process and role of the public and private keys are illustrated in Figure 2. Here, signer Alice holds the private (secret) key skA , which is associated with the public key pkA ; anyone can access the public key, while only Alice knows the private key. Alice signs message m using her private key skA , resulting in signature σ . Then Bob (or any other verifier) may use the message-signature pair (m, σ) and Alice’s public key pkA to confirm the message was signed by Alice. The security here is based on the fact that an unauthorized party, such as Eve in Figure 2, cannot determine the private key from knowledge of the public key. Suppose that Eve has another message m′ that she wishes to pass off as sent (signed) by Alice. In this case, Eve shares (m′ , σ ′ ) with Bob, who accepts that pair as sent by Alice if Eve is able to use skA to sign it. Otherwise, Bob rejects the pair. We require signature schemes to be correct, meaning that if the signer follows the protocol honestly, then the verifier accepts the resulting signature. The typical security notion is existential unforgeability under chosen-message attack (EUFCMA), which intuitively states that an adversary who sees a number of valid message-signature pairs cannot produce a signature for a new message. Zero-knowledge protocols are used to convince an entity that a statement is true without revealing any additional information. As an albeit overly simplified example, consider a safe with an oldfashioned rotary (or dial) lock for which Alice knows the combination. Bob can challenge Alice by locking it and rotating the dial. She can demonstrate to Bob that she knows the combination by showing him the unlocked safe. Bob can repeat the challenge by rotating the dial to different locations, and equipped with the combination, Alice can unlock it. Each time, she shows Bob the unlocked safe. He is then convinced that Alice knows the lock combination, yet he has no knowledge of

II. D IGITAL S IGNATURE S CHEMES AND Z ERO - KNOWLEDGE P ROTOCOLS Digital signatures are used primarily for: • Data Integrity, ensuring that messages are not tampered with in transit between parties; • Data Origin Authentication, verifying the sender of a message; and, • Non-Repudiation, guaranteeing that a user cannot later deny having signed a message. Formally, a digital signature scheme is a cryptographic protocol with the following components: 1) Public parameter generation: Given a security parameter λ, outputs public parameters. 2) Key generation: Given public parameters, outputs a private (signing) key and a public (verification) key. 3

Alice (signer)

Sign with Private Key skA

Bob (verifier)

(m, σ) Verify with Public Key pkA

Eve (quantum-equipped adversary)

(m′ , σ ′ ) (forged)

Accept

Reject Forged (m′ , σ ′ )

Genuine (m, σ)

Fig. 2: Signing and verification with forgery attempt; valid signatures verify and forgeries fail.

the combination itself. Zero-knowledge protocols employ mathematics to achieve this phenomenon of demonstrating knowledge without revealing the knowledge. Protocols should satisfy the properties found in Table II. In Section III, we explain how zero-knowledge protocols can provide digital signature schemes. Property

Description

Completeness

✓ Verifier accepts a true statement with high probability. ✗ Dishonest prover cannot make the verifier accept a false statement, except with small probability. ♣ Verifier has no information beyond the veracity of the statement.

Soundness

Zero-Knowledge

Commitment comm Challeng e

Bob (verifier)

chal

e resp chal Respons

Alice (prover)

Verification: accept/reject

Fig. 3: Sigma-protocol depicting Alice using skA to generate commitment comm, followed by Bob sharing a challenge chal, after which Alice provides a response respchal using skA that Bob can then verify using Alice’s public key pkA leading to acceptance or rejection.

Round 1 Additional Signatures incorporate the FiatShamir transform, including CROSS and LESS, the code-based schemes discussed in this article. The Fiat-Shamir transform modifies the sigma protocol to construct a digital signature scheme in two key ways: Parallel repetition: 1 The prover constructs κ commitments comm1 , . . . , commκ for some integer κ and sends them to the verifier, who then sends κ challenges chal1 , . . . , chalκ to the prover. The prover constructs κ responses respchal1 , . . . , respchalκ . The verifier accepts the proof (signature) if each of the κ transcripts {(commi , chali , respi )}κi=1 is accepted.

TABLE II: Zero-knowledge protocol properties, assuming honest prover.

III. S IGMA P ROTOCOLS AND THE F IAT-S HAMIR T RANSFORM The Fiat-Shamir transform [14] turns interactive zero-knowledge protocols into practical digital signature schemes; in particular, it converts a sigma protocol into a digital signature scheme. A sigma protocol is an interactive protocol between two parties—the prover P and the verifier V—in which the prover convinces the verifier that she knows a piece of secret information, without revealing the actual secret information. See Figure 3 for a sketch. More than one-third of the submissions to NIST’s

1

Parallel repetition is not soundness-amplifying for arbitrary interactive arguments, but it is for the type used here [3].

4

IV. D IGITAL S IGNATURE S CHEME BASED ON R ESTRICTED S YNDROME D ECODING

Commitment (comm1 , . . . , commκ )

Bob

(respchal1 , . . . , respchalκ )

Alice Syndrome decoding has been used as a decoding technique for linear codes since the early 1950s, dating back nearly to the beginning of coding theory [18]. In the 1970s, Berlekamp, McEliece, and van Tilborg [6] proved that decoding a random linear code in the Hamming metric is NP-complete. The hardness of syndrome decoding is integral to several code-based KEMs, including McEliece and HQC, though each considers a particular family of codes (binary Goppa for McEliece and binary quasi-cyclic for HQC). CROSS modifies the Syndrome Decoding Problem (SDP), to be stated shortly, and uses it in a novel way to provide a new digital signature scheme. We explore this variant of the SDP and then the signature scheme.

(prover)

(verifier) Verification: accept/reject

Fig. 4: The Fiat-Shamir transform reduces the interactivity of a sigma protocol. Alice uses skA to generate commitments commi , i ∈ [κ], and then hashes to generate challenges chali , i ∈ [κ]. Bob then verifies using Alice’s public key pkA , leading to acceptance or rejection and reducing the communication between Alice and Bob.

De-interactivization: Using a cryptographic hash function H , the prover constructs the challenge herself as (chal1 , . . . , chalκ ) = H(comm1 , . . . , commκ , m),

A. Restricted Syndrome Decoding As all codes considered in this article are linear, we use the term “code” to mean linear code. An [n, k] linear code C over the alphabet Fq , meaning the finite field with q elements, is an Fq -linear subspace of Fnq . Let Fm×n be the set of m × n q matrices with entries in Fq . For an [n, k] code C , (n−k)×n there exists a parity check matrix H ∈ Fq with the property that x ∈ C if and only if xH T = 0. The Hamming weight of a vector v = (v1 , . . . , vn ) is the number of nonzero entries, wt(v) = | {i : vi ̸= 0} |. The syndrome of a vector . A x ∈ Fnq (with respect to H ) is xH T ∈ Fn−k q code whose minimal nonzero codeword weight is d is said to have minimum distance d and is able to correct any t errors, provided d ≥ 2t + 1. Indeed, given a received word w = c + e ∈ Fnq with c ∈ C , it follows that w and e have the same syndrome. A solution to the Syndrome Decoding Problem allows one to determine the error vector e and recover the original codeword c if C has minimum distance at least 2t + 1. Notice that (1) and (2) give a linear and a nonlinear constraint, respectively. We see below that (2) is replaced in the Restricted Syndrome Decoding Problem (RSDP).

where m is the message being signed. If the original protocol has a challenge space of size S , after parallel repetition, the protocol remains 2-special sound, while the challenge space size increases to S κ , meaning that the soundness error is reduced from S −1 to S −κ . Thus, it suffices to 128 192 take κ = log (respectively, log , 256 for NIST 2c 2 c log2 c Level I (respectively, Level III, Level V) security.2 De-interactivization then transforms the soundnessamplified sigma protocol into a digital signature scheme as described in Figure 4. In the next two sections, we see how the FiatShamir transform gives rise to two new digital signature schemes, each based on a different perspective. In Section IV, we consider CROSS, which exemplifies a syndrome-decoding–style approach. Later, in Section V, we consider equivalence-based designs (LESS/MEDS) that trade different forms of structure for different size and performance profiles. 2 This is in contrast with the classical Schnorr protocol [29], which does not require parallel repetition because it naturally has exponentially-small soundness error.

5

at most polynomial (e.g., square-root) rather than exponential; accordingly, CROSS parameters are selected to resist both classical and quantum variants. Overall, CROSS assumes average-case hardness of (restricted) syndrome decoding for random linear codes over finite fields. Notice that if E = Fnq , then the RSDP is the classical SDP. We now define a set that plays a crucial role in CROSS. Take  E := g i : i ∈ [z] ⊂ F∗p ,

Syndrome Decoding Problem (SDP) (n−k)×n

Given a parity-check matrix H ∈ Fq , n with s ∈ Fn−k , and t ∈ [n] , find e ∈ F q q syndrome s = eH T (1) and weight wt(e) ≤ t.

(2)

where F∗p represents the multiplicative group, z is a prime that divides p − 1, and g ∈ F∗p is of order z . When we take E = En , the RSDP is NP-complete [8]. In this case, the RSDP is expected to have at most one solution if log2 (z) ≤ (1 − Rate) log2 (p), where Rate represents the rate of the code whose parity check matrix is H . Observe that En , under componentwise multiplication, is a commutative group isomorphic to Fnz , viewed as n-tuples of integers modulo z under componentwise addition, via the map En → Fnz

Restricted Syndrome Decoding Problem (RSDP) (n−k)×n

Given a parity-check matrix H ∈ Fq , n , find e ∈ Fn with s ∈ Fn−k , and E ⊆ F q q q syndrome s = eH T (3) and e ∈ E.

(4)

g = (g i1 , . . . , g in ) 7→ ℓ(g) = (i1 , . . . , in ).

B. CROSS

Such a representation enables CROSS to perform arithmetic faster and to compactly represent an element in En . We now take G ≤ En to be a multiplicative subgroup given by (m ) Y ui G = ⟨a1 , . . . , am ⟩ = ai : ui ∈ [z] ,

CROSS is based on the RSDP with a restricted error set E , and improves on the SDP in two main respects. First, RSDP can permit higher-weight errors while still yielding a unique solution, which increases the cost of information-set decoding (ISD) attacks; consequently, smaller RSDP instances may achieve the same security level as larger SDP instances. Second, when componentwise multiplication acts transitively on the restricted vectors, the restriction can also reduce communication. CROSS is expected to be quantum-secure because it relies on code-based hardness assumptions rather than number-theoretic problems vulnerable to Shor’s algorithm. Its security reduces to the hardness of solving RSDP (and a subgroup variant) over random linear codes [5]. The underlying Syndrome Decoding Problem is NP-complete [6] and underlies long-standing post-quantum schemes such as Classic McEliece. The best known attacks on SDP/RSDP are ISD-style algorithms and refinements, for which known quantum improvements are

i=1

for some a1 , . . . , am ∈ En and m < n. The RSDP(G), which is still NP-hard, is defined as the RSDP with E = G. The RSDP(G) is expected to have a unique solution provided |G|p−(1−R)n ≤ 1. The CROSS signature scheme is obtained after applying the Fiat-Shamir transform on t parallel executions of the following zero-knowledge protocol. Public parameters: G ≤ En (n−k)×n

Public keys: H ∈ Fp , and s = eH T . Private key: e ∈ G. Commitment phase: The prover samples Seed uniformly at random from {0, 1}λ . Then, through a deterministic cryptographically secure pseudorandom generator, she makes the following samples: 6



 ′ ′ Seed(u ) , Seed(e ) from {0, 1}2λ with initializa-

V. D IGITAL S IGNATURE S CHEMES BASED ON C ODE E QUIVALENCE A. The Code Equivalence Problem It is natural to ask when two mathematical objects are essentially the same. Perhaps the earliest reference to this notion for codes is Golay’s work [15], in which codes are considered up to coordinate relabeling. The concept was then formalized in MacWilliams’ dissertation [19] to the notion we now call code equivalence, to be defined shortly. Code equivalence made its appearance in cryptography in the late 1970s with the work of Berlekamp, McEliece, and van Tilborg [6]. The code equivalence decision problem asks if two codes are the same up to a weight-preserving isomorphism (for instance, a coordinate permutation). It was shown in the late 1990s that the graph isomorphism problem can be reduced to the code equivalence problem in polynomial time [26]. Babai demonstrated a quasipolynomial-time algorithm for the graph isomorphism problem [4], but it is still unknown whether either problem admits a polynomial time algorithm. When considering code equivalence between two codes, a necessary condition is that both codes have the same parameters or the same weight enumerators. However, it is not always easy to determine these values. For instance, for the small example in Figure 5, it is feasible to see that the two codes are identical up to interchanging two coordinates because the codes are short (length 3) with only 4 codewords. As we see below, the inability to quickly identify large codes that are the same up to relabeling (for instance) underpins some digital signature schemes. Let C0 , C1 ⊆ V be two codes in the same ambient space V over the field Fq with weight function wt—we take V = Fnq with the Hamming weight and V = Fn×m with the rank weight for LESS and MEDS, respectively; this formalism applies to any weighted vector space over Fq . An isomorphism from C0 to C1 is a function ψ : V → V that is: • linear, i.e. ∀a, b ∈ Fq , x, y ∈ V we have

′ tion Seed, u′ from Fnp with initialization Seed(u ) , (e′ ) ′

and e from G with initialization Seed . She computes σ ∈ G such that3 σ(e′ ) = e. Define u = σ(u′ ) and compute s̃ = uH T . She constructs the commitment as (c0 , c1 ) = (Hash(s̃, σ), Hash(u′ , e′ )),

and sends it to the verifier. Challenge phase 1: The verifier samples a challenge β uniformly at random from F∗p , and sends it to the prover. Response phase 1: The prover computes y = u′ + βe′ and sends h = Hash(y) to the verifier. Challenge phase 2: The verifier samples a challenge b uniformly at random from {0, 1}, and sends it to the prover. Response phase 2: The prover constructs ( (y, σ) if b = 0 f= Seed if b = 1 and sends it to the verifier. Verification: The verifier checks the following. If b = 0, he computes ỹ = σ(y) and s̃ = ỹH T − βs. Thus, ỹ = σ(y) = σ(u′ ) + σ(βe′ ) = u + βe and s̃ = ỹH T − βs = uH T + βeH T − βs = uH T .

He accepts if Hash(y) = h, Hash(s̃, σ) = c0 , and σ ∈ G. If b = 1, he uses the deterministic cryptographically secure pseudorandom generator   (u′ ) (e′ ) to sample Seed , Seed from {0, 1}2λ with initialization Seed. Compute y = u′ + βe′ . He accepts if Hash(y) = h and Hash(u′ , e′ ) = c1 . This zero-knowledge protocol is a type of 5pass identification scheme called a q2-Identification scheme, with q = p − 1, because the first challenge can take q different values, while the second can take only 2 (0 or 1). In particular, CROSS is a variant of the 5-pass identification scheme first introduced by [10], which implies that CROSS achieves a level of security known as EUF-CMA.

ψ(ax + by) = aψ(x) + bψ(y),

3

As the element σ ∈ G gives rise to a bijection G → G, we denote the product σe′ as σ(e′ ) because the same bijection is used later.

• weight-preserving, i.e.,

wt(ψ(x)) = wt(x) ∀x ∈ V,

7

and

• maps C0 to C1 , i.e.,

Public and private keys: The prover’s public key is a pair of RREF generator matrices (G0 , G1 ) with G1 ∈ LG0 . The prover’s secret key is A ∈ Aut(V ) such that G1 = rref(G0 A). Commitment phase: The prover samples R uniformly at random from Aut(V ), and constructs the commitment as comm = rref(G0 R). She sends comm to the verifier. Challenge phase: The verifier samples a challenge chal uniformly at random from {0, 1}, and sends it to the prover. Response phase: The prover constructs ( R if chal = 0 resp = A−chal R = −1 A R if chal = 1

ψ(C0 ) = {ψ(x) : x ∈ C0 } = C1 .

When there is an isomorphism from C0 to C1 , we say that C0 and C1 are isomorphic (or equivalent). Computational Code Equivalence Problem Given two equivalent codes C0 and C1 , find an isomorphism ψ from C0 to C1 . Computational code equivalence is the hard problem that underlies both LESS and MEDS. The difficulty of the problem depends heavily on the parameters and features of the codes being considered, as well as on the representation of the codes C0 and C1 . The standard approach is to use the reduced row echelon form (RREF). In particular, if C0 ⊆ Fnq is a code of dimension k , then C0 can be written as the row span of a k × n generator matrix G0 .4 Two generator matrices G0 , G′0 will generate the same code C0 if and only if they are row equivalent, and it follows that C0 can be represented by a unique RREF generator matrix. For a given matrix G, we denote by rref(G) its reduced row echelon form. For any linear map ψ : V → V , there exists a matrix representation Aψ of ψ with respect to the standard basis. In particular, Aψ is defined by ψ(x) = xAψ ∀x ∈ V . If G0 is the RREF generator matrix for C0 , then rref(G0 Aψ ) is the RREF generator matrix for C1 = ψ(C0 ). This gives a convenient way to formulate code equivalence in terms of RREF generator matrices: the codes generated by G0 and G1 are equivalent if and only if there is a matrix A such that G1 = rref(G0 A) and which is weight-preserving on the ambient space. We denote by Aut(V ) the set of all such matrices, called the automorphism group of (V, wt).

and sends it to the verifier. Verification: The verifier checks that ( rref(G0 resp) = comm if chal = 0 rref(G1 resp) = comm if chal = 1 which we write more compactly as rref(Gchal resp) = comm. We call a triple τ = (comm, chal, resp) a transcript, and we say that a transcript is accepting if it would result in V accepting the proof; equivalently, if rref(Gchal resp) = comm.

The public information consists of G0 and G1 while the secret key is A; thus, for security, we require that it must be difficult to recover any A′ such that G1 = rref(G0 A′ ) given G0 and G1 . To transform this protocol into a correct and secure digital signature scheme, it must satisfy three correctness and security conditions: Perfect Correctness: If the protocol is executed honestly, then V will accept the proof. 2-Special Soundness: There must be an efficient algorithm Ext—the extractor—which, on input two accepting transcripts

B. Digital Signatures from Code Equivalence At a high level, LESS and MEDS are built from a sigma protocol in the following framework. Public parameters: All users agree on an ambient space V with weight function wt.

τ0 = (comm, 0, resp0 ), and τ1 = (comm, 1, resp1 )

with the same commitment, outputs a witness A′ = Ext(τ0 , τ1 ) such that G1 = rref(G0 A′ ). Honest Verifier Zero-Knowledge: There must exist an efficient algorithm Sim that, given G0 and

4

While this discussion applies to LESS directly, some extra work is required for MEDS—see Section V-D.

8

G1 (but not A) produces an accepting transcript τ = (comm, chal, resp). Moreover, the distribution of transcripts obtained from Sim must be identical to the distribution of transcripts output by honest interactions between P and V. Intuitively, 2-special soundness ensures that any prover convincing the honest verifier with probability greater than 21 knows a corresponding witness (secret key). Honest-verifier zero-knowledge ensures the verifier learns nothing about that secret when interacting with a knowledgeable prover. Both properties are verified directly; see, for example, LESS [7, Section 4] and MEDS [11, Section 4].

Scaling coordinates: For λ = (λ1 , . . . , λn ), x = (x1 , . . . , xn ) ∈ Fnq , define the Hadamard product λ ◦ x = (λ1 x1 , . . . , λn xn ). If λ ∈ (F∗q )n , then wt(λ ◦ x) = wt(x) for any x. Permuting coordinates: For any permutation σ in the symmetric group Sn , define σ ∗ x = (xσ−1 (1) , xσ−1 (2) , . . . , xσ−1 (n) ). Then, wt(σ ∗ x) = wt(x) for all x ∈ Fnq . According to the MacWilliams Theorem on Equivalence of Codes [9, Theorem 1], these maps are essentially the only weight-preserving linear transformations of Fnq with the Hamming metric. Thus, any such map ψ can be written as ψ : x → σ∗(λ◦x) for some λ ∈ (F∗q )n and some σ ∈ Sn . Such a map ψ has matrix representation Aψ = DP where D is the diagonal matrix with Dii = λi ∀i ∈ [n], and P is the permutation matrix of σ : n X P = eσ(i) eTi .

C. LESS: Linear Equivalence Signature Scheme In this section, we describe LESS, a signature scheme based on (linear) code equivalence, and we occasionally reference MEDS, a closely related construction based on matrix code equivalence, for brief points of comparison. A detailed treatment of MEDS is deferred to Section V-D. LESS takes V = Fnq with the Hamming weight wt(x) = |{i ∈ [n] : xi ̸= 0}|, and considers codes C ⊆ Fnq of dimension k .

i=1

A matrix of the form A = DP is called a monomial matrix, and the collection of n × n monomial matrices over Fq is denoted Monn (Fq ). When wt is the Hamming weight, Aut(Fnq , wt) = Monn (Fq ). D. MEDS: Matrix Equivalence Digital Signature In MEDS, the ambient space is V = Fn×m , and the weight function is the rank: wt(X) = rank(X). A linear map ψ : Fn×m → Fn×m can be written as

2

ψ(X) = A1 XB1 + A2 XB2 + · · · + At XBt

1

for some t ≤ (nm)2 . Naturally, these maps will generally not be weight-preserving on Fn×m . It is known that the only such maps that preserve rank take the form ψ(X) = AXB, or ψ(X) = AX T B for some A ∈ GLn (Fq ) and B ∈ GLm (Fq ), and moreover that the second case is possible only when n = m [16, Theorem 1.3]. Following the MEDS specification, we will consider only maps of the first kind. Thus, the isomorphisms of codes take the form C0 7→ C1 = AC0 B for invertible A and B of the correct size. To make this formulation of MEDS compatible with our generic description in Section V-B, we need a generator matrix formulation of code equivalence for matrix codes C0 ⊆ Fn×m . The standard

0 2 1 0 0

1

2

Fig. 5: Two equivalent linear codes over F3 . In blue, the code C0 is generated by (1, 0, 0) and (0, 1, 1). In red, the code C1 is generated by (0, 1, 0) and (1, 0, 1). These codes are equivalent: C1 is obtained from C0 by exchanging the first and second coordinates. Points in purple are common to both codes. Two kinds of linear maps that preserve this weight are 9

approach is to vectorize the code: for X ∈ Fn×m , we define vec(X) to be the vector obtained from X by concatenating its rows: vec(X) = [x1 , . . . , xn ]. The vectorization of a code C0 ⊆ Fn×m is

P:

(G0 , . . . , GS−1 ), (A1 , . . . , AS−1 )

R ←$ Aut(V ) comm ← rref(G0 R)

! V : G0 , G1 , . . . , GS−1 comm

−−−→ chal

←−− chal ←$ {0, 1, 2, . . . , S − 1}

vec(C0 ) = {vec(X) : X ∈ C0 } ⊆ Fnm q . resp ← A−1 chal R

If {X1 , . . . , Xk } is a basis for C0 , then {vec(X1 ), . . . , vec(Xk )} is a basis for vec(C0 ), which we can arrange as the rows of a matrix and row reduce, yielding an RREF generator matrix G0 for vec(C). This vectorization interacts nicely with code equivalence. We have the identity

resp

−−→

Accept if rref(Gchal resp) = comm

Fig. 6: The sigma protocol incorporating multiple public keys. Here, A0 = I , the identity matrix.

2) Exploiting Commitment Recoverability: Commitment recoverable schemes are such that given a public key (G0 , G1 ) and a challenge/response pair (chal, resp), there is an efficient algorithm that recovers the unique accepting commitment comm. In LESS and MEDS, we must have comm = rref(Gchal resp). This enables a straightforward optimization of the protocol: the signature will instead consist of the challenge string and re−−→ −→ sponse vector: σ = (chal, − resp). During verification, the verifier will reconstruct the commitment vector using the signature, recompute the challenge by hashing the reconstructed commitment vector and message, and accept the proof if and only if the hash output is equal to the challenge component of the signature as depicted in Figure 7. The commit-

vec(AXB) = vec(X)(AT ⊗ B)

where ⊗ is the Kronecker product, defined by   a11 B a12 B · · · a1ℓ B  . .. ..  .. . A⊗B = . . .   .  ak1 B ak2 B · · · akℓ B when A = (aij )1≤i≤k . Hence, if G0 is the RREF 1≤j≤ℓ

generator matrix for C0 , then G1 = rref(G0 (AT ⊗ B)) is the RREF generator matrix for vec(AC0 B). E. Implementation Details LESS and MEDS feature optimizations to improve signing time and signature size. In this section, we detail a number of these optimizations. 1) Multiple Public Keys: To reduce the number of repetitions required, we can increase the challenge space size by increasing the number of codes in the public key. We fix an integer S ≥ 2 and define the secret key as a tuple (A1 , . . . , AS−1 ) ←$ Aut(V )S−1 with corresponding public key (G0 , G1 , . . . , GS−1 ), where Gi = rref(G0 Ai ). Then, we adapt the sigma protocol as depicted in Figure 6. Since the protocol of Figure 6 now has S possible challenges, its soundness error falls to S −1 . This means that, in order to achieve soundness error 2−λ , it suffices to take κ = logλ S parallel repetitions of 2 the protocol. This optimization decreases signature size and running time, at the cost of increasing public key sizes. Both LESS and MEDS consider S = 2 (corresponding to a single public key), while LESS also proposes parameter sets with S = 4, 8.

Verify′ ((G0 , G1 ); m, σ) 301 :

−−→ −→ parse (chal, − resp) ← σ

302 :

for i = 1, 2, . . . , κ

comm′i ← rref(Gchali respi ) −−→′ −−−→ 304 : chal ← H(comm, m) −−→′ −−→ 305 : if chal ̸= chal 303 :

306 : 307 :

return “Reject” return “Accept”

Fig. 7: The modified verification procedure exploiting commitment recoverability. ment vector consists of κ elements of Aut(V )— requiring approximately κ · (n log2 q + log2 n!) bits for LESS, and κ·(n2 +m2 ) log2 q bits for MEDS— while the challenge vector consists of κ integers 10

between 1 and S , which can be represented in approximately κ log2 S bits. For proposed LESS and MEDS parameter sets, this optimization yields a substantial decrease in signature size. 3) Random Seeds and Constant-Weight Hash Functions: When resp is an element of Aut(V ), it requires approximately n log2 q+log2 n! (for LESS) or (n2 + m2 ) log2 q (for MEDS) bits to represent. A straightforward optimization of the protocol is to send the random seeds for the rounds when chal = 0, rather than the group element R. To keep responses—and thus the final signature—small, it is preferable that the challenge string have low Hamming weight. This can be enforced via a constant-weight hash function H , whose outputs are binary strings of length κ with exactly w nonzero entries. It suffices to choose κ and w with   κ (S − 1)w ≥ 2λ . w

CROSS LESS MEDS

104 103 102 101 100

Level I

Level III

Level V

Fig. 8: Signing time in Mcycles. ·105 1.5

CROSS LESS MEDS

1

Compared to an ordinary hash with codomain {0, 1}κ , achieving the same security typically requires larger κ; in practice, the resulting increase in rounds is outweighed by the signature-size reduction from having more rounds where the response is a seed rather than an element of Aut(V ).

0.5

0

Level I

Level III

Level V

Fig. 9: Public key + signature size in bytes. VI. P ERFORMANCE C OMPARISON All three code-based digital signatures are based on novel underlying assumptions and feature a variety of performant parameter sets for varied use cases. The concrete security of the underlying problems remains an important direction for future research.

Figures 8 and 9 compare the signing time and (public key + signature) sizes for CROSS, LESS, and MEDS at NIST security levels I, III, and V.5 VII. C ONCLUSION This article provided an overview of modern code-based digital signatures based on restricted syndrome decoding and code equivalence: CROSS, LESS, and MEDS. These protocols are believed to be quantum-safe. Although all are code-based signatures, they embody distinct design philosophies and exhibit different performance. CROSS is built around a restricted form of syndrome decoding, whereas LESS and MEDS are based on code equivalence problems.

R EFERENCES [1] M. R. Albrecht, D. J. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V. Maram, I. von Maurich, R. Misoczki, R. Niederhagen, K. G. Paterson, E. Persichetti, C. Peters, P. Schwabe, N. Sendrier, J. Szefer, C. J. Tjhai, M. Tomlinson, and W. Wang. Classic McEliece, 2020. NIST PQC Round 3 submission. [2] N. Aragon, P. Barreto, W. Beullens, P. Gaborit, A. Joux, S.-Y. Lau, E. Persichetti, C. Peters, and J.-P. Tillich. BIKE: Bit flipping key encapsulation, 2020. NIST PQC Round 3 submission. [3] T. Attema and S. Fehr. Parallel repetition of (k1 , . . . , kµ )special-sound multi-round interactive proofs. In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology –

5 New MEDS parameters taken from https://groups. google.com/a/list.nist.gov/g/pqc-forum/c/pbT DnPrc2A/m/ ZPrIVSmFCQAJ

11

CRYPTO 2022, volume 13507 of Lecture Notes in Computer Science, pages 415–443. Springer, 2022. [4] L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 684–697. ACM, 2016. [5] M. Baldi, A. Barenghi, M. Battagliola, S. Bitzer, M. Gianvecchio, P. Karl, F. Manganiello, A. Pavoni, G. Pelosi, F. Pintore, P. Santini, J. Schupp, E. Signorini, F. Slaughter, A. Wachter-Zeh, and V. Weger. CROSS: Codes and restricted objects signature scheme, 2023. NIST PQC Additional Digital Signature Schemes submission. [6] E. Berlekamp, R. McEliece, and H. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory, 24(3):384–386, 1978. [7] J.-F. Biasse, G. Micheli, E. Persichetti, and P. Santini. LESS is more: Code-based signatures without syndromes. In A. Nitaj and A. M. Youssef, editors, AFRICACRYPT 2020, volume 12174 of LNCS, pages 45–65. Springer, Cham, July 2020. [8] S. Bitzer, A. Pavoni, V. Weger, P. Santini, M. Baldi, and A. Wachter-Zeh. Generic Decoding of Restricted Errors. In Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT), pages 246– 251, Taipei, Taiwan, 2023. IEEE. [9] K. Bogart, D. Goldberg, and J. Gordon. An elementary proof of the MacWilliams theorem on equivalence of codes. Information and Control, 37(1):19–22, 1978. [10] P.-L. Cayrel, P. Véron, and S. M. El Yousfi Alaoui. A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In A. Biryukov, G. Gong, and D. R. Stinson, editors, Selected Areas in Cryptography, pages 171–186. Springer Berlin Heidelberg, 2011. [11] T. Chou, R. Niederhagen, E. Persichetti, T. H. Randrianarisoa, K. Reijnders, S. Samardjiska, and M. Trimoska. Take your MEDS: Digital signatures from matrix code equivalence. In N. El Mrabet, L. De Feo, and S. Duquesne, editors, AFRICACRYPT 2023, volume 14064 of LNCS, pages 28–52. Springer, Cham, July 2023. [12] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. [13] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé. CRYSTALSDilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268, 2018. [14] A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M. Odlyzko, editor, CRYPTO ’86, pages 186–194. Springer Berlin Heidelberg, 1987. [15] M. J. E. Golay. Notes on Digital Coding. Proceedings of the IRE, 37(6):657, 1949. [16] E. Gorla and F. Salizzoni. MacWilliams’ extension theorem for rank-metric codes. Journal of Symbolic Computation, 122:102263, 2024. [17] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-

Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery. [18] R. W. Hamming. Error detecting and error correcting codes. The Bell System Technical Journal, 29(2):147– 160, 1950. [19] F. J. MacWilliams. Combinatorial Problems of Elementary Abelian Groups. PhD dissertation, Harvard University, 1962. [20] R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report, 44:114–116, Jan. 1978. [21] C. A. Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. Bos, J. Deneuville, A. Dion, P. Gaborit, J. Lacan, E. Persichetti, J. Robert, P. Véron, and G. Zémor. HQC: Hamming quasi-cyclic. NIST PQC Submission, 2025. [22] D. Moody, R. Perlner, A. Regenscheid, A. Robinson, and D. Cooper. Transition to post-quantum cryptography standards. Technical Report NIST IR 8547 IPD, National Institute of Standards and Technology, Nov. 2024. Initial Public Draft. [23] National Institute of Standards and Technology. Post-quantum cryptography standardization. https://csrc.nist.gov/projects/post-quantum-cryptography/ post-quantum-cryptography-standardization, 2017. Updated December 2025. [24] National Institute of Standards and Technology. Status report on the first round of the additional digital signature schemes for the NIST post-quantum cryptography standardization process. Technical Report NIST IR 8528, National Institute of Standards and Technology, Oct. 2024. [25] H. Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 15(2):157–166, 1986. [26] E. Petrank and R. M. Roth. Is code equivalence easy to decide? IEEE Transactions on Information Theory, 43(5):1602–1604, 1997. [27] T. Prest, P. Fouque, L. Ducas, J. Tillich, M. M. Szydlo, and P. Gaborit. Falcon: Fast-Fourier lattice-based compact signatures over NTRU. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019(1):1– 42, 2019. [28] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126, Feb. 1978. [29] C.-P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, Jan. 1991. [30] P. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994.

12

S HORT B IOS Sarah Arpin ([email protected]) is an Assistant Professor in the Department of Mathematics at Virginia Tech. She earned an M.A. in Pure Mathematics from CUNY Hunter College, an M.S. in Applied Mathematics, and a Ph.D. in Number Theory from the University of Colorado Boulder. She completed a postdoc jointly with Leiden University and the Quantum Software Consortium in the Netherlands. Her research interests include number theory, cryptography, and coding theory. Jason LeGrow ([email protected]) is an Assistant Professor in Virginia Tech’s Mathematics Department. Previously, he was a research fellow at the University of Auckland, Mathematics Department. He holds a Ph.D. and MMath in combinatorics and optimization, both from the University of Waterloo, and a BSc (Hons) in pure mathematics from Memorial University of Newfoundland. His research interests are in post-quantum cryptography. Hiram H. López ([email protected]) is an Associate Professor in the Department of Mathematics at Virginia Tech. He received the B.S. degree in applied mathematics from the Autonomous University of Aguascalientes and the Ph.D. in mathematics from CINVESTAV-IPN. He held a postdoctoral position at Clemson University and a tenure-track position at Cleveland State University. His research interests include coding theory, commutative algebra, and image processing. Gretchen Matthews ([email protected]) is a Professor of Mathematics at Virginia Tech and Director of a regional component of the Commonwealth Cyber Initiative (CCI). Matthews earned a B.S. from Oklahoma State University and a Ph.D. from Louisiana State University, both in mathematics, and an M.B.A. from Virginia Tech. She held a postdoctoral appointment at the University of Tennessee and was on the faculty at Clemson University. Her research interests include algebraic geometry and combinatorics and their applications to coding theory and cryptography. 13