Cryptography Reference
In-Depth Information
j
=
m−i
+1
(1
q
−j
)
j
=
n−i
+1
(1
q
−j
)
−
−
.
(1)
j
=1
(1
−
q
−j
)
We use this formula for analyzing the distribution and the eciency on the UOV
signature schemes.
The FDH and the PFDH Schemes.
In the FDH scheme, a signature on a message
M
is generated via
σ
f
−
1
(
H
(
M
)) and verified via
f
(
σ
)=
H
(
M
). Moreover,
in the probabilistic FDH (PFDH) scheme which is parameterized by the length
parameter
l
of random salt, a signature
σ
=(
x, r
) on a message
M
is generated
via
r
←
l
and
x
f
−
1
(
H
(
M
∈
R
{
0
,
1
}
←
||
r
)) and verified via
f
(
x
)=
H
(
M
||
r
).
3 Existing Schemes and Their Analyses
There are many FDH-like schemes in MPKC, for instance, the Matsumoto-Imai
(MI) [20], the HFE [22], and the UOV [16] signature schemes. In this paper,
we study the UOV and the HFE signature schemes, each of which employs a
non-bijective trapdoor one-way function. It is well-known that FDH-like signa-
ture schemes using a trapdoor permutation achieve the EUF-CMA. However,
it is unclear in the case that a non-bijective trapdoor function is used. The
Rabin signature scheme in [2], which is a PFDH-like signature scheme using
non-bijective trapdoor function, has the provable EUF-CMA, since the Rabin
function has the useful property where every element in the range always has
four preimages and the signature is uniformly distributed. On the other hand, in
the UOV and the HFE functions, every element in the range has non-constant
number of preimages. Therefore it seems to be dicult to sample from distri-
bution of signatures without knowledge of trapdoor, because the distribution is
non-uniform. In this section, we review the UOV and the HFE signature schemes,
and analyze distribution of their signatures.
3.1 UOV Signature Scheme
In [23], Patarin designed the Oil and Vinegar (OV) signature scheme. The origi-
nal OV signature scheme was broken by Kipnis and Shamir [17]. However, Kipnis
et al. suggested that the attack does not work if we use more vinegar variables
than oil variables [16]. They also presented such a scheme called the Unbal-
anced Oil-Vinegar (UOV) signature scheme. Cao et al. revisited the Kipnis-
Shamir attack on the UOV scheme [6], and Braeken et al. studied its security
in several aspects [5]. However, no general ecient attack for one-wayness of
the UOV function has been reported so far. Even though Faugere and Per-
ret reported that the one-wayness of the UOV function with only 64-bit out-
put is broken in a complexity bounded by 2
40
.
3
[12], it is applicable to limited
sizes.
