<abstract xmlns="http://www.w3.org/1999/xhtml"><p>In this article we study the difficulty of solving Multiple Right-Hand Side (MRHS) equation systems. In the first part we show that, in general, solving MRHS systems is NP-hard. In the next part we focus on special (large) families of MRHS systems that can be solved in polynomial time with two algorithms: one based on linearisation of MRHS equations, and the second one based on decoding problems that can be solved in polynomial time.</p></abstract>

In this article we study the difficulty of solving Multiple Right-Hand Side (MRHS) equation systems. In the first part we show that, in general, solving MRHS systems is NP-hard. In the next part we focus on special (large) families of MRHS systems that can be solved in polynomial time with two algorithms: one based on linearisation of MRHS equations, and the second one based on decoding problems that can be solved in polynomial time.

MRHS Equation Systems that can be Solved in Polynomial Time

Institute of Computer Science and Mathematics, Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava, Ilkovičova 3, SK–812-19 Bratislava,

Tatra Mountains Mathematical Publications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"MRHS Equation Systems that can be Solved in Polynomial Time"}

In this article we study the difficulty of solving Multiple Right-Hand Side (MRHS) equation systems. In the first part we show that, in general, solving MRHS...

MRHS Equation Systems that can be Solved in Polynomial Time

Publicado en línea: 25 feb 2017

Páginas: 205 - 219

Recibido: 17 ago 2016

DOI: https://doi.org/10.1515/tmmp-2016-0040

Palabras clave
algebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography

© 2016 Pavol Zajac, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

MRHS Equation Systems that can be Solved in Polynomial Time

Publicado en línea: 25 feb 2017

Páginas: 205 - 219

Recibido: 17 ago 2016

DOI: https://doi.org/10.1515/tmmp-2016-0040

Palabras clavealgebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography

© 2016 Pavol Zajac, published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Palabras clave
algebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography