CRYPTO : Christophe Levrat – A new algorithm solving the matrix code equivalence problem

Chargement Évènements

« Tous les Évènements

  • Cet évènement est passé.

CRYPTO : Christophe Levrat – A new algorithm solving the matrix code equivalence problem

11 mars / 11:00 - 12:00

The matrix code equivalence problem consists, given two k-dimensional vector spaces C,D of m x n matrices over a finite field, in finding invertible matrices P and Q such that D=PCQ. Recent signature schemes such as MEDS and ALTEQ relate their security to the hardness of this problem. Naranayan et al. recently published an algorithm solving this problem in the case k = n =m in O(q^{k/2}) operations. In this talk, we present a different algorithm which solves the general matrix equivalence problem. Our approach consists in reducing the problem to the matrix code conjugacy problem, i.e. the case P=Q. For the latter problem, a natural invariant based on the hull of the code can be used. Next, the equivalence of codes can be deduced using a usual list collision argument. For k=m=n, our algorithm achieves a similar complexity to the aforementioned reference. However, it extends to a much broader range of parameters. This is joint work with Alain Couvreur.

CRYPTO : Christophe Levrat – A new algorithm solving the matrix code equivalence problem

Détails

Date :
11 mars
Heure :
11:00 - 12:00
Catégorie d’Évènement:

Lieu

Bâtiment Fermat, salle 4205

Organisateur

Yann Rotella