Algebraic cryptanalysis applied to equivalence problems

In this talk, we first give an introduction to algebraic cryptanalysis, before looking into concrete applications to solving hard problems relevant for cryptography. The examples chosen for this talk are equivalence problems. Broadly, an equivalence problem considers two instances of the same mathematical object and asks if there exists a map between them that preserves some defined property. Two such problems will be looked at in detail. The matrix code equivalence problem takes as input two error-correcting codes in the rank metric and the map we are tasked to find is an isometry that preserves the rank of codewords. The second problem we are interested in is the alternating trilinear form equivalence, where we are given two alternating trilinear forms and the goal is to find an isomorphism between them. We first show how these two problems are similar, namely that an alternating trilinear form can be viewed as a matrix code with special properties, or that a matrix code can be viewed as a trilinear form without the alternating property. We then present some of our results on attacking these problems using tools from algebraic cryptanalysis. The rising interest in equivalence problems is due to their aptness for building a zero-knowledge-based identification scheme which, using the Fiat-Shamir transform, can be turned into digital signature schemes.