*18:56*[PhD][Update] Enrico Thomae: About the Security of Multivariate Quadratic Public Key Schemes

Name: Enrico Thomae

Topic: About the Security of Multivariate Quadratic Public Key Schemes

Category:public-key cryptography

Description: 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 t[...]