Cryptography Reference
In-Depth Information
many multivariate systems in such a way that vastly different schemes are de-
rived with potentially vastly different resistances to specialized attacks.
One of the great challenges facing MPKC is the task of deriving security
proofs. In fact, there currently is no widely accepted quantification for indistin-
guishability between systems of multivariate equations. One reason for the ab-
sence of such a quantification is the fact that even with a great deal of structure
in the construction of a multivariate cryptosystem, the coecients can appear
to have a uniform distribution. In fact, history has shown that once a way to
distinguish a system of structured multivariate equations from a collection of
random equations is discovered, a method of solving this system is often quickly
developed.
Recently, several cryptanalyses of various multivariate cryptosystems have
pointed out weaknesses in the predominant philosophy for the construction of
multivariate public key cryptosystems. Several systems, SFLASH, Square, for ex-
ample, which are based on simple modifications of the prototypical Matsumoto-
Imai public key cryptosystem, have been broken by very similar differential at-
tacks exploiting some symmetry which is inherent to the field structure these
systems utilize. See [5-8]. In fact, even various attacks on other multivariate
schemes, for example the oil-vinegar attack, see [9], can be viewed as a dual
attack, finding a differential invariant.
In [10], a classification of field maps exhibiting the multiplicative symmetry
was presented. In this article we are interested in the dual problem, that is,
identifying all possible initial general linear differential symmetries a field map
can possess. Such a characterization will lead to a fuller understanding of the
theory, potentially establish a foundation for modeling more general security
proofs, and establish a reasonable and quantitative criterion for the development
of future multivariate schemes.which we may model
The paper is organized as follows. The next section illustrates the ubiquitous
nature of the differential attack by recasting the attack on the balanced oil and
vinegar scheme in the differential setting. In the following section, we focus on
differential symmetry, presenting the general linear symmetry and discussing
the general structure of the space of linear maps exhibiting this symmetry. The
subsequent section restricts the analysis of this space to the case in which the
hidden field map of the cryptosystem is a
C
∗
monomial. Next the specific case
of the squaring map used in Square is analyzed. The space of linear maps is
then determined for projected systems such as the projected SFLASH analogue,
pSFLASH. Finally, we review these results and analyze the dimension of this
space of linear maps as a metric for determining differential security.
2
Differential Symmetries and Invariants
Differential attacks play a crucial role in multivariate public key cryptography.
Such attacks have not only broken many of the so called “big field” schemes,
they have directed the further development of the field by inspiring modifiers —
Plus (+), Minus (-), Projection (p), Perturbation (P), Vinegar (v) — and the
creation of newer more robust techniques.
