Pavol Zajac – Slovak University of Technology in Bratislava

Title: MRHS equation systems and their use in cryptography

Abstract: A Multiple-Right-Hand-Sides (MRHS) equation is an inclusion in the form , where is a matrix over some field and is a set of vectors. A system of MRHS equations is a conjunction of multiple MRHS equations. Vector is a solution of a MRHS system if all MRHS equations in the system are satisfied. In this talk we will review some methods of solving MRHS equations and MRHS systems, and show the application of MRHS equations in cryptography.

Question of whether a system of MRHS solution or not is NP complete, and is thus believed to be hard to solve in general. On the other hand, we can show that specific (infinite) classes of MRHS systems can be solved in polynomial time. We have proposed a specific generic construction to exploit this property in a construction of a signature scheme.

MRHS systems are also of a specific interest in algebraic cryptanalysis, especially for designs based on substitution-permutation networks. The non-linear elements of the cipher are modeled by right-hand-side sets , while linear diffusion layers are represented compactly in the left-hand-side matrix . There is an open question, how difficult is to solve some specific classes of MRHS systems obtained from ciphers. This question is especially important for ciphers realized by circuits with a low number of (both linear and non-linear) gates.