IACR News item: 20 June 2013
PhD Database
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.
\r\nSection 2 discusses the MQ-Problem, which relates to direct pre-image attacks using the\r\npublic key, i.e. finding x for a given y and P(x) = y, which is known to be difficult in\r\ngeneral. 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.
\r\nIn 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\r\nsecurity level again. More generally we present an algorithm to solve underdetermined\r\nsystems of MQ-equations faster than before.
\r\nSection 3 presents the main part of this work and is dedicated to algebraic key recovery\r\nattacks on MQ-schemes.\r\nUnfortunately 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\r\nframework 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 vari[...]
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.
\r\nSection 2 discusses the MQ-Problem, which relates to direct pre-image attacks using the\r\npublic key, i.e. finding x for a given y and P(x) = y, which is known to be difficult in\r\ngeneral. 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.
\r\nIn 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\r\nsecurity level again. More generally we present an algorithm to solve underdetermined\r\nsystems of MQ-equations faster than before.
\r\nSection 3 presents the main part of this work and is dedicated to algebraic key recovery\r\nattacks on MQ-schemes.\r\nUnfortunately 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\r\nframework 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 vari[...]
Additional news items may be found on the IACR news page.