Cryptography Reference
In-Depth Information
x
v
)=
y
4:
until
{
z
n
|
F
UOV
(
z
n
,
}
=
∅
x
n
∈
R
{
z
n
|
x
v
)=
y
F
UOV
(
z
n
,
}
;
5:
x
v
);
7:
return
σ
=(
x, r
)
The verification algorithm
VerUOV
pk
(
σ, M
) returns 1 if
P
UOV
(
x
)=
H
(
M
S
−
1
(
x
n
,
6:
x
←
r
), oth-
erwise returns 0. We treat the hash function
H
as the random oracle in our
analysis. If
l
is large enough, then a random salt
r
is fresh every time with
overwhelming probability. Therefore, each
y
is independently and uniformly dis-
tributed over
k
n
, and the output
x
and
r
of the above signing algorithm are also
uniformly distributed over
k
n
+
v
and over
||
l
, respectively.
Next, we show the security of the slightly modified UOV scheme against
chosen-message attack.
Theorem 1.
If the UOV function is
(
,t
)
-secure, the modified UOV scheme is
(
, t, q
H
,q
s
)
-secure, where
=
(
q
H
+
q
s
+1)
/
(1
{
0
,
1
}
(
q
H
+
q
s
)
q
s
2
−l
)
,
t
=
t
−
(
q
H
+
q
s
+1)(
t
UOV
+
O
(1))
,and
t
UOV
is running time to compute the UOV function
P
UOV
.
Proof sketch.
This proof is similar to a usual proof for FDH-like signature
schemes. Here we briefly describe the simulation of the random oracle and the
signing oracle. In the simulation of the random oracle, the simulator answers
just a random value
h
−
k
n
only
once. In the simulation of the signing oracle, the simulator answers a signature
σ
=(
x, r
)andsets
H
(
M
k
n
, but returns the given challenge
y
∈
R
∈
l
.
Note that, on condition where random variables (
x, r
) are output of the signing
algorithm taking input
M
, the conditional distribution of hash values
H
(
M
k
n
+
v
and
r
||
r
)
←
P
UOV
(
x
)where
x
∈
R
∈
R
{
0
,
1
}
||
r
)
∈
R
k
n
+
v
. Because the value
x
output by the signing algorithm is uniformly distributed over
k
n
+
v
and satisfies
P
UOV
(
x
)=
H
(
M
is identical to the distribution of
P
UOV
(
x
)where
x
||
r
). The details of this proof are given in Appendix A.
Eciency of the modified UOV.
Let
p
i
be the probability that the rank of
A
(
x
n
+1
,...,x
n
+
v
)isequalto
i
where (
x
n
+1
,...,x
n
+
v
)
∈
R
k
v
. We assume
that the probability
p
i
follows the formula (1). On condition that the rank of
A
(
x
n
+1
,...,x
n
+
v
)isequalto
i
at the step 1, the conditional probability that
it does not repeat the loop again is 1
/q
n−i
and the conditional expectation of
the number of loops is
q
n−i
. For example, in the case of (
q, n
)=(2
8
,
10), the
probabilities
p
i
that the expected number of loop
q
n−i
is 1, 2
8
,2
16
,and2
24
are
about 0
.
996, 2
−
8
,2
−
32
,and2
−
72
, respectively. The expected number of loops
n
i
=0
p
i
q
n−i
is 2
.
0.
On the other hand, in the original signing algorithm, the probability to es-
cape the loop with a set of vinegar variables
x
v
)is
equal to
i
is
p
i
/q
n−i
. Thus, it returns without repeating loops with probability
x
v
such that the rank of
A
(
i
=0
p
i
/q
n−i
. Accordingly, the expected number of loops is 1
/
(
i
=0
p
i
/q
n−i
).
Using the formula (1), 1
/
(
i
=0
p
i
/q
n−i
)=1
.
004 if (
q, n
)=(2
8
,
10). Therefore,
the impact on eciency on the modified UOV is limited.
Then, we mention the size of the signature. Since the modification requires
an additional random salt, the length of the signature increases by at least
log(
q
s
(
q
H
+
q
s
))-bits, This is about 90-bits.
