Analysis of the MQQ Public Key Cryptosystem

International audienceMQQ is a multivariate cryptosystem based on multivariate quadratic quasigroups and the Dobbertin transformation [18]. The cryptosystem was broken both by Gröbner bases computation and MutantXL[27]. The complexity of Gröbner bases computation is exponential in the degree of regularity, which is the maximum degree of polynomials occurring during the computation. The authors of [27] observed that the degree of regularity for solving the MQQ system is bounded from above by a small constant. In this paper we go one step further in the analysis of MQQ. We explain why the degree of regularity for the MQQ system is bounded. The main result of this paper is how the complexity of solving the MQQ system is the minimum complexity of solving just one quasigroup block and solving the Dobbertin transformation. Furthermore, we show that the degree of regularity for solving the Dobbertin transformation is bounded from above by the same constant as the bound on the MQQ system. We then investigate the strength of a tweaked MQQ system where the input to the Dobbertin transformation is replaced with random linear equations. We find that the degree of regularity for this tweaked system varies both in the size of the quasigroups and the number of variables. We conclude that if a suitable replacement for the Dobbertin transformation is found, MQQ can possibly be made strong enough to resist pure Gröbner attack for correct choices of quasigroups size and number of variables