## CryptoDB

### Christopher Wolf

#### Affiliation: Ruhr Universitaet Bochum

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

MQ^*-IP: An Identity-based Identification Scheme without Number-theoretic Assumptions
Abstract

In this article, we propose an identification scheme which is based on
the two combinatorial problems Multivariate
Quadratic equations (MQ) and Isomorphism of Polynomials (IP).
We show that this scheme is statistical zero-knowledge.
Using a trapdoor for the MQ-problem, it is possible to make it also identity-based, i.e., there is no need for distributing public keys or for certificates within this scheme.
The size of the public keys and the communication complexity\
are within the range of other non-number-theoretic identification schemes. In contrast to MQ^*-IP, these schemes do usually no permit identity-based public keys.

2008

EPRINT

Time-Area Optimized Public-Key Engines: MQ-Cryptosystems as Replacement for Elliptic Curves?
Abstract

In this paper ways to efficiently implement public-key schemes based onMultivariate Quadratic polynomials (MQ-schemes for short) are investigated. In particular, they are claimed to resist quantum computer attacks. It is shown that such schemes can have a much better time-area product than elliptic curve cryptosystems. For instance, an optimised FPGA implementation of amended TTS is estimated to be over 50 times more efficient with respect to
this parameter. Moreover, a general framework for implementing small-field MQ-schemes in hardware is proposed which includes a systolic architecture performing Gaussian elimination over composite binary fields.

2008

CHES

2005

EPRINT

Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations
Abstract

Multivariate quadratic systems can be used to construct both secure and efficient public key schemes. In this article, we introduce the necessary mathematical tools to deal with multivariate quadratic systems, present an overview of important schemes known so far and outline how they fit into a taxonomy of only four basic schemes and some generic modifiers. Moreover, we suggest new constructions not previously considered. In this context, we propose some open problems and new research directions in the field of multivariate quadratic schemes.

2005

EPRINT

Equivalent Keys in Multivariate Quadratic Public Key Systems
Abstract

Multivariate Quadratic public key schemes have been suggested back in 1985 by Matsumoto and Imai
as an alternative for the RSA scheme.
Since then, several other schemes have been proposed, for example Hidden Field Equations,
Unbalanced Oil and Vinegar schemes, and Stepwise Triangular Schemes.
All these schemes have a rather large key space for a secure choice of parameters.
Surprisingly, the question of equivalent keys has not been discussed in the open literature
until recently.
In this article, we show that for all basic classes mentioned above,
it is possible to reduce the private --- and hence the public ---
key space by several orders of magnitude. For the Matsumoto-Imai scheme, we are even able to show that
the reductions we found are the only ones possible, i.e., that these reductions are tight.
While the theorems developed in this article are of independent interest themselves
as they broaden our understanding of Multivariate Quadratic public key systems,
we see applications of our results both in cryptanalysis and in
memory efficient implementations of MQ-schemes.

2005

EPRINT

Multivariate Quadratic Polynomials in Public Key Cryptography
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.

2004

EPRINT

Classification of Highly Nonlinear Boolean Power Functions with a Randomised Algorithm for Checking Normality
Abstract

A Boolean function is called normal if it is constant on flats of certain dimensions. This property is relevant for the construction and analysis of cryptosystems. This paper presents an asymmetric Monte Carlo algorithm to determine whether a given Boolean function is normal. Our algorithm is far faster than the best known (deterministic) algorithm of Daum et al. In a first phase, it checks for flats of low dimension whether the given Boolean function is constant on them and combines such flats to flats of higher dimension in a second phase. This way, the algorithm is much faster than exhaustive search. Moreover, the algorithm benefits from randomising the first phase. In addition, by evaluating several flats implicitly in parallel, the time-complexity of the algorithm decreases further. As an application, we determine the level of normality for several, highly nonlinear Boolean power functions.

2004

EPRINT

Direct Division in Factor Rings
Abstract

Conventional techniques for division in the polynomial factor ring
$\Ftm$ or the integer ring $\Zzs$ use a combination of inversion
and multiplication. We present a new algorithm that computes the
division directly and therefore eliminates the multiplication
step. The algorithm requires $2\,{\rm degree\/}{(m)}$ (resp. $2
\log_2 n$) steps, each of which uses only shift and
multiply-subtract operations.

2004

EPRINT

Equivalent Keys in HFE, C$^*$, and variations
Abstract

In this article, we investigate the question of equivalent keys for
two $\mathcal{M}$ultivariate $\mathcal{Q}$uadratic
public key schemes HFE and C$^{*--}$ and
improve over a previously known result, to appear at PKC 2005.
Moreover, we show a new non-trivial extension of these results to the
classes HFE-, HFEv, HFEv-, and C$^{*--}$, which are cryptographically
stronger variants of the original
HFE and C$^*$ schemes.
In particular, we are able to reduce the size of the private --- and hence the public ---
key space by at least one order of magnitude.
While the results are of independent interest themselves,
we also see applications both in cryptanalysis
and in memory efficient implementations.

2004

EPRINT

Superfluous Keys in Multivariate Quadratic Asymmetric Systems
Abstract

In this article, we show that public key schemes based on multivariate quadratic
equations allow many equivalent, and hence superfluous private keys.
We achieve this result by investigating several transformations to identify these keys and
show their application to Hidden Field Equations (HFE), C$^*$,
and Unbalanced Oil and Vinegar schemes (UOV).
In all cases, we are able to reduce the size of the private --- and hence the public ---
key space by at least one order of magnitude.
We see applications of our technique both in cryptanalysis of these
schemes and in memory efficient implementations.

#### Program Committees

- Eurocrypt 2009

#### Coauthors

- Andrey Bogdanov (2)
- An Braeken (1)
- Stanislav Bulygin (1)
- Jintai Ding (1)
- Thomas Eisenbarth (2)
- Patrick Fitzpatrick (1)
- Albrecht Petzoldt (1)
- Bart Preneel (7)
- Andy Rupp (2)
- Enrico Thomae (2)
- Bo-Yin Yang (1)