Cryptography Reference
In-Depth Information
operation in our proposed scheme is more ecient than that of the original.
Moreover, if we use a non-commutative ring with ecient arithmetic operation,
we can achieve a high processing speed.
This paper is organized as follows.
2 briefly reviews Birational Permutation
scheme and the attack described by Coppersmith, Stern and Vaudenary.
§
3re-
views Sato-Araki scheme and the two attacks described by Coppersmith against
the scheme.
§
§
4 redefines HS scheme as a scheme that deals with finite fields as
base rings.
5 analyzes security measures against the attack of Coppersmith,
Stern and Vaudenary and the two attacks of Coppersmith.
§
6 describes how
Uchiyama and Ogura reduced (proposed) HS scheme to Rainbow, and gives an
example of the reduction.
§
7 analyzes security against UOV, MinRank and High-
Rank attacks, which are attacks against Rainbow.
§
8 observes the eciency of
signature generation in HS scheme and compare the eciency of signature gen-
eration in HS scheme and the corresponding Rainbow.
§
9 concludes the paper.
In the appendix, we extend HS scheme using rings with involution.
§
2
Birational Permutation Scheme
In this section, we summarize the attack described by Coppersmith, Stern and
Vaudenary against Birational Permutation scheme. We will analyze this attack
in the extended HS scheme later. First, we describe Birational Permutation
scheme [21].
Let
p
and
q
be prime numbers and
N
=
pq
. Let us assume that the factoriza-
tion of
N
is dicult. Let
n
be a natural number. For
k
=2
,
3
,...,n
, we define
g
k
:(
)
n
Z
/N
Z
→
Z
/N
Z
by a homogeneous quadratic polynomial over
Z
/N
Z
as
follows:
k−
1
g
k
(
x
1
,x
2
,...,x
n
)=
a
ik
x
i
x
k
+
a
ij
x
i
x
j
,
i
=1
1
≤i≤j≤k−
1
where
a
ij
∈
Z
/N
Z
. The central map of Birational Permutation scheme is con-
structed by
)
n
)
n−
1
.
G
=(
g
2
,g
3
,...,g
n
):(
Z
/N
Z
→
Z
/N
Z
(
The key generation, the signature generation, and the verification of Birational
Permutation scheme are described as follows.
Key Generation
The secret key consists of prime numbers
p
and
q
, the central map
G
and two
ane (linear) transformations
A
1
:(
)
n−
1
)
n−
1
,A
2
:(
)
n
Z
/N
Z
→
(
Z
/N
Z
Z
/N
Z
→
)
n
.
The public key consists of
N
and the composite map
F
=
A
1
◦
(
Z
/N
Z
G
◦
A
2
=
)
n
)
n−
1
.
(
f
2
,f
3
,...,f
n
):(
Z
/N
Z
→
(
Z
/N
Z
