Details:
Title  Analysis of the MQQ public key cryptosystem.  Author(s)  Danilo Gligoroski, Faug`ere JeanCharles, Rune Steinsmo Odegaard, Ludovic Perret  Type  Book, Chapter in Book, Conference Proceeding  Abstract  MQQ is a multivariate public key cryptosystem (MPKC) based on multivariate quadratic quasigroups and a special transform called “Dobbertin transformation” [17]. The security of MQQ, as well as any MPKC, reduces to the difficulty of solving a nonlinear system of equations easily derived from the public key. In [26], it has been observed that that the algebraic systems obtained are much easier to solve that random nonlinear systems of the same size. In this paper we go one step further in the analysis of MQQ. We explain why systems arising in MQQ are so easy to solve in practice. To do so, we consider the socalled the degree of regularity; which is the exponent in the complexity of a Gröbner basis computation. For MQQ systems, we show that this degree is bounded from above by a small constant. This is due to the fact that the complexity of solving the MQQ system is the minimum complexity of solving just one quasigroup block or solving the Dobbertin transformation. Furthermore, we show that the degree of regularity of the Dobbertin transformation is bounded from above by the same constant as the bound observed on MQQ system. We then investigate the strength of a tweaked MQQ system where the input of the Dobbertin transformation is replaced with random linear equations. It appears that the degree of regularity of this tweaked system varies both with 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 attacks for adequate choices of quasigroup size and number of variables.  Keywords  multivariate cryptography, Gröbner bases, publickey, multivariate quadratic quasigroups, algebraic cryptanalysis  ISBN  9783642176180/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642176197_13 
Language  English  Pages  169183  Publisher  Berlin: Springer  Year  2010  Edition  0  Translation 
No  Refereed 
No 
