Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS

• URL: http://arxiv.org/abs/2604.09292v1
• Date: Fri, 10 Apr 2026 13:03:00 GMT
• Title: Cross-Paradigm Models of Restricted Syndrome Decoding with Application to CROSS
• Abstract summary: We show that solutions to Restricted Syndrome Decoding can be deduced from vectors of a particular structure and a small norm in newly constructed codes.<n>This allows us to reduce Restricted Syndrome Decoding to both code-based (Regular Syndrome Decoding) and lattice-based problems.
• Score: 0.47267770920095525
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Restricted Syndrome Decoding (ResSD) is a variant of linear code decoding problem where each of the error's entries must belong to a fixed small set of values. This problem underlies the security of CROSS, a post-quantum signature scheme that is one of the Round 2 candidates of NIST's ongoing additional signatures call. We show that solutions to this problem can be deduced from vectors of a particular structure and a small norm in newly constructed codes, in both Hamming and Euclidean metrics. This allows us to reduce Restricted Syndrome Decoding to both code-based (Regular Syndrome Decoding) and lattice-based problems (Closest Vector Problem, List of Short/Close Vectors), increasing the attack surface and providing new insights into the security of ResSD. We evaluate our attacks on CROSS instances both theoretically and experimentally on reduced parameters.

Related papers

• Fast Fault-Tolerant Decoders for Hypergraph Product and Lifted-Product Codes [1.9365949510386082]
  We design low-complexity, fault-tolerant decoders for quantum low-density parity-check (QLDPC) codes.<n>We target two major bottlenecks of decoding under the emphcircuit-level noise model.
  arXiv  Detail & Related papers  (2026-08-31T16:18:29Z)
• Follow the Latent Roadmap: Navigating Revocable Decoding for Diffusion LLMs with Anchor Tokens [22.687236570529844]
  We propose ASRD (Anchor Supervised Revocable Decoding), a training-free framework that operates within the embedding space.<n>We show that ASRD outperforms recent remasking baselines, achieving accuracy improvements of up to 6.4% while accelerating inference throughput by up to 7.2times$.
  arXiv  Detail & Related papers  (2026-06-15T15:23:47Z)
• Combinatorial Synthesis: Scaling Code RLVR via Atomic Decomposition and Recombination [70.27578249309103]
  Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as the cornerstone for shaping the remarkable coding abilities of Large Language Models (LLMs)<n>We propose Atomic Decomposition and Recombination (ADR), a novel framework that generates verifiable code tasks via decomposition into atomic elements and controlled recombination.<n>Our work sheds light on a new paradigm for novel code task synthesis and scalable RLVR training.
  arXiv  Detail & Related papers  (2026-05-29T09:29:32Z)
• MPCitH-based Signatures from Restricted Decoding Problems [16.371060416568195]
  We embed the restricted decoding problem within MPCitH and VOLE-in-the-Head frameworks.<n>We propose a structurally simple modeling that achieves competitive signature sizes.<n>We obtain signature sizes comparable to the smallest MPCitH-based candidates in the NIST competition.
  arXiv  Detail & Related papers  (2025-10-13T10:09:32Z)
• The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head [2.123778388986574]
  We introduce two new problems: the Matrix Subcode Equivalence Problem and the Matrix Code Permuted Kernel Problem.<n>We apply the MPCitH paradigm to build a signature scheme.<n>We obtain a signature size of $approx$ 4 800 Bytes, with a public key of $approx$ 275 Bytes.
  arXiv  Detail & Related papers  (2025-07-21T08:33:24Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  Researchers have attempted to demonstrate the algorithmic hardness of the Learning Parity with Noise problem.<n>We characterize the efficiency of the reduction in terms of the parameters of the decoding and primitive problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• Q2A: Querying Implicit Fully Continuous Feature Pyramid to Align Features for Medical Image Segmentation [10.66113563605316]
  We propose Q2A, a novel one-step query-based aligning paradigm, to solve the feature misalignment problem in the INR-based decoder. For each target coordinate, Q2A first generates several queries depicting the spatial offsets and the cell resolutions of the contextual features aligned to the coordinate, then calculates the corresponding aligned features.
  arXiv  Detail & Related papers  (2024-04-15T05:53:26Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Optimal Single-Shot Decoding of Quantum Codes [4.233908672338595]
  We discuss single-shot decoding of quantum Calderbank-Shor-Steane codes with faulty syndrome measurements. By adding redundant rows to the code's parity-check matrix we obtain an additional syndrome error correcting code.
  arXiv  Detail & Related papers  (2023-10-27T13:35:49Z)
• Fault-Tolerant Computing with Single Qudit Encoding [49.89725935672549]
  We discuss stabilizer quantum-error correction codes implemented in a single multi-level qudit. These codes can be customized to the specific physical errors on the qudit, effectively suppressing them. We demonstrate a Fault-Tolerant implementation on molecular spin qudits, showcasing nearly exponential error suppression with only linear qudit size growth.
  arXiv  Detail & Related papers  (2023-07-20T10:51:23Z)
• Fault Sneaking Attack: a Stealthy Framework for Misleading Deep Neural Networks [46.731211379810105]
  We propose a fault sneaking attack on deep neural networks (DNNs)<n>The adversary aims to misclassify certain input images into any target labels by modifying the DNN parameters.<n>We show that the proposed framework can inject multiple sneaking faults without losing the overall test accuracy performance.
  arXiv  Detail & Related papers  (2019-05-28T18:56:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.