Cryptography Reference
In-Depth Information
fixed values and
x
a free variable living over the extension field
F
q
n
+
.Usingthis
notation, we can formulate the following system of quadratic equations over the
vector space
n
q
n
+
:
F
n
+
+
p
(
i
)
ω
=0
n
λ
i
P
i
=1
For rank 1, we can sample a total of (
n
−
1) linearly independent values
ω
(1)
,...,ω
(
n
−
1)
from the kernel and hence obtain (
n
−
1)
n
linearly indepen-
dent equations in a total of (
n
−
1) + (
n
+
+
p
)=2
n
+
+
p
−
1 unknowns.
According to [12], we expect an overall complexity of
N
+
r
+1
r
+2
3
for
N
the num-
ber of unknowns. For the proposed parameters
n
=48
,
=3
,p
=5weobtaina
workload of
2
n
+
+
p
+1
3
3
2
52
.
55
. This is clearly worse than Schnorr's method.
However, the Gröbner method can exploit computing all intermediate steps in
the ground field, so the authors of [2] report a substantial speed-up here. More-
over, for variations of Square+, we might be able to formulate side-conditions
easier than for Schnorr's method.
Executing either the algorithm of Schnorr or of Levi-dit-Vehel
et al.
,wecan
reconstruct the initial Square system and are in the same position as a legitimate
user.
We have implemented the attack of Schnorr and found the theory in line with
the practical experiments. In particular, the matrices
≈
(
i
)
(
n
+
)
have rank 1 over the extension field and we can reconstruct the matrix
H
for
public key matrices
F
for 1
≤
i
≤
(
k
)
P
for 1
≤
k
≤
(
n
+
+
p
)alone.
5Con lu on
In this paper we have presented the first cryptanalysis of the two twin schemes
Double-Layer Square and Square+. Both attacks relied heavily on the rank prop-
erties of the public key equations over the ground field (Double-Layer) or the
extension field (Square+). In either case, each scheme is fully broken for any
reasonable choice of parameters: For Double-Layer Square, the attack is expo-
nential in the security parameter
. However, as
= 4 and cannot be increased
too much due to generic attacks against
uadratic schemes, it is
ecient in practice. For Square+, the attack is fully polynomial in all security
parameters
q, , p
.
As we have established a strong link between odd characteristic Hidden Field
Equations and Square, we know that any cryptanalytic result for the former can
be exploited for the latter. So the relation between Square and odd-HFE is the
same as for MIA/C
∗
and HFE. All attacks to the latter (odd-HFE, HFE) will
inevitable apply to the former (Square, MIA/C
∗
). Hence, any strategy to repair
Square will need to take these similarities into account. In addition, we have to
remember that Square will always be much weaker than odd-HFE—for reasons
similar to the pair MIA/C
∗
and HFE. Moreover, we expect that any successful
cryptanalysis of odd-HFE can be turned easily in a cryptanalysis of Square—
maybe even
without
any further modification. For example, transferring Square
M
ultivariate
Q
