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.
Enrico Thomae (#889)
Topic of his/her doctorate.
About the Security of Multivariate Quadratic Public Key Schemes
Year of completion
The primary goal of this thesis is to evaluate the security of multivariate quadratic public key schemes. We investigate three main topics related to the security of MQ-schemes, namely the MQ-Problem, the IP-Problem and the MinRank-Problem.
Section 2 discusses the MQ-Problem, which relates to direct pre-image attacks using the public key, i.e. finding x for a given y and P(x) = y, which is known to be difficult in general. In section 2.1 we provide a brief survey on algorithms to solve such systems, like F4, F5, XL and MutantXL. We recap the complexity analysis of the first three algorithms and provide a detailed complexity analysis of the latter. Our contribution is a proof of theorem 2.7 which is hopefully simpler than that in [CKPS, Section 8]. Further we derived theorem 2.29 and thus confirmed results from Yang and Chen [YC04a] in a different way.
In section 2.2 we present a new direct attack on the Unbalanced Oil and Vinegar signature scheme, which forces to raise parameters in order to obtain the same security level again. More generally we present an algorithm to solve underdetermined systems of MQ-equations faster than before.
Section 3 presents the main part of this work and is dedicated to algebraic key recovery attacks on MQ-schemes. Unfortunately naive algebraic attacks are usually far from being efficient due to the large number of variables. So we first formalize the underlying class of problems and introduce the Isomorphism of Polynomials with partial Knowledge (IPpK) Problem in section 3.3. We relate this new problem to known problems, like the Isomorphism of Polynomials Problem with one and two secrets. Our main contribution is to provide a general algebraic framework to tackle the IPpK-Problem. Therefore we generalize the notion of equivalent keys to so-called good keys. In a nutshell equivalent keys allow to reduce the number of variables of an algebraic attack. Good keys further reduce the number of variables, but this time also the number of equations. Finding an optimal trade-off is the main purpose of section 3.4. We show that good keys provide a different point of view on the best known algebraic attacks, like the UOV Reconciliation attack or the Rainbow Band Separation attack. We use our new technique to give new polynomial time attacks on MQQ-Enc, MQQ-Sig and a variant of STS. Further we gain new and faster exponential time attacks on Enhanced TTS, Enhanced STS and MFE-Dio.
Section 4 presents the third part of this work, namely the MinRank-Problem. We investigate known techniques to solve this problem and apply them to provide polynomial time attacks on Double-Layer Square and Square+. Furthermore we show how to speed up MinRank attacks specialized for a variant of Rainbow over noncommutative rings.
Even if not intended right at the beginning, this thesis ended up in covering most of the techniques (except linear [DHN+07] and differential [FGS05] attacks) for evaluating the security of MQ-schemes.
enrico.thomae (at) rub.de