International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Christopher Wolf (#33)
Name Christopher Wolf
Personal Homepage http://www.christopher-wolf.de
Topic of his/her doctorate. Multivariate Quadratic Polynomials in Public Key Cryptography
Category public-key cryptography
Keywords multivariate quadratic, overview, Quartz, Sflash, taxonomy, signature schemes, alternative schemes, isomorphism of polynomials,one-way functions, cryptanalysis
Ph.D. Supervisor(s) Bart Preneel
Year of completion 2005
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, Rivest-Shamir-Adleman) 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 NP-completeness 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), Matsumoto-Imai 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 STS-based 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 one-way 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.

Link to full text http://hdl.handle.net/1979/148
E-Mail Address chris (at) Christopher-Wolf.de
Last Change 2011-02-12 11:16:37
To provide an update on this entry, please click .

Christopher Wolf's Students

Enrico Thomae - About the Security of Multivariate Quadratic Public Key Schemes (public-key cryptography)

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR