Cryptography Reference
In-Depth Information
than
ε
. We can transform any
(
ε,
Q
,
T
)
-adversary into an algorithm which, given the
g
x
output
(
p
,
q
,
g
,
y
)
from Setup, outputs x such that y
=
mod
p, with a complexity
O
QT
, and a probability of success close to 1.
ε
log
(
g
k
Note that if
k
→
mod
p
) mod
q
looks like a random function, then we have
=
(log
q
). Indeed, for a random function over
Z
q
, there are less than
q
c
log
q
O
(
c
log
q
)!
possible
sets of
c
log
q
pairwise different elements and every single set is mapped onto a single
value with probability
q
1
−
c
log
q
. So the probability that such a set exists is less than
q
/
(
c
log
q
)! This becomes very small for large
q
.
Proof.
Let (
M
M
has never
been queried to
H
(neither directly nor by the Sig oracle), then the probability that
h
,
h
,
r
,
s
) be the output of
A
. First of all, we notice that if
r
||
=
H
(
r
||
M
)is1
/
q
. If we replace
A
by an algorithm which decides to fail if
r
||
M
was not queried, the new probability of success is greater than
ε
−
1
/
q
, which can be
approximated to
ε
. So from now on we assume that
r
||
M
was always queried to
H
.
to query
H
with some values which are
already known, so we assume that every time
We also notice that there is no use for
A
sends some query to
H
then it was
never queried before to
H
and it cannot be written
r
A
||
M
where
M
was queried to Sig
before and
r
was a part of the output.
The first step of the proof consists of simulating the two oracles
H
and Sig by some
probabilistic algorithms which produce the same statistic behavior. The simulator works
by managing a list of declared (
u
H
(
u
)) pairs. Initially, the list is empty. Every time
the adversary queries an oracle, the simulator uses the defined list, may insert a new
pair, and may decide to abort the simulation. We will show that the probability to abort
is negligible. Here is how the simulator works.
,
1:
if
oracle H is queried
then
2:
let
u
be the query
3:
pick a random
h
4:
insert (
u
,
h
) in the list
5: output
h
6:
else
7:
let
M
be the query
Z
q
8:
pick
α, β
∈
at random
←
(
g
α
y
β
mod
p
) mod
q
9:
r
←
/β
10:
s
r
mod
q
11:
h
←
s
α
mod
q
12:
if
there is some (
r
||
M
,
h
) pair in the list
then
13:
abort the simulation
14:
else
15:
insert (
r
||
M
,
h
) in the list
16:
output (
h
,
r
,
s
)
17:
end if
18:
end if
Search WWH ::
Custom Search