Connecting the complexity of MQ-and code-based cryptosystems
Abstract
We study the connection between the MQ problem and the decoding
problem, through the intermediate MRHS representations. The main goal
of this study is to explicitly bound 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.
problem, through the intermediate MRHS representations. The main goal
of this study is to explicitly bound 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.