Cryptography Reference
In-Depth Information
enough for our attack that such a linear combination exists. In order to
eciently
obtain this solution using (3) we also need the rank of the whole matrix from
fig. 4 to be rank(
A
)+
n
. This is true with overwhelming probability in our case.
Otherwise we would obtain parasitic solutions by (3).
Up to this point, the overall complexity of the MinRank attack is
q
(
n
+
)(2
n
+
)
3
2
n
q
until
A
becomes singular. We need
to repeat this sampling until we have recovered (
n
+
) linearly independent
equations of small rank. Solving (3) requires Gaussian elimination in (2
n
+
)
variables.
Now we have to deal with the problem that
S
is not a (2
n
+
)
as we expect to sample
q
vectors
ω
∈
F
×
(2
n
+
)square
matrix but a rectangular (2
n
+
)
2
n
matrix. Obviously equation (4) and (5)
are not equivalent any longer, but it holds
×
n
+
2
n
+
n
+
2
n
+
(
i
)
(
i
)
λ
i
S
F
(
i
)
λ
i
S
G
(
i
)
λ
i
F
Sω
+
λ
i
G
Sω
=0
Sω
+
Sω
=0
.
⇒
i
=1
i
=
n
+
+1
i
=1
i
=
n
+
+1
I.e. the probability of choosing
ω
in the kernel of low-rank matrices is still 1
/q
.
This argument hides a slight heuristic. If we choose
ω
2
n
q
∈
R
F
,
Sω
is not a
2
n
+
q
any longer and thus the rows of the matrix in fig. 4
are not randomly chosen. Nevertheless they are independent and thus formula
(6) should be a good approximation. Our experiments in table 1 confirm this.
The backward direction is not true, as 2
n
+
vectors of lenght 2
n
are always
linearly dependent and thus we obtain
q
parasitic solutions. The overall attack
cost is therefore
random element in
F
(
n
+
)
q
+1
(2
n
+
)
3
.
Unfortunately, the authors of [9] did not provide concrete security parameters.
However, using their security analysis, we derived
q
=31
,n
=17
,
=4fora
claimed security level of 2
80
. Using our attack, this reduces to 2
45
to separate
the upper from the lower level. We have broken this set of parameters in about 1
day, see Table 1. Moreover, we can ignore the embedding modifier, as explained
in [2, Sect. 5]. In a nutshell, we work on the maximal rank of the corresponding
matrices. However, the embedding modifier will only
decrease
the rank and hence
not increase its maximum. Hence, the difference from fig. 3 still holds. Once we
have separated these layers, the rest of the attack is equal to Billet/Macario-Rat
[4], although we have to take the Double-Layer structure into account. First,
we separate out the two layers
F
G
. Using the algorithm of Billet/Macario-
Rat, we can separate the variables of the
F
-layer into
x
1
,...,x
n
+
(output of
Billet/Macario-Rat) and
x
n
+
+1
,...,x
2
n
+
(others). Using these, we have the
variable mixing
S
, the equation mixing
T
, and the inner layer
X
2
and
for the
first
layer
F
. For the second,
i.e.
the
G
-layer, it is a bit more complicated as we are
dealing with
αX
2
+
β
(
x
1
,...,x
n
+
)
X
+
γ
(
x
1
,...,x
n
+
)
.
