Cryptography Reference
In-Depth Information
b
5
=(1
,
6
,
4
,
3
,
5
,
5
,
12
,
7
,
0
,
0
,
0
,
0)
,
b
6
=(3
,
1
,
5
,
9
,
9
,
5
,
3
,
1
,
0
,
0
,
0
,
0)
,
b
7
=(9
,
10
,
1
,
6
,
1
,
6
,
5
,
5
,
0
,
0
,
0
,
0)
,
b
8
=(8
,
4
,
3
,
1
,
10
,
12
,
9
,
5
,
0
,
0
,
0
,
0)
,
b
9
=(4
,
9
,
10
,
10
,
7
,
6
,
7
,
3
,
12
,
2
,
0
,
3)
,
10
=(11
,
4
,
8
,
3
,
3
,
7
,
5
,
6
,
1
,
12
,
5
,
0)
,
b
11
=(3
,
3
,
4
,
9
,
6
,
10
,
7
,
6
,
0
,
10
,
12
,
2)
,
12
=(5
,
10
,
11
,
4
,
8
,
7
,
3
,
7
,
8
,
0
,
1
,
12)
,
c
5
=9
,c
6
=1
,c
7
=2
,c
8
=6
,c
9
=8
,c
10
=11
,c
11
=9
,c
12
=0
.
7
Security Analysis for Attacks against Rainbow
Proposition 6.2 implies that attacks against Rainbow are applicable to HS
scheme with
L
=
K
. In this section, we estimate security conditions against the
UOV attack ([13,12]), the MinRank attack ([9,23,3]) and the HighRank attack
([9],[8],[17]), which are well-known attacks against Rainbow without using equa-
tion solvers like XL, Grobner basis algorithm, etc. Our security analysis against
these attacks is obtained by combining the results known for these attacks and
an analogue (Proposition 3) of Uchiyama-Ogurafs result.
UOV Attack.
The UOV attack is effective for the UOV signature scheme
[12], and not for Rainbow. In HS scheme, the UOV attack finds the subspace
B
−
1
(
K
r
)in
K
n
where
B
is the matrix expression of the linear part
of
A
2
. The subspace is searched as an invariant subspace of
W
1
W
−
2
for linear
combinations
W
1
,
(invertible)
W
2
of the matrices corresponding to the quadratic
parts of the components of the public key. From the complexity of the UOV
attack [12] and Proposition 3 we have
Proposition 4.
Let
K
=
GF
(2
a
)
. The following condition is necessary in order
that HS
(
R
;
n
)
may have a security level of
l
bits against the UOV attack:
n−r
{
0
}
×
a
(
n
−
2
r
−
1) + 4 log
2
(
r
)
≥
l,
(
n
=
rn
)
.
Remark 4.
The UOV attack is more ecient in the case of balanced Oil and
Vinegar than in the case of general Unbalanced Oil and Vinegar. Therefore, we
should not choose
n
= 2 in HS scheme, otherwise, HS scheme corresponds to a
balanced Oil and Vinegar scheme.
MinRank Attack.
In the MinRank attack, one solves the MinRank problem
for rank 2
r
. In other words, one finds a (
λ
r
+1
,...,λ
n
)
K
n−r
such that
∈
n
rank(
λ
i
M
i
)
≤
2
r.
i
=
r
+1
where
M
i
is the symmetric matrix corresponding to the quadratic part of the
i
i-th component of the public key. Once such a matrix is found, one can compute
the decomposition
K
n
=
B
−
1
(
K
2
r
n−
2
r
)
⊕
B
−
1
(
K
n−
2
r
)
,
2
r
×{
0
}
{
0
}
×
