Speaker
Description
The Matrix Equivalence Digital Signature (MEDS) is a code-based digital signature that was submitted to the NIST call for quantum-resistant protocols. It is currently considered as a candidate for building advanced group action signatures schemes.
The hard problem behind this digital signature is the Matrix Code Equivalence problem. Namely, given two matrix codes $C_1$ and $C_2$, suppose that there is a matrix pair $(A,B)$ where $AC_1B=C_2$ (left and right multiplication of matrices in $C_1$ by $A$ and $B$), how do we find the matrices $A$ and $B$?
This talk studies the matrix code equivalence problem from a sample complexity point of view. Since there is no known polynomial-time algorithm for finding $A$ and $B$ given one instance of the $(C_1, C_2)$ pair, how many such instances are enough to make a polynomial-time solution possible? In particular, we try to establish a relationship between the number of samples and the complexity of finding the secret pair $(A,B)$ using the XL (Extended Linearization) Algorithm.