About this article
Published Online: Mar 23, 2018
Page range: 163 - 177
Received: May 24, 2017
DOI: https://doi.org/10.1515/tmmp-2017-0025
Keywords
© 2018
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.
We study the connection between the MQ problem and the decoding problem, through the intermediate MRHS representation. The main goal of this study is to explicitly bound the complexity of solving MQ systems with decoding tools. The main observation is that although the MQ problem over GF(2) can be efficiently transformed to syndrome decoding, the existing general decoding methods are not suitable to solve the system as efficiently as expected from the MQ representation.