We study the connection between the MQ problem and the decodingproblem, through the intermediate MRHS representations. The main goalof this study is to explicitly bound complexity of solving MQ systems with decodingtools. The main observation is that although the MQ problem over GF(2)can be efficiently transformed to syndrome decoding, the existing general decodingmethods are not suitable to solve the system as efficiently as expected fromthe MQ representation.
@article{498,
title = {Connecting the complexity of MQ-and code-based cryptosystems},
journal = {Tatra Mountains Mathematical Publications},
volume = {70},
year = {2018},
language = {EN},
url = {http://dml.mathdoc.fr/item/498}
}
Zajac, Pavol. Connecting the complexity of MQ-and code-based cryptosystems. Tatra Mountains Mathematical Publications, Tome 70 (2018) . http://gdmltest.u-ga.fr/item/498/