<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

Pubblicato online: 25 feb 2017

Pagine: 205 - 219

Ricevuto: 17 ago 2016

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

Parole chiave
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

Pubblicato online: 25 feb 2017

Pagine: 205 - 219

Ricevuto: 17 ago 2016

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

Parole chiavealgebraic 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.

Parole chiave
algebraic cryptanalysis, MRHS equations, NP-hard, post-quantum cryptography