<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

Data publikacji: 25 lut 2017

Zakres stron: 205 - 219

Otrzymano: 17 sie 2016

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

Słowa kluczowe
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

Data publikacji: 25 lut 2017

Zakres stron: 205 - 219

Otrzymano: 17 sie 2016

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

Słowa kluczowealgebraic 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.

Słowa kluczowe
algebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography