Cryptography Reference
In-Depth Information
which helps an adversary to transform the public key into a system of poly-
nomials with a form of a central map of Rainbow. From the complexity of the
MinRank attack [23] and Proposition 3 we have
Proposition 5.
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 MinRank attack:
r
)(
n
2
/
3+
nr/
3
r
2
/
6))
2
ar
+log
2
((
n
−
−
≥
l.
HighRank Attack.
In the HighRank attack, one finds a linear combination,
M
,of
M
r
+1
,...,M
n
(as above) such that rank(
M
)=
n
−
r
. The probability
r
is
q
−
(
n−r
)
.Once
such a value of
M
is found, one can compute the decomposition
K
n
=
B
−
1
(
K
n−r
that the rank of a random linear combination is equal to
n
−
r
)
⊕
B
−
1
(
K
r
)
,
n−r
×{
0
}
{
0
}
×
which helps an adversary to transform the public key into a system of polyno-
mials with a form of central map of Rainbow. Therefore, from the complexity of
the HighRank attack [8] and Proposition 3 we have
Proposition 6.
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 HighRank attack:
ar
+log
2
(
n
3
/
6)
≥
l.
From Proposition 4, 5 and 6, we have
Corollary 1.
Inthecaseof
K
=
GF
(256)
, we must choose a non-commutative
ring with dimension more than
10
and
˜
n>
2
in order that HS
(
R
;
n
)
has the
80-bits security level against UOV, MinRank and HighRank attacks.
8E
encyofHSScheme
Any non-commutative ring
R
can be embedded in a matrix ring
(
l, K
)for
some positive integer
l
.Ifwecanchooseasmall
l
, the arithmetic operation
of
R
becomes ecient. The number of field multiplication in solving a linear
equations appearing in each layer in the signature generation in our proposed
scheme estimated as
O
(
l
3
) because the equations is of form of equations with
respect to
M
X∈
M
(
l, K
),
A
.
X
=
B
(
A
,
B∈
M
(
l, K
))
.
On the other hand, that in the corresponding Rainbow estimated as
O
(
d
3
)where
d
is the dimension of
R
because of Proposition 3. Thus, if
l<d
is satisfied, the
signature generation of our proposed scheme is more ecient than that of the
corresponding Rainbow.