Abstract

We propose a systematic approach to analyzing the security of the family of DME cryptosystems, which belong to the area of multivariate cryptography. We focus on the DME scheme proposed to the NIST in 2023 and a minus variation of the scheme, called DME^-. As in many attacks on other multivariate cryptosystems, the bottleneck of the attack reduces to solving an instance of the MinRank problem of low rank, arising from the structure of the scheme. We prove that the expected number of solutions of such a MinRank instance is finite. All complexity estimates are derived using existing results about complexity generalized determinantal ideals and therefore rely on the assumption of genericity. Once the set of private keys is simplified -- by specializing some of the variables -- so that, for a given public key, there exists essentially a unique private key, the genericity assumption appears reasonable in light of the experimental results. The results presented in this talk are part of the speaker’s PhD thesis.

Bio

Pilar recently completed her PhD at the Universidad Complutense de Madrid and is currently a postdoctoral researcher at EPITA. Her research interests include the mathematical foundations and cryptanalysis of post-quantum schemes, especially multivariate ones.