Cryptography Reference
In-Depth Information
to be secure against all known attacks. We will outline below how they differ
from the original Square scheme—but can be broken nevertheless.
One thing which has also developed with
schemes is their cryptanalysis.
In this article, we will concentrate on attacks from the so-called MinRank family.
Idea is to find a linear combination of some matrices, such that the new matrix
has a special (minimal) rank. Or more formally: Given k matrices M 1 ,...,M k
MQ
n × n
q
k
q
F
and a scalar r N
, find a vector λ F
such that
Rank
k
λ i M i
r.
i =1
We call this an MinRank( q, k, r )-problem . Note that the general MinRank prob-
lem is NP-complete [5]. We will see later how
M
ultivariate
Q
uadratic schemes
relate to matrices in general and to MinRank in particular.
A first MinRank attack in the
uadratic setting was launched
against TTM [13]. Informally speaking, the authors exploited the existence of
a so-called step-structure in the private key to reveal linear relations between
the private and the public key. When enough of these relations were found, the
whole private key could be unravelled. A similar approach was followed in [19].
Here, the step-width was made wider: Instead of allowing only rank differences
of 1, rank differences up to r were allowed. Finally, [21] gave further ideas on
discovering rank structure, in particular “crawling” attacks that exploit that
areas of low rank might be close-by. A cryptanalysis of the Rainbow Signature
Scheme using MinRank can be found in [3]. Our attack on Double-Layer Square
(see sect. 3) will strongly refer to this paper.
Another algorithm to break MinRank-instances in practice is [12]. Here, Gröb-
ner bases are used to actually calculate elements of the kernel and thus derive
possible choices of λ
M
ultivariate
Q
k
q . For some parameters this algorithm is much faster
than sampling and therefore we use it in sect. 4 to break Square+.
F
1.1 Achievement and Organisation
In this paper, we describe an ecient cryptanalysis of the two public key schemes
Double-Layer Square and Square+. We show how to break Double-Layer Square
by a refined MinRank attack that is an extension of Billet and Gilbert [3] attack
against Rainbow. The overall attack complexity is 2 45 . Furthermore we break
Square+ using methods from the cryptanalysis of odd characteristic HFE [2]
and a MinRank attack [12]. In both cases, the attack is in polynomial time of
(nearly) all parameters. In particular, the schemes are completely broken for all
possible, practical choices of parameters.
In sect. 2, we introduce the Square cryptosystem and fix some notation.
Double-Layer Square and its attack is discussed in sect. 3. We deal with Square+
and the corresponding MinRank problem in sect. 4. This paper concludes with
sect. 5. There, we also outline possible extensions to Square- or multi-Square.
Due to space limitations, we had to remove most of the experiments. A full
version is available at http://eprint.iacr.org/2011/431 .
 
Search WWH ::




Custom Search