Cryptography Reference
In-Depth Information
x
v
, we consider the
Another Approach for UOV Scheme.
For a vinegar variable
x
v
). In a typical parameter-setting of UOV, it uses
n
map
x
n
→
F
UOV
(
x
n
,
×
n
x
v
). Unfortunately, from the formula (1), a rank of random
square matrix
A
(
−
j
=1
(1
−
q
−j
). This
n
×
n
square matrix is less than
n
with probability
δ
=1
x
n
→
F
UOV
(
x
n
,
x
v
) is not 1-to-1 mapping with non-negligible
means that the map
probability. For example,
δ
0
.
004 if
q
=2
8
and
n
= 10.
We mention another approach which reduces
δ
to a negligible probability.
Let
w
be a positive integer. In this approach, the
m × n
matrix
A
(
x
v
)where
n
=
m
+
w
is used instead of
n
≈
×
n
matrix. Consequently, the UOV function
S
where
F
UOV
:
k
n
+
v
k
m
is defined by
becomes
P
UOV
=
F
UOV
◦
→
T
x
v
))
T
,
F
UOV
(
x
n
,
x
v
)=
A
(
x
v
)
x
n
+(
g
1
(
x
v
)
,...,g
m
(
where
A
(
x
v
)=[
a
i,j
(
x
v
)] is a
m
×
n
matrix and
a
i,j
and
g
i
are the same in
Definition 3. From the formula (1), a rank of random
m
×
n
matrix is less than
−
j
=
w
+1
(1
q
−j
)
q
−w
/
(
q
m
with probability
δ
=1
−
≤
−
1). For example, if
q
=2
8
and
w
=9then
δ
is less than about 2
−
80
. This means that, the map
x
v
) is surjective with probability 1
x
n
δ
. That is, the UOV function
P
UOV
is always
q
v
-to-1 mapping except negligible ratio of domain. As a result, we
can easily prove that the UOV signature scheme is secure against chosen-message
attack. This approach can be also applied to the multi-layer OV schemes [10].
→
F
UOV
(
x
n
,
−
4.2 Modified HFE Signature Scheme
Basic idea for the simple modification of the HFE signing algorithm is to sample
no element with a certain probability which depends on a hash value. In the orig-
inal signing algorithm of HFE, as explained in Section 3.2, the signatures are not
uniformly distributed. To make the distribution uniform, we adjust probability
for repeating the loop.
Here we introduce a positive integer
N
whichisusedasathresholdfora
number of preimages. For simplicity, we suppose
N
=
d
. For an element
y
in
target space of
F
HFE
such that
y
has
i
preimages
{
x
1
, ..., x
i
}
, our modified signing
algorithm randomly chooses an element from
{x
1
, ..., x
i
}
with probability
i/N
.
Accordingly, it chooses no element from
{x
1
, ..., x
i
}
and repeats the loop again
with probability 1
− i/N
. As a result, the signing algorithm returns
x
without
repeating the loop with probability 1
/q
n
1
/ω
(
x
)=1
/q
n
1
/N
where
ω
(
x
) is the number of preimages of
P
HFE
(
x
). The probability apparently does
not depend on
x
. We note that, for any element
y
in target space of
F
HFE
,the
probability
i/N
is at most 1 where
N
=
d
,since
y
has at most
d
preimages in
the HFE function, where
d
is the maximum degree of
F
HFE
. In a practical setting,
the threshold
N
can be set less than
d
, e.g.,
N
= 30, because an element in the
target space of
F
HFE
has a few preimages with overwhelming probability.
The modified HFE
−
signature scheme (
GenHFE
−∗
,
SigHFE
−∗
,
VerHFE
−∗
)is
described as follows. Note that we employ the minus version of the HFE for
security concern of the underlying trapdoor function, but the plain HFE scheme
·
ω
(
x
)
/N
·
·
