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

Source: arXiv:2606.31601 · Published 2026-06-30 · By Sarah Arpin, Jason T. LeGrow, Hiram H. López, Gretchen L. Matthews

TL;DR

This paper presents an in-depth overview and analysis of two code-based digital signature schemes—CROSS and LESS—that are candidates in NIST's second-round Post-Quantum Cryptography Standardization Process for Additional Signature Schemes. These schemes leverage hard problems from coding theory, namely restricted syndrome decoding (CROSS) and code equivalence (LESS), to construct digital signatures believed to be secure against quantum attacks. The authors meticulously explain the underlying mathematical problems, the transformation of zero-knowledge sigma protocols into digital signatures via the Fiat-Shamir transform, and the signature protocols themselves.

The paper clarifies how CROSS uses a restricted set of error vectors to instantiate a syndrome decoding problem variant that allows for efficient signatures with smaller parameters, while LESS relies on the hardness of finding an isomorphism between two equivalent linear codes. Both schemes emphasize security notions such as existential unforgeability under chosen-message attack (EUF-CMA) and honest-verifier zero-knowledge. The authors also discuss implementation optimizations like parallel repetition and commitment recovery to improve signature size and verification efficiency. Overall, these schemes aim to provide quantum-safe alternatives to lattice-based or number-theoretic signatures, addressing NIST’s call for diverse post-quantum cryptographic tools.

Key findings

• CROSS uses the Restricted Syndrome Decoding Problem (RSDP) with error vectors from a multiplicative subgroup G to enable unique decoding solutions at higher error weights, helping reduce key and signature sizes compared to classical syndrome decoding.
• The RSDP with error set G remains NP-hard and CROSS uses this hardness with parameters chosen to resist both classical and quantum Information Set Decoding (ISD) attacks, which only enjoy polynomial quantum speedups.
• LESS signature scheme security is based on the Computational Code Equivalence Problem: given two equivalent codes, find an isomorphism mapping one to the other, a problem related to Graph Isomorphism and believed to be hard.
• LESS and MEDS schemes rely on the monomial automorphism group and rank-preserving maps respectively, leveraging structural code equivalences in ambient vector spaces with Hamming and rank weights.
• The Fiat-Shamir transform applied with parallel repetition and commitment hashing achieves EUF-CMA security by exponentially decreasing soundness error (e.g., κ = 128/log2 c for NIST Level I).
• LESS and MEDS introduce multiple public keys (S>2) to increase challenge space, decreasing required parallel repetitions κ and thus reducing signature size at the cost of larger public keys.
• Commitment recoverability optimization allows signatures to omit explicit commitments, reconstructing them from challenge-response pairs and reducing signature transmission size substantially.
• CROSS’s zero-knowledge protocol uses a 5-pass q2-Identification scheme structure with two-stage challenges (large and binary), providing both completeness and soundness with two challenge phases.

Threat model

The adversary is a quantum-capable adversary who attempts existential forgery by producing valid signatures on messages without knowledge of the secret key. The attacker has access to the signer’s public key and can request signatures on chosen messages but cannot efficiently solve the underlying NP-hard problems of restricted syndrome decoding or code equivalence underlying CROSS and LESS, respectively. The schemes assume standard cryptographic primitives like collision-resistant hash functions and a trustworthy implementation of the Fiat-Shamir transform.

Methodology — deep read

1. Threat model and assumptions: The adversary is a classical or quantum computationally bounded attacker attempting to forge signatures without access to the signer’s secret key. The schemes aim for existential unforgeability under chosen-message attacks (EUF-CMA). Attackers cannot efficiently solve the underlying NP-complete problems: Restricted Syndrome Decoding (for CROSS) or Code Equivalence (for LESS).

2. Data and problem setup: The schemes work over finite fields Fq with linear codes characterized by parity-check or generator matrices. CROSS’s RSDP restricts the error vectors to a multiplicative subgroup G of Fnq, chosen so that the syndrome decoding problem remains hard with uniqueness of solution. LESS and MEDS encode secret keys as an automorphism A in groups of monomial or rank-preserving matrices mapping one public code to an equivalent code.

3. Architecture/Algorithms: Both schemes rely on zero-knowledge sigma protocols for identification—interactive proofs where a prover demonstrates knowledge of a secret key without revealing it. CROSS constructs commitments using randomized seeds and group actions on error vectors, with two-phase challenges allowing for soundness amplification. LESS uses row-reduced echelon forms of generator matrices combined with automorphism group elements as commitments and responses. The Fiat-Shamir transform converts these interactive protocols into non-interactive digital signature schemes by replacing the verifier’s random challenges with cryptographic hash outputs.

4. Training regime: Not applicable as these are cryptographic constructions rather than learned models. However, parameters such as κ (number of parallel repetitions), size of subgroup G, and code rates are carefully chosen according to security level targets (e.g., NIST Level I to V) and known ISD attack complexities.

