Cryptography Reference
In-Depth Information
G
((
x
1
,...,x
n
+
)
,X
)=
αX
2
+
β
(
x
1
,...,x
n
+
)
X
+
γ
(
x
1
,...,x
n
+
)
( )
where
α
∈
F
q
n
,
β
is ane and
γ
is quadratic over
F
q
n
. The whole central map
over the vector space is thus given by
⎛
⎞
f
(1)
(
x
1
,...,x
n
+
)
.
f
(
n
+
)
(
x
1
,...,x
n
+
)
g
(1)
(
x
1
,...,x
2
n
+
)
.
g
(
n
)
(
x
1
,...,x
2
n
+
)
⎝
⎠
F ||G
=
.
g
(
i
)
=
x
G
(
i
)
x
with
(
i
)
With || we denote concatenation of two vectors and
G
∈
2
n
+
×
2
n
+
q
. By construction, we have rank(f
f
(
i
)
)
≤
n
+
and rank(
g
(
i
)
)
F
2
n
+
,
cf. fig. 3 for the overall structure of the two layers. In order to invert the central
mapwefirstusethesquarerootformula(1)todetermine
x
1
,...,x
n
+
.This
solution is plugged into (2) which is then solved,
e.g.
by the school topic root
finding for quadratic equations or by Berlekamp's algorithm.
≤
n
n
n
+
n
+
0
and
0
0
for
F
(1)
,...,
F
(
n
+
)
for
G
(
n
+
+1)
,...,
G
(2
n
+
)
Fig. 3.
Central maps of Double-Layer Square
3.1 MinRank Attack against Double-Layer Square
In this section we adapt the MinRank attack of Billet and Gilbert [3] to Double-
Layer Square. In order to reconstruct
T
we have to solve the problem of finding
i
=1
2
n
+
a linear combination
(
i
)
for
λ
i
∈
F
q
with minimal rank. In general this
is a dicult problem, as Buss
et al.
[5] showed that the decisional version of
MinRank over
λ
i
P
F
q
is NP-complete.
The idea of [3] to calculate a solution of the MinRank problem is to sample
a vector
ω
∈
R
F
2
n
q
and hope that it lies in the kernel of a linear combination of
low-rank matrices. If this is the case solving the linear system of equations
2
n
+
2
n
q
,λ
i
2
n
×
2
n
q
(
i
)
ω
=0for
ω
∈
R
F
(
i
)
λ
i
P
∈
F
q
,
P
∈
F
(3)
i
=1
