Description
We here investigate the hardness of one of the most relevant problems in multivariate cryptography, namely MinRank: given non-negative intgers n,k,r, and matrices M_0,...,M_k, of size n with entries in F_q, decide whether there exists an F_q-linear combination of those matrices which has rank less than or equal to r. Our starting point is the Kipnis-Shamir modeling of the problem. We first prove new properties satisfed by this modeling. Then, we propose a practical resolution of it - based on a Groebner basis approach - that permits us to efficiently solve two challenges proposed by Courtois for his zero-knowledge authentication scheme, built upon MinRank.<br/> Next we turn to the theoretical complexity of the problem: we exhibit a multi-homogeneous structure of the algebraic system modeling the probem, that yields a theoretical bound on its hardness, reflecting the practical behaviour of our approach. Our main result is that, when the size of the matrices involved minus the target rank is constant, we can solve MinRank in polynomial time.<br/> This is a joint work with Jean-Charles Faugères and Ludovic Perret.
Next sessions
-
Séminaire C2 à INRIA Paris
Emmanuel Thomé et Pierrick Gaudry Rachelle Heim Boissier Épiphane Nouetowa Dung Bui Plus d'infos sur https://seminaire-c2.inria.fr/ -
Attacking the Supersingular Isogeny Problem: From the Delfs–Galbraith algorithm to oriented graphs
Speaker : Arthur Herlédan Le Merdy - COSIC, KU Leuven
The threat of quantum computers motivates the introduction of new hard problems for cryptography.One promising candidate is the Isogeny problem: given two elliptic curves, compute a “nice’’ map between them, called an isogeny.In this talk, we study classical attacks on this problem, specialised to supersingular elliptic curves, on which the security of current isogeny-based cryptography relies. In[…]-
Cryptography
-