Cryptography Reference
In-Depth Information
The verification algorithm
VerUOV
pk
(
σ, M
), on a signature
σ
=
x
and a message
M
, returns 1 if
P
UOV
(
x
)=
H
(
M
). Otherwise, it returns 0. Note that the step 5
can be computed by using the Gaussian elimination.
Analysis of the scheme.
First, we point out that a rank of the
n × n
ma-
trix
A
(
x
v
) defined in Definition 3 depends on a set of vinegar variables
x
v
.
From the formula (1) in Section 2,
n
×
n
random matrix with element on
k
with cardinality
q
has rank
i
∈{
1
,...,n
}
with probability
p
(
q, n, n, i
)=
q
−
(
n−i
)
2
(
j
=
n−i
+1
(1
q
−j
))
2
/
j
=1
(1
−
−
q
−j
). For example,
p
(2
,
80
,
80
,
80)
≈
0
.
289 and
p
(2
8
,
10
,
10
,
10)
0
.
996.
Then, we mention the non-uniformity of signatures on the UOV scheme. At
the step 3, suppose that it chooses a set of vinegar variables
≈
x
v
such that the
x
v
)isequalto
i
. In this case, the map
k
n
k
n
,
x
v
)
rank of
A
(
→
x
n
→
F
UOV
(
x
n
,
is a
q
n−i
-to-1 mapping. Therefore, the ratio of elements
y
in
k
n
such that
x
v
)
is, the higher the probability of ending the loop is. As a result, such a set of
vinegar variables tends to be output more frequently. Thus the signature distri-
bution is non-uniform.
To simulate the signing oracle in the security proof, the simulator has to
sample signatures from the real distribution of UOV. However, it is dicult for
the UOV scheme, since the structure of the secret map
F
UOV
is hidden due to a
secret mapping
S
. To our knowledge, no security proof against chosen-message
attack has been presented on a signature scheme based on the UOV function.
x
v
)=
y
is not empty is 1
/q
n−i
. The higher the rank of
A
(
{
z
n
|
F
UOV
(
z
n
,
}
3.2 HFE Signature Scheme
The HFE cryptosystem is proposed by Patarin [22], which is a generalized ver-
sion of the Matsumoto-Imai cryptosystem [20]. The cryptanalyses on HFE for
certain sets of parameters are presented in many papers [18,11,15]. In particu-
lar, Granboulan et al. estimated the complexity
O
(
n
O
(log
d
)
) of the attack using
Grobner basis algorithm where
q
=2and
d
is polynomial on
n
[15]. In the at-
tack, field equations
x
i
−
x
i
=0,
i
=1
,...,n
, are used in the computations of
the Grobner basis. The field equations can be easily used in the case
q
=2.
The HFE-minus (HFE
−
) function is a variant of the HFE function, which is
not considered to be broken yet. The HFE
−
function is defined as
P
HFE
−
(
x
)=
(
p
1
(
x
)
,..., p
n−m
(
x
)) where the HFE function is
P
HFE
(
x
)=(
p
1
(
x
)
, ...,p
n
(
x
)),
that is, the last
m
components of the output vector of the HFE function is
removed. However, we note that reasonable parameters of the HFE
−
function
are still controversial, and the parameters should be appropriately chosen. For
simplicity, we analyze the plain HFE signature scheme in this section, but its
minus variant also has a similar problem.
The HFE function and its security notion are defined as follows.
Definition 5.
Let
S, T
:
k
n
k
n
be invertible ane transformations,
φ
:
K
→
k
n
the standard linear isomorphism given by
φ
(
a
0
+
a
1
x
+
...
+
a
n−
1
x
n−
1
)=
(
a
0
,a
1
,...,a
n−
1
)
,
q
,
n
,and
d
positive integers,
k
a finite field with cardinality
→