5. Evaluation protocol: Security considerations rely on reductions to NP-hard problems and the best-known classical and quantum attacks. Soundness error reductions via parallel repetition are theoretically quantified (soundness error decreases exponentially with κ). Performance optimizations are evaluated theoretically with impact on signature size and verification cost. No empirical attack implementations are presented.

6. Reproducibility: The schemes are fully described with mathematical formalisms enabling independent implementation. The paper is expository and does not provide code or concrete parameter files but references official NIST submissions where code may eventually be released. Datasets are not applicable.

Concrete example (CROSS end-to-end):

• Prover selects secret error vector e ∈ subgroup G as private key.
• Public key consists of parity-check matrix H and syndrome s = eHT.
• During signing, deterministic pseudorandom seeds generate random vectors u′ and e′ in G.
• Prover computes commitments c0 and c1 as hashes of masked syndromes and random vectors.
• Verifier issues two challenges β ∈ F*p and b ∈ {0,1}.
• Prover responds with y = u′ + βe′ and either (y, σ) or Seed depending on b.
• Verifier checks hash consistency and syndromes to accept or reject.
• The signature is formed by κ parallel repetitions of these transcripts, converted to a non-interactive signature using the Fiat-Shamir transform.

Technical innovations

• Introduction of the Restricted Syndrome Decoding Problem (RSDP) with error vectors restricted to multiplicative subgroups, enabling unique decoding at higher weights to improve efficiency over classical syndrome decoding.
• Development of code equivalence-based digital signature schemes (LESS and MEDS) relying on hard isomorphism problems between linear and matrix codes, extending prior work on graph isomorphism reductions.
• Use of zero-knowledge sigma protocols with parallel repetition and the Fiat-Shamir transform to achieve EUF-CMA secure, non-interactive, code-based digital signature schemes.
• Optimization techniques like multiple public keys to broaden challenge spaces, and commitment recoverability to reduce signature sizes by reconstructing commitments during verification.
• Application of vectorization and Kronecker products to handle matrix-code equivalences in MEDS, allowing utilization of rank metric and matrix automorphisms in signature construction.

Baselines vs proposed

• Classical Syndrome Decoding Problem (SDP): typical ISD attack complexity larger due to weight limits, compared to CROSS’s RSDP allowing higher-weight errors for same security level.
• Graph Isomorphism Problem reduction to Code Equivalence: known quasi-polynomial time algorithms exist for graph isomorphism but no efficient polynomial ones for code equivalence assumed, underpinning LESS security.
• NIST Round 2 candidate signature schemes (code-based) compared to lattice-based signatures like CRYSTALS-Dilithium and FALCON: code-based schemes trade larger key sizes for non-lattice assumptions.

Limitations

• The security arguments rely on worst-case to average-case hardness assumptions of RSDP and code equivalence without extensive empirical cryptanalysis against adaptive quantum adversaries.
• No implementation or benchmarking data is presented for signature generation/verification speed or concrete signature/key sizes under various parameter sets.
• Assumes ideal cryptographic hash functions for Fiat-Shamir transform and challenge generation; real-world hash collisions or attacks are not analyzed.
• No discussion on side-channel resistance or implementation pitfalls that could affect practical deployment.
• The approach requires relatively large public keys and signature sizes compared to some lattice-based alternatives, potentially impacting practicality.

Open questions / follow-ons

• Can tighter or adaptive security reductions be established for RSDP and code equivalence problems in the quantum random oracle model?
• What are the concrete performance trade-offs in realistic implementations of CROSS and LESS at different NIST security levels, especially on constrained hardware?
• How resilient are the signature schemes to side-channel or fault-injection attacks in practice?
• Are there more efficient parameterizations or structural restrictions that preserve hardness while reducing key or signature sizes?

Why it matters for bot defense

For bot-defense and CAPTCHA researchers, this paper is informative primarily from the cryptographic primitives perspective underpinning secure authentication and integrity mechanisms in adversarial environments. The CROSS and LESS signature schemes exemplify how complex mathematical hardness assumptions can enable post-quantum secure digital signatures that could secure identity proofs and challenge-response protocols resistant to quantum-empowered attackers.

Though the paper does not address human interaction or bot-detection directly, understanding code-based signature schemes enriches the toolkit for designing backend authentication processes that must remain robust against forgery or impersonation in a post-quantum future. Implementers of CAPTCHA systems might consider integrating such signatures to enhance non-repudiation and authenticity guarantees where quantum resistance is a requirement. Additionally, the zero-knowledge protocol constructions and Fiat-Shamir transformation principles presented here are conceptually useful in designing efficient proofs of possession or challenge-response mechanisms within bot management systems.

Cite

@article{arxiv2606_31601,
  title={ Digital signature schemes based on code equivalence and syndrome decoding from restricted errors },
  author={ Sarah Arpin and Jason T. LeGrow and Hiram H. López and Gretchen L. Matthews },
  journal={arXiv preprint arXiv:2606.31601},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.31601}
}

Read the full paper

• arXiv:2606.31601 (abstract)
• arXiv:2606.31601 (PDF)