Cryptography Reference
In-Depth Information
little attention has been given to provable security for the UOV and the HFE
schemes. Although Courtois studied provable security against key-only attack
on Quartz which is a variant of HFE [8], the security against chosen-message
attack is unclear. In this paper, we study provable security of the UOV and the
HFE signature schemes in the sense of EUF-CMA.
We note that it is not clear whether the UOV and the HFE signature schemes
satisfy EUF-CMA or not, even if their underlying trapdoor functions are assumed
to be one-way. The UOV and the HFE signature schemes employ the well-known
“hash-and-sign” paradigm like the Full-Domain Hash (FDH) scheme, which is
formalized by Bellare and Rogaway [1]. Let
f
be a trapdoor one-way permuta-
tion and
f
−
1
its inverse. Specifically, they showed that if
H
is a hash function
}
∗
to the domain of
f
−
1
, then the FDH is provably secure against
chosen-message attack in the random oracle model. However, unfortunately each
underlying trapdoor function of the UOV and the HFE is not permutation.
from
{
0
,
1
Our Contribution.
First, we suggest that a usual security proof for the Full-
Domain Hash scheme cannot directly apply to that of the UOV and the HFE
signature schemes. In the security proof for FDH-like schemes, a signing oracle
has to sample signatures from actual distribution. However, the simulation of
the signing oracle for the UOV and the HFE schemes might not be done by the
usual manner, since their signatures are not uniformly distributed.
The UOV function consists of a secret non-bijective function
F
UOV
(
x
1
,...,x
n
,
x
n
+1
,...,x
n
+
v
). We call
x
1
,...,x
n
oil variables and
x
n
+1
,...,x
n
+
v
vinegar vari-
ables. Once a set of randomly chosen vinegar variables is fixed as
x
n
+1
,...,x
n
+
v
,
the number of elements included in the range of the map (
x
1
,...,x
n
)
→
F
UOV
(
x
1
,...,x
n
,x
n
+1
,...,x
n
+
v
) is determined by the choice of (
x
n
+1
,...,x
n
+
v
).
In the signing algorithm, a signer repeatedly chooses sets of vinegar variables
until the range covers the chosen hash value. This makes the vinegar variables
non-uniform.
On the other hand, the HFE function consists of a secret non-bijective function
F
HFE
.Since
F
HFE
is a univariate mapping on a big field with degree which is less
than some parameter
d
, it is known that each element in target space of
F
HFE
has 0 to
d
preimages. Note that, for a map
f
:
A
→
B
,wecall
B
target and
{
range of
f
, respectively. In the signing algorithm, a signer randomly
chooses one of preimages of a hashed message. Thus the difference of the number
of preimages causes that signatures are not uniformly distributed.
Then, we show that the UOV and the HFE signature schemes can be modified
into ones achieving the EUF-CMA without changing each underlying trapdoor
function. The modifications require some additional cost, but are simple and
straightforward. In particular, the modified signature-generation process makes
the distribution of signatures uniform. The security of the modified schemes is
proved in the random oracle model under an assumption that the underlying
trapdoor function is one-way.
f
(
a
)
|
a
∈
A
}
Related Work.
Gentry et al. introduced a new notion of a trapdoor function with
preimage sampling and gave a lattice-based concrete example which is surjective
