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

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.