The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head

• URL: http://arxiv.org/abs/2507.15377v1
• Date: Mon, 21 Jul 2025 08:33:24 GMT
• Title: The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head
• Authors: Magali Bardet, Charles Brion, Philippe Gaborit, Mercedes Haiech, Romaric Neveu,
• Abstract summary: 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.
• Score: 2.123778388986574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nowadays, equivalence problems are widely used in cryptography, most notably to establish cryptosystems such as digital signatures, with MEDS, LESS, PERK as the most recent ones. However, in the context of matrix codes, only the code equivalence problem has been studied, while the subcode equivalence is well-defined in the Hamming metric. In this work, we introduce two new problems: the Matrix Subcode Equivalence Problem and the Matrix Code Permuted Kernel Problem, to which we apply the MPCitH paradigm to build a signature scheme. These new problems, closely related to the Matrix Code Equivalence problem, ask to find an isometry given a code $C$ and a subcode $D$. Furthermore, we prove that the Matrix Subcode Equivalence problem reduces to the Hamming Subcode Equivalence problem, which is known to be NP-Complete, thus introducing the matrix code version of the Permuted Kernel Problem. We also adapt the combinatorial and algebraic algorithms for the Matrix Code Equivalence problem to the subcode case, and we analyze their complexities. We find with this analysis that the algorithms perform much worse than in the code equivalence case, which is the same as what happens in the Hamming metric. Finally, our analysis of the attacks allows us to take parameters much smaller than in the Matrix Code Equivalence case. Coupled with the effectiveness of \textit{Threshold-Computation-in-the-Head} or \textit{VOLE-in-the-Head}, we obtain a signature size of $\approx$ 4 800 Bytes, with a public key of $\approx$ 275 Bytes. We thus obtain a reasonable signature size, which brings diversity in the landscape of post-quantum signature schemes, by relying on a new hard problem. In particular, this new signature scheme performs better than SPHINCS+, with a smaller size of public key + signature. Our signature compares also well with other signature schemes: compared to MEDS, the signature is smaller, and we reduced the size of the sum of signature and public key by a factor close to 5. We also obtain a signature size that is almost half the size of the CROSS signature scheme.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• 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)
• MIRANDA: short signatures from a leakage-free full-domain-hash scheme [10.228787876075266]
  We present $mathsfMiranda$, the first family of full-domain-hash signatures based on matrix codes.<n>Our trapdoor is very simple and generic: if we propose it with matrix codes, it can actually be instantiated in many other ways.
  arXiv  Detail & Related papers  (2025-10-08T19:24:24Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Quantum advantage from soft decoders [0.7728149002473877]
  We provide improvements for some instantiations of the Optimal Polynomial Interpolation (OPI) problem. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. In order to be able to use a decoder in the setting of Regev's reduction, we provide a novel reduction from a syndrome to a coset sampling problem.
  arXiv  Detail & Related papers  (2024-11-19T15:12:03Z)
• Encodings of the weighted MAX k-CUT on qubit systems [0.0]
  This paper explores encoding methods for the weighted MAX k-CUT problem on qubit systems.<n>We examine various encoding schemes and evaluate the efficiency of these approaches.<n> Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes.
  arXiv  Detail & Related papers  (2024-11-13T13:21:35Z)
• MinRank Gabidulin encryption scheme on matrix codes [6.471199354529622]
  We propose a generalization of the McEliece scheme and the Niederreiter frame to matrix codes and the MinRank problem. Our new approach permits to achieve better trade-off between ciphertexts and public key than the classical McEliece scheme.
  arXiv  Detail & Related papers  (2024-05-26T12:04:01Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme [0.8643517734716606]
  We present a post-quantum digital signature algorithm based on solving multivariate equations. We show that our carefully chosen parameters can resist all existing state-of-the-art attacks. This is the smallest signature size among all known post-quantum signature schemes of similar security.
  arXiv  Detail & Related papers  (2023-12-15T04:58:10Z)
• 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)
• 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)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• Conservation laws and quantum error correction: towards a generalised matching decoder [2.1756081703276]
  We explore decoding algorithms for the surface code, a prototypical quantum low-density parity-check code. The decoder works by exploiting underlying structure that arises due to materialised symmetries among surface-code stabilizer elements. We propose a systematic way of constructing a minimum-weight perfect-matching decoder for codes with certain characteristic properties.
  arXiv  Detail & Related papers  (2022-07-13T18:00:00Z)
• Sparsifying Parity-Check Matrices [60.28601275219819]
  We consider the problem of minimizing the number of one-entries in parity-check matrices. In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages. We propose a simple matrix row manipulation which alters the PCM, but not the code itself.
  arXiv  Detail & Related papers  (2020-05-08T05:51:40Z)

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.