Cryptography Reference
In-Depth Information
8.1
Eciency in the Case of Group Ring of Dihedral Group
To compare the e
ciency of signature generation in HS scheme and the corre-
sponding Rainbow, we prepare dihedral group and its realization. Let
n
be a
positive integer.
M
1
=(
a
ij
)
,M
2
=(
b
ij
)
∈
M
(
n, K
) is defined as
a
ij
=
1 f
j
b
ij
=
1 f
j
+
i
−
i
≡
1(mod
n
)
,
≡
1(mod
n
)
,
0
otherwise
,
0
otherwise
.
We write
D
n
for the group generated by
M
1
and
M
2
.
D
n
is isomorphic to the
dihedral group with 2
n
elements.
K
[
D
n
] denotes the group ring with coecients
in
K
and associated to
D
n
, then, it is a non-commutative ring of dimension 2
n
−
1,
realized in
(
n, K
).
K
[
D
n
] is closed by a transpose operation because
D
n
is so.
Therefore we can use
K
[
D
n
] as a base ring in HS scheme. Table 1 compares
the eciency of the signature generation in HS scheme and the corresponding
Rainbow. The non-commutative rings used in HS schemes in the table are chosen
by
K
[
D
n
]where
K
=
GF
(256) and
n
=10
,
11
,
12
,
13. These non-commutative
rings satisfy the conditions in Corollary 1. The number of layers in each HS
scheme is chosen by 3, and then the corresponding Rainbow of HS(
K
[
D
n
]; 3)
becomes Rainbow(
K
;
r, r, r
)with
r
=2
n
M
1 by Proposition 3. We estimate the
number of multiplication of
GF
(256) for eciency comparison. M
sig
(HS(
R
;3))
(resp. M
sig
(R(
GF
(256);
r, r, r
))) stands for the number of multiplications in the
signature generation in HS(
R
;3)(resp.Rainbow(
GF
(256);
r, r, r
)). Table 1 shows
that the signature generation of HS scheme is about 50% faster than that of the
corresponding Rainbow.
−
Table 1.
Eciency comparison of HS scheme with the corresponding Rainbow (in
terms of the number of multiplications in
GF
(256))
HS(
R,
3)
HS(
K
[
D
10
]
,
3) HS(
K
[
D
11
]
,
3) HS(
K
[
D
12
]
,
3) HS(
K
[
D
13
]
,
3)
Dimension of
R
19
21
23
25
Matrix size
10
11
12
13
M
sig
(HS(
R
;3))
25353
33233
42581
53521
Corresponding Rainbow
R(
R(19
,
19
,
19)
R(21
,
21
,
21)
R(23
,
23
,
23)
R(25
,
25
,
25)
GF
(256);
r, r, r
)
M
sig
(R(
GF
(256);
r, r, r
))
50198
66766
86618
110050
ratio
50
.
5%
49
.
8%
49
.
2%
48
.
6%
9Con lu on
In this paper, we redefine HS scheme as a scheme in the multivariate public
key cryptosystem, from a scheme whose security is based on the diculty of
integer factorization. For this proposed scheme, we analysed the security against
the attacks of Coppersmith, Stern and Vaudenary for Birational Permutation
scheme, the two attacks of Coppersmith for Sato-Araki scheme, and the Min-
Rank, HighRank and UOV attacks for Rainbow. The proposed HS scheme can
