<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

Published Online: Feb 25, 2017

Page range: 205 - 219

Received: Aug 17, 2016

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

Keywords
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

Published Online: Feb 25, 2017

Page range: 205 - 219

Received: Aug 17, 2016

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

Keywordsalgebraic 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.

Keywords
algebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography