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

arXiv:2507.15377 · cs.CR · Submitted 2025-07-21 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia, and with me are Elias and Priya, guest researcher.

Elias: Today's paper: "The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head".

Nadia: The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head introduces new problems related to matrix codes, which are then used to build a post-quantum signature scheme.

Elias: First, who's behind it and why it matters.

Title and authors: Nadia: So we're looking at this paper today titled "The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head." It sounds pretty technical, but what's the core idea behind that title?

Elias: Well, basically, they're taking this matrix code idea and using it to build a new way for digital signatures. They’re talking about two specific problems they call the Matrix Subcode Equivalence Problem and the Matrix Code Permuted Kernel Problem.

Nadia: So what does that actually mean for cryptography? It suggests that even when we move into these matrix codes, there are harder problems out there to rely on for security than just the standard code equivalence problem.

Elias: Exactly, they prove this new problem reduces to something called the Hamming Subcode Equivalence problem, which is known to be NP-Complete. That’s a solid foundation for making their signature scheme secure.

Priya: From a privacy standpoint, what we need to watch is how these matrix problems translate into actual data structures for signing; we want to make sure the underlying math doesn't leak too much information about the secret witness.

Nadia: That's right, Priya. And they’re using a specific framework called MPC-in-the-Head, which is key because it lets them build these proofs of knowledge efficiently for signature schemes.

Elias: The authors are essentially showing how you can take an equivalence problem and turn it into an efficient signature scheme using this MPCitH paradigm.

Nadia: It’s about finding a way to make that reduction work in practice, which is what they're focusing on here.

Priya: So, if we distill it down, they are proposing a new hard problem for constructing signatures based on these matrix properties rather than just using standard equivalence checks.

The paper's summary: Nadia: Okay, so let's look at the summary of "The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head." It points out these two new problems: the Matrix Subcode Equivalence Problem and the Matrix Code Permuted Kernel Problem.

Elias: These new problems are linked to the existing Matrix Code Equivalence problem, which is what you see in schemes like MEDS. But these authors say their version asks to find an isometry given a code C and a subcode D, rather than just comparing two codes directly.

Nadia: So they’re focusing on the relationship between a main code and one of its specific subsets, which is what they call the Hamming metric version of this problem.

Elias: And the big finding here is that they prove that this Matrix Subcode Equivalence problem reduces to the Hamming Subcode Equivalence problem, which researchers know is NP-Complete.

Priya: For us, it’s important that this reduction confirms the difficulty of these problems; if you can solve one, you can solve the other, which means we have a solid hardness guarantee for their signing process.

Nadia: And they connect this hardness to building a signature scheme using MPC-in-the-Head techniques, which is where the practical application comes in.

Elias: They take this kernel problem and use MPCitH to construct a signature scheme, aiming for a smaller size than existing schemes like MEDS for that first NIST security level.

The paper's improvements: Nadia: Now let's talk about what they claim are the specific improvements in this work regarding the Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head.

Elias: They introduce a couple of new problems, but the main improvement is that they build a signature scheme directly from the Matrix Code Permuted Kernel Problem using MPCitH techniques.

Nadia: So, compared to older methods like MEDS, they claim their resulting signature size is smaller and their public keys are much smaller too.

Elias: They state that this new scheme gets a signature size of approximately four thousand eight hundred Bytes with a public key around two hundred seventy-five Bytes.

Priya: That reduction in size is significant when you think about deployment, especially for systems where bandwidth or storage matters, because smaller signatures mean less data being transmitted.

Nadia: And they also detail the attacks on this problem themselves, showing how they perform better than in older problems like MCE because of something called invariants.

Elias: They found that the attacks on this new formulation behave differently and require careful adaptation, and they specifically find that the attacks perform worse by a large margin due to the use of these invariants.

Conclusion: Nadia: So we’re wrapping up this discussion on "The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head." They establish a new hard problem based on matrix codes, linking it to the known NP-Complete Hamming Subcode Equivalence problem.

Elias: The main implication is that we can now build post-quantum signatures by leveraging these matrix problems through the MPCitH paradigm for creating zero-knowledge proofs.

Priya: For me, what this means for privacy and measurement is that the scheme is designed to be efficient, which suggests it might be feasible to use in real-world applications without massive computational overhead.

Nadia: That efficiency comes with a trade-off in terms of signature size, and they’ve shown that this new approach can yield a public key around two hundred seventy-five Bytes and a signature size of about four thousand eight hundred Bytes.

Elias: They also show that when comparing their results to other schemes like CROSS or MEDS, their signature performs better than SPHINCS+ and is smaller than MEDS by a factor close to five.

Nadia: So, in summary, this paper gives us a way to construct signatures based on the Matrix Subcode Equivalence problem using MPC-in-the-Head techniques.

LITIS, University of Rouen Normandie · XLIM, University of Limoges

cs.CR

Submitted: 2025-07-21

Updated: 2026-10-08

Journal ref: Designs, Codes and Cryptography, 2026, 94 (76)

Project page: https://pqcalteq.github.io

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 62/100

The gist: The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head introduces new problems related to matrix codes, which are then used to build a post-quantum signature

Key concepts

Matrix Subcode Equivalence Problem (MSE)
This is a novel mathematical problem asking to find an isometry given a code C and a subcode D. It is closely related to the Matrix Code Equivalence problem used in existing schemes like MEDS, and the paper proves it is at least as hard as the Hamming SEP.
MPCitH Paradigm
This framework is used to build proofs of knowledge for signature schemes. It relies on Shamir’s Secret Sharing instead of additive sharing to verify that a witness satisfies polynomial constraints by evaluating specific functions on the secret shares.
Hamming Subcode Equivalence Problem
This is a known NP-Complete problem that the authors prove the Matrix Subcode Equivalence problem reduces to. Proving this reduction establishes MSE as a hard problem suitable for use in constructing post-quantum signature schemes.

Terminology

Summary

The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head introduces new problems related to matrix codes, which are then used to build a post-quantum signature scheme. The work proves that the Matrix Subcode Equivalence problem reduces to the Hamming Subcode Equivalence problem, establishing a new hard problem for constructing signatures using the MPCitH paradigm.

Matrix Code Problems Introduced

The paper introduces two novel problems: the Matrix Subcode Equivalence Problem (MSE) and the Matrix Code Permuted Kernel Problem (MCPKP), which are closely related to the Matrix Code Equivalence problem (MCE) used in MEDS The 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.

Hardness and Reductions

The Matrix Subcode Equivalence problem (MSE) is shown to be at least as hard as the Hamming SEP The MSE problem is at least as hard as the Hamming SEP Since A and B are invertible, one can easily see that this is equivalent to G′(A⊤ ⊗ B) −1 = T⊤G which itself can be rewritten as G′(A⊤ ⊗ B)H⊤ = 0 (where H is the parity-check matrix of G). The Matrix Subcode Equivalence problem has been studied in several articles [24, 27, 43], and [23] led to the MEDS signature scheme.

MPCitH Frameworks

