<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

Online veröffentlicht: 25. Feb. 2017

Seitenbereich: 205 - 219

Eingereicht: 17. Aug. 2016

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

Schlüsselwörter
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

Online veröffentlicht: 25. Feb. 2017

Seitenbereich: 205 - 219

Eingereicht: 17. Aug. 2016

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

Schlüsselwörteralgebraic 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.

Schlüsselwörter
algebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography