Paper 2005/393
Multivariate Quadratic Polynomials in Public Key Cryptography
Christopher Wolf
Abstract
This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography. In the first chapter, some general terms of cryptography are introduced. In particular, the need for public key cryptography and alternative schemes is motivated, i.e., systems which neither use factoring (like RSA, RivestShamirAdleman) nor the discrete logarithm (like ECC, elliptic curve cryptography). This is followed by a brief introduction of finite fields and a general discussion about Multivariate Quadratic systems of equations and ways of representing them. In this context, affine transformations and their representations are also discussed. After these tools are introduced, they are used to show how Multivariate Quadratic equations can be used for signature and encryption applications. In addition, the problem of Multivariate Quadratic polynomial equations is put into perspective and a link with the theory of NPcompleteness is established. The second chapter concludes with the two related problems "isomorphism of polynomials" and "minimal rank" of the sum of matrices. Both prove useful in the cryptanalysis of Multivariate Quadratic systems. The main part of this thesis is about concrete trapdoors for the problem of Multivariate Quadratic public key systems. We can show that all such systems fall in one of the following four classes: unbalanced oil and vinegar systems (UOV), stepwise triangular systems (STS), MatsumotoImai Scheme A (MIA), and hidden field equations (HFE). Moreover, we demonstrate the use of several modifiers. In order to evaluate the security of these four basic trapdoors and their modifiers, we review some cryptanalytic results. In particular, we were able to develop our own contributions in this field by demonstrating an affine approximation attack and an attack using Gr"obner base computations against the UOV class. Moreover, we derived a key recovery and inversion attack against the STS class. Using our knowledge of the HFE class, we develop two secure versions of the signature scheme Quartz. Another important part of this thesis is the study of the key space of Multivariate Quadratic public key systems. Using special classes of affine transformations, denoted ``sustainers", we are able to show that all four basic classes have some redundancy in their key spaces and hence, have a smaller key space than previously expected. In particular for the UOV and the STS class, this reduction proves quite dramatic. For HFE and MIA, we only find some minor redundancies. Moreover, we are able to show that our results for MIA are the only ones possible, i.e., there are no other redundancies than the one we describe in this thesis. In addition, we extend our results to several important variations of HFE and MIA, namely HFE, HFEv, HFEv, and MIA. They have been used in practice for the construction of signature schemes, namely Quartz and Sflash. In order to demonstrate the practical relevance of Multivariate Quadratic constructions and also of our taxonomy, we show some concrete examples. In particular, we consider the NESSIE submissions Flash, Sflash, and Quartz and discuss their advantages and disadvantages. Moreover, we describe some more recent developments, namely the STSbased schemes enhanced TTS, Tractable Rational Maps, and Rainbow. Then we move on to some application domains for Multivariate Quadratic public key systems. In particular, we see applications in the area of product activation keys, electronic stamps and fast oneway functions. Finally, we suggest some new schemes. In particular, we give a generalisation of MIA to odd characteristics and also investigate some other trapdoors like STS and UOV with the branching and the homogenisation modifiers. All in all, we believe that Multivariate Quadratic polynomial systems are a very practical solution to the problem of public key cryptography. At present, it is not possible to use them for encryption. However, we are confident that it will be possible to overcome this problem soon and use Multivariate Quadratic constructions both for encrypting and signing.
Metadata
 Available format(s)
 PDF PS
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Ph.D. thesis, Katholieke Universiteit Leuven, B. Preneel (supervisor), 156+xxiv pages, November 2005
 Keywords
 multivariate quadraticoverviewQuartzSflashtaxonomysignature schemesalternative schemesisomorphism of polynomialsoneway functionscryptanalysis
 Contact author(s)
 Christopher Wolf @ esat kuleuven be
 History
 20051101: received
 Short URL
 https://ia.cr/2005/393
 License

CC BY
BibTeX
@misc{cryptoeprint:2005/393, author = {Christopher Wolf}, title = {Multivariate Quadratic Polynomials in Public Key Cryptography}, howpublished = {Cryptology ePrint Archive, Paper 2005/393}, year = {2005}, note = {\url{https://eprint.iacr.org/2005/393}}, url = {https://eprint.iacr.org/2005/393} }