MPCitH-based Signatures from Restricted Decoding Problems

• URL: http://arxiv.org/abs/2510.11224v1
• Date: Mon, 13 Oct 2025 10:09:32 GMT
• Title: MPCitH-based Signatures from Restricted Decoding Problems
• Authors: Michele Battagliola, Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger,
• Abstract summary: 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.
• Score: 16.371060416568195
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Threshold-Computation-in-the-Head (TCitH) and VOLE-in-the-Head (VOLEitH), two recent developments of the MPC-in-the-Head (MPCitH) paradigm, have significantly improved the performance of digital signature schemes in this framework. In this note, we embed the restricted decoding problem within these frameworks. We propose a structurally simple modeling that achieves competitive signature sizes. Specifically, by instantiating the restricted decoding problem with the same hardness assumption underlying CROSS, we reduce sizes by more than a factor of two compared to the NIST submission. Moreover, we observe that ternary full-weight decoding, closely related to the hardness assumption underlying WAVE, is a restricted decoding problem. Using ternary full-weight decoding, we obtain signature sizes comparable to the smallest MPCitH-based candidates in the NIST competition.

Related papers

• Toward Uncertainty-Aware and Generalizable Neural Decoding for Quantum LDPC Codes [0.9453554184019106]
  Quantum error correction (QEC) is essential for scalable quantum computing.<n>We propose textbfQuBA, a Bayesian graph neural decoder that integrates attention to both dot-product and multi-head.<n>We further develop textbfSAGU textbf(Sequential Aggregate Generalization under Uncertainty), a multi-code training framework with enhanced cross-domain robustness.
  arXiv  Detail & Related papers  (2025-10-05T01:08:39Z)
• R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning [80.104336426172]
  Chain-of-thought (CoT) enhances problem-solving ability of large language models.<n>CoT incurs substantial inference cost due to long autoregressive trajectories.<n>We introduce R-Stitch, a training-free hybrid decoding framework.
  arXiv  Detail & Related papers  (2025-07-23T08:14:36Z)
• 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)
• Efficient Layered New Bit-Flipping QC-MDPC Decoder for BIKE Post-Quantum Cryptography [6.583725235299022]
  Bit Flipping Key Encapsulation mechanism is a candidate of post-quantum cryptography standardization.<n>New bit-flipping (BF) decoding algorithm decides the BF threshold by an affine function with high-precision coefficients.<n>This paper proposes a column-layered decoder for the new BIKE BF decoding algorithm to substantially reduce the memory requirement.
  arXiv  Detail & Related papers  (2024-12-16T17:23:41Z)
• Highly Efficient Parallel Row-Layered Min-Sum MDPC Decoder for McEliece Cryptosystem [6.583725235299022]
  The medium-density parity-check (MDPC) code-based McEliece cryptosystem remains a finalist of the post-quantum cryptography standard. The Min-sum decoding algorithm achieves better performance-complexity tradeoff than other algorithms for MDPC codes. For the first time, the row-layered scheduling scheme is exploited to substantially reduce the memory requirement of MDPC decoders.
  arXiv  Detail & Related papers  (2024-07-17T16:19:42Z)
• Fault-tolerant quantum architectures based on erasure qubits [49.227671756557946]
  We exploit the idea of erasure qubits, relying on an efficient conversion of the dominant noise into erasures at known locations. We propose and optimize QEC schemes based on erasure qubits and the recently-introduced Floquet codes. Our results demonstrate that, despite being slightly more complex, QEC schemes based on erasure qubits can significantly outperform standard approaches.
  arXiv  Detail & Related papers  (2023-12-21T17:40:18Z)
• Projective Space Stern Decoding and Application to SDitH [0.1755623101161125]
  We show that here standard decoding algorithms for generic linear codes over a finite field can speed up by a factor which is essentially the size of the finite field. We apply this technique to SDitH and show that the parameters of both the original submission and the updated version fall short of meeting the security requirements asked by the NIST.
  arXiv  Detail & Related papers  (2023-12-05T09:33:15Z)
• Testing the Accuracy of Surface Code Decoders [55.616364225463066]
  Large-scale, fault-tolerant quantum computations will be enabled by quantum error-correcting codes (QECC) This work presents the first systematic technique to test the accuracy and effectiveness of different QECC decoding schemes.
  arXiv  Detail & Related papers  (2023-11-21T10:22:08Z)
• Deep Learning Assisted Multiuser MIMO Load Modulated Systems for Enhanced Downlink mmWave Communications [68.96633803796003]
  This paper is focused on multiuser load modulation arrays (MU-LMAs) which are attractive due to their low system complexity and reduced cost for millimeter wave (mmWave) multi-input multi-output (MIMO) systems. The existing precoding algorithm for downlink MU-LMA relies on a sub-array structured (SAS) transmitter which may suffer from decreased degrees of freedom and complex system configuration. In this paper, we conceive an MU-LMA system employing a full-array structured (FAS) transmitter and propose two algorithms accordingly.
  arXiv  Detail & Related papers  (2023-11-08T08:54:56Z)
• Quality-Aware Translation Models: Efficient Generation and Quality Estimation in a Single Model [77.19693792957614]
  We propose to make neural machine translation (NMT) models quality-aware by training them to estimate the quality of their own output. We obtain quality gains similar or even superior to quality reranking approaches, but with the efficiency of single pass decoding.
  arXiv  Detail & Related papers  (2023-10-10T15:33:51Z)
• Union-find quantum decoding without union-find [4.24243593213882]
  We show that the behaviour of the decoder at scale underutilises the data structure. Improvements and simplifications can be made to architectural designs to reduce resource overhead in practice. This yields a linear-time worst-case complexity for the decoder at scale, even with a naive implementation omitting popular optimisations.
  arXiv  Detail & Related papers  (2023-06-16T10:54:59Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)

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.