Cryptography Reference
In-Depth Information
25. Sakumoto, K., Shirai, T., Hiwatari, H.: Public-Key Identification Schemes Based on
Multivariate Quadratic Polynomials. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS,
vol. 6841, pp. 706-723. Springer, Heidelberg (2011)
A Proof of Theorem 1
Assume that, on the modified UOV signature scheme, there is an adversary
A
who takes a public key
pk
generated via (
pk
,
←
GenUOV
∗
(1
λ
), after at most
q
H
(
λ
) queries to the random oracle,
q
s
(
λ
) signature queries, and
t
(
λ
) processing
time, then outputs a valid signature with probability at least
(
λ
). Then, we
construct an inverting algorithm
B
that takes
P
UOV
·
)
generated via (
P
UOV
,
·
)
←
GenUOVfunc
(1
λ
) and a challenge
y
∈
R
k
n
, then finds a preimage
x
such that
P
UOV
(
x
)=
y
at
t
(
λ
) processing time with probability at least
(
λ
). We also call
B
the simulator.
The
simulator
takes
as
input
(
P
UOV
,y
)
generated via
(
P
UOV
,
·
)
←
B
GenUOVfunc
(1
λ
), and
y
k
n
, sets a list
L
∈
R
←∅
and
i
←
0, randomly picks
α
, and selects an length of the random salt
l
which is
large enough. The simulator
B
runs
A
on public key
pk
=(
P
UOV
,l
)andsimulates
the random oracle and the signing oracle as follows.
∈{
1
,...,q
H
+
q
s
+1
}
Answering random oracle queries.
Suppose (
m
i
||
r
i
) is a random oracle query.
First,
B
increases
i
by 1. If (
m
i
,r
i
,
·
)
∈
L
,then
B
answers
h
such that (
m
i
,r
i
,h
)
∈
L
.Elseif
i
=
α
,then
B
sets
L
←
L
∪{
(
m
i
,r
i
,y
)
}
answers
y
.Else
B
chooses an
element
h
i
∈
R
k
n
,sets
L
←
L
∪{
(
m
i
,r
i
,h
i
)
}
,andanswers
h
i
.
Answering signing oracle queries.
Suppose
m
i
is a signing oracle query. First,
the simulator
B
increases
i
by 1. The simulator
B
chooses
r
i
∈
R
l
{
0
,
1
}
and
x
i
∈
R
k
n
+
v
and computes
y
i
←
P
UOV
(
x
i
). If (
m
i
,r
i
,
·
∈
L
then
B
aborts. Else
B
)
sets
L
←
L
∪{
(
m
i
,r
i
,y
i
)
}
and answers (
x
i
,r
i
).
Output.
Eventually,
A
outputs a forgery (
x, r
) of some message
m
. Without loss
of generality, we assume that
A
asked the hash query
m
r
beforehand (if not,
B
can do it instead of
A
). If the answer was
y
,weget
x
such that
P
UOV
(
x
)=
y
,thus
B
outputs the preimage
x
. Otherwise, we do not learn anything, then
B
fails.
||
Analysis.
The view of
A
in the successful simulation is properly distributed. In
particular, we note that the value
x
output by the legitimate signing algorithm
is uniformly distributed over
k
n
+
v
, because for any (
x
n
,
x
v
)
k
n
+
v
,
∈
⎡
⎤
x
v
∈
R
k
v
,H
1
,...,H
i
∈
R
k
n
,
x
n
∈
R
{
z
n
|
F
UOV
(
z
n
,
x
v
)=
H
i
}
;
∞
⎣
⎦
Pr
{
z
n
|
F
UOV
(
z
n
,
x
v
)=
H
1
}
=
∅
,...,
{
z
n
|
F
UOV
(
z
n
,
x
v
)=
H
i−
1
}
=
∅
,
x
n
,
x
v
)
{
z
n
|
F
UOV
(
z
n
,
x
v
)=
H
i
}
=
∅
,
(
x
n
,
x
v
)=(
i
=1
Pr
H
∈
R
k
n
,
x
n
∈
R
{
z
n
|
F
UOV
(
z
n
,
x
v
)=
H
}
;
{
z
n
|
F
UOV
(
z
n
,
x
v
)=
H
}
∅
,
x
n
=
x
n
1
q
v
=
1
q
n
+
v
.
Pr
H
∅
=
=
∈
R
k
n
;
{
z
n
|
F
UOV
(
z
n
,
x
v
)=
H
}
=