The MPCitH paradigm is a powerful tool for building proofs of knowledge The TCitH framework relies on Shamir’s Secret Sharing instead of usually used additive sharing This framework allows checking that a witness x is such that f1(x) = · · · = fm(x) = 0 by evaluating fj([[x]]i) for all j in [1, m], and then computing a linear combination [[α]]i = Pm j=1 γjfj ([[x]]i. The VOLEitH framework uses Vector Oblivious Linear Evaluations (VOLE) correlations to commit to a witness and then prove the knowledge of the solution of polynomial constraints by performing operations on the hidden witness.

Signature Scheme Construction

A signature scheme is built using the Matrix Code Permuted Kernel Problem via MPC-in-the-Head techniques The protocol involves sharing a witness in N shares using Shamir’s Secret Sharing, committing to these N shares, performing the MPC protocol ”in his head”, and then sending commitments of the computations. The signature size is derived from this process, resulting in a signature size of ≈ 4800 Bytes with a public key of ≈ 275 Bytes.

Attacks on the Problem

The paper details several attacks on the MSE problem, including an attack through code equivalence and algebraic attacks. The complexity for one collision in Algorithm 3 is at least O N1 N2 2(mn)ωCSolve, n, k → ∞. Furthermore, the analysis shows that the attacks perform much worse than in the code equivalence case due to the use of invariants. The QMLE problem is introduced as a related problem that can be solved by building lists and solving an inhomogeneous instance using Algorithm 6.

Parameter Selection and Comparison

The parameter choices are selected according to the attacks described in Section 5 Table 2 shows the parameters chosen according to the attacks described in Section 5 and according public key size in Bytes. The resulting signature sizes for MCPKP are compared with other schemes, such as CROSS and MEDS, showing that our signature performs better than SPHINCS+. The comparison also shows that the signature is smaller than MEDS by a factor close to 5.

Computational Cost

The computational cost of the signature scheme is influenced by both the symmetric part and the MPC simulation part For KuMQuat-28-L1s, there are O(mn 2) multiplications in Fq for us, with q = 64 and m = n = 12 compared to O(k′(mn) 2) multiplications in Fq for us, with q = 64 and m = n = 12. This results in around the same amount of multiplications in Fq, but for q = 2, this protocol would need to be repeated more times than for q = 64 (to have an appropriate soundness error), so we can expect the size of Fq to have a limited influence. The symmetric part tends to often be more important than the MPC emulation one.

Conclusion on Hardness

The analysis of the attacks shows that for MSE, there are no invariants that allow for an efficient adaptation of previous attacks, making it harder than MCE in practice. The complexity of solving inhQSMLE is bounded by CinhQSMLE = O v + 2/3 − v−ω, n, k → ∞. The final analysis suggests that the witness is composed of two invertible matrices, which do not have a smaller representation than (m squared + n 2) log2(q), which is quite large.

The gist

The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head introduces new problems related to matrix codes, which are then used to build a post-quantum signature scheme. The work proves that the Matrix Subcode Equivalence problem reduces to the Hamming Subcode Equivalence problem, establishing a new hard problem for constructing signatures using the MPCitH paradigm.

How it works

The paper introduces two novel problems: the Matrix Subcode Equivalence Problem (MSE) and the Matrix Code Permuted Kernel Problem (MCPKP), which are closely related to the Matrix Code Equivalence problem (MCE) used in MEDS The two 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.

Matrix Code Problems Introduced

The paper introduces two novel problems: the Matrix Subcode Equivalence Problem (MSE) and the Matrix Code Permuted Kernel Problem (MCPKP), which are closely related to the Matrix Code Equivalence problem (MCE) used in MEDS The two 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.

Signature Scheme Construction

A signature scheme is built using the Matrix Code Permuted Kernel Problem via MPC-in-the-Head techniques The protocol involves sharing a witness in N shares using Shamir’s Secret Sharing, committing to these N shares, performing the MPC protocol ”in his head”, and then sending commitments of the computations.

Improvements for AI systems

  1. The system can generate signatures using a new hard problem based on the Matrix Subcode Equivalence Problem to build a signature scheme, resulting in a signature size of ≈ 4 800 Bytes, with a public key of ≈ 275 Bytes.

  2. The improved AI system can utilize the MPC-in-the-Head paradigm (specifically TCitH or VOLEitH frameworks) to construct zero-knowledge proofs that are transformed into efficient signature schemes for code-based cryptography.

  3. The signature scheme performs better than SPHINCS+ with a smaller size of public key + signature and is almost half the size of the CROSS signature scheme.

Related papers