<abstract xmlns="http://www.w3.org/1999/xhtml"><p> We study the connection between the MQ problem and the de­coding 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.</p></abstract>

We study the connection between the MQ problem and the de­coding 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.

Connecting the Complexity of MQ- and Code-Based Cryptosystems

Tatra Mountains Mathematical Publications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Connecting the Complexity of MQ- and Code-Based Cryptosystems"}

We study the connection between the MQ problem and the de­coding problem, through the intermediate MRHS representation. The main goal of this study is to...

Connecting the Complexity of MQ- and Code-Based Cryptosystems

Online veröffentlicht: 23. März 2018

Seitenbereich: 163 - 177

Eingereicht: 24. Mai 2017

DOI: https://doi.org/10.1515/tmmp-2017-0025

Schlüsselwörter
decoding problem, MQ problem, MEHS

© 2018

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Connecting the Complexity of MQ- and Code-Based Cryptosystems

Online veröffentlicht: 23. März 2018

Seitenbereich: 163 - 177

Eingereicht: 24. Mai 2017

DOI: https://doi.org/10.1515/tmmp-2017-0025

Schlüsselwörterdecoding problem, MQ problem, MEHS

© 2018

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Schlüsselwörter
decoding problem, MQ problem, MEHS