Classification of Keys in MQQ-SIG

Abstract

The security of almost all public-key cryptography is based on some computationally hard problem. Most prominent are the problems of factoring integers into primes and computing discrete logarithms in finite groups. However, in the last two decades, several new public-key schemes have emerged that base their security on completely different problems. One such promising proposal is to base the security of public-key cryptography schemes on the difficulty of solving large systems of multivariate quadratic polynomial equations. A major challenge in designing these public-key systems is to embed an efficient trapdoor into the set of equations. Recently, a novel approach towards this problem was suggested by Gligoroski et al. cite{Gligoroski:2008:MQT}, using the concept of quasigroup string transformations. In this thesis we describe a methodology for identifying strong and weak keys in the newly introduced multivariate public-key signature scheme MQQ-SIG, which is based on this idea. We have conducted a large number of experiments based on Gröbner basis attacks, in order to classify the various parameters that determine the keys in MQQ-SIG. Our findings show that there are big differences in the importance of these parameters. The methodology consists of a classification of different parameters in the scheme, together with an introduction of concrete criteria on which keys to avoid and which to use. Additionally, we identified an unnecessary requirement in the original specification that required the quasigroups to fulfill a certain condition. Removing this restriction can potentially speed up the key generation process by a large factor. Having all this, we propose a new enhanced key generation algorithm for MQQ-SIG that will generate stronger keys and be more efficient than the original key generation method.