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.
Prochains exposés
-
Adelic reduction of module lattices
Orateur : Henry Bambury - DGA-MI et Inria Rennes
We give a strict generalisation of the LLL algorithm over number fields, based on the reduction theory of $GL(n)$ over the adele ring of a number field. Our algorithm is free of heuristics, with rigorous bounds on output quality and complexity. -- based on joint work with Seungki Kim, Changmin Lee and Phong Nguyen ---
Cryptography
-
-
European Cyber Week: atelier cryptographie post-quantique
Dans la continuité des éditions 2021, 2022 et 2024, la DGA — en partenariat avec CREACH LABS et avec le soutien de l'ANSSI, de l'IRISA, de l'IRMAR et du Pôle d'Excellence Cyber — organise la 4e édition de l'atelier consacré à la cryptographie post-quantique dans le cadre de l'European Cyber Week 2026. Attention, il faut s'inscrire (gratuitement) au préalable — s'inscrire à la conférence Les[…] -
Post-quantum day of the cryptography seminar
A scientific day devoted to post-quantum cryptography, held in the wake of the European Cyber Week, with talks more technical than those presented at the ECW.