Cryptography Reference
In-Depth Information
Table 2.
Time to solve the MinRank problem for Square+ for varying embedding
degree
, but fixed field size
q
= 31, field extension
n
= 17, and plus equations
p
=5.
Each line is based on 11 independent experiments. We see that the running time does
not depend on the embedding degree
.
time [sec]
q
n
p
min
avg
max
0
1590.59
1610.13
1630.91
1
1580.85
1605.42
1624.17
2
1563.80
1600.54
1616.89
3
1587.97
1603.67
1628.78
31
17
5
4
1557.96
1604.47
1626.03
5
1567.56
1610.80
1636.44
6
1584.20
1606.61
1622.34
7
1573.56
1604.07
1621.94
8
1583.91
1609.04
1629.97
9
1575.46
1603.57
1624.08
10
1565.71
1597.58
1618.23
We start with Schorr's method. It uses the following observation: For given
rank
r
, each sub-matrix of size (
r
+1)
(
r
+ 1) must have determinant zero.
Hence, each such determinant gives rise to one equation of degree (
r
+1). For a
(
τ
×
τ
)-matrix, we can form
×
r
+1
2
sub-matrices (selecting
r
+1 rows and columns,
respectively) and hence equations. Assuming that a suciently high proportion
of them is linearly independent, we are able to solve the corresponding system
of equations by linearization. In our case, we have
r
=1and
τ
:= (
n
+
+
p
)
τ
free variables, leading to a total of
n
+
+
2
degree 2 monomials. For
+
p<n
,
this allows to compute a solution in
n
+
+
p
2
3
∈
O
(
n
6
) computations over
F
q
n
+
and is hence polynomial in all security parameters. For the proposed parameters
n
=48
,
=3
,p
= 5 we obtain a total workload of
2
31
.
77
≈
and have hence
broken the scheme.
For the second method, we inspect the kernel of the matrix
H
. Remember
that each kernel element
ω
n
q
n
+
∈
F
has the form
ω
:=
SM
n
+
(0
, ω
2
,...,
ω
n
+
)
˜
for
ω
i
∈
F
q
n
+
and 2
≤
i
≤
(
n
+
). So randomly sampling vectors
ω
∈
R
q
n
+
needs
q
n
+
trials on average to find a kernel element of
H
and is hence
exponential in the security parameters
n,
. It is also impractical for the proposed
parameters. Thus we use the more refined technique from Levy-dit-Vehel
et al.
[12] to solve instances of the MinRank problem. In a nutshell, they do not sample
vectors
ω
but
calculate
them. This is done by generating an overdetermined
n
F
-
system and then solving it with Gröbner base techniques. Note that the attack
complexity grows exponentially with the rank of the target matrix. However, as
this rank is fixed to 1 in our case, we are not concerned by this.
The dimension of the kernel of
H
is (
n
−
MQ
1) in the extension field and thus
we can fix all but one coecient of
ω
at random and still expect a solution.
The corresponding vector therefore becomes (
ω
1
,...,ω
n
−
1
,x
)with
ω
i
∈
F
q
n
+
