Cryptography Reference
In-Depth Information
•
A
If
makes a hash oracle query on a message
m
that was not already in a hash
oracle query, then
B
does the following:
-
B
increments
i
.
-
B
sets
m
i
:=
m
.
-If
i
=
j
then
B
sets
y
i
:=
y
,
σ
i
:= ⊥
and returns
y
i
to
A
.
e
-If
i
=
j
then
B
picks uniformly at random
σ
i
← Z
n
,sets
y
i
:=
σ
i
mod
n
and
returns
y
i
to answer
A
's query.
-
B
adds the triple
(
m
i
,
y
i
,σ
i
)
to the table.
•
If
A
makes a hash oracle query about a message
m
that was already queried before,
then
B
finds
m
=
m
t
for
t
<
i
within a table entry and returns to
A
the value
y
t
in the table entry.
•
If
A
makes a signing oracle query on
m
then
B
proceeds as follows:
- If a hash oracle query was not previously made on
m
, then
itself makes such a
query and updates the table as before. Hence, in the following we may suppose
that whenever
B
makes a signing query on
m
, it has already made a hash query
on
m
and, therefore,
m
is equal to one of the
m
i
in the entries of the table.
-If
i
A
=
j
then there is an entry
(
m
i
,
y
i
,σ
i
)
in the table and
A
returns the signature
σ
i
to
B
.
-If
i
=
j
, then
A
aborts the experiment.
•
Finally,
A
outputs its forgery
(
m
,σ)
. If a hash oracle query was not made by
A
B
=
on
m
, then
does so and updates the table. Hence we may assume that
m
m
t
for some
m
t
in a table entry.
•
If
(
m
t
,σ)
is the forgery output by
A
and
t
=
j
, then
B
outputs
σ
, otherwise the
experiment is aborted.
Let us now analyze
B
's behavior and estimate its probability of success, i.e., the
e
probability that
B
outputs a value
σ
such that
σ
≡
y
(
mod
n
)
. First of all we
observe that
B
is indeed a PPT algorithm and that the initial choice of the index
j
made by
B
can be interpreted as
B
's guess at the index of the hash oracle query made
by
A
about the message
m
whose signature will be output by
A
at the end. If this
guess is not correct then
B
will fail, but if
B
guessed right then the view of
A
when
run as a subroutine of
B
is identically distributed to the view of
A
in experiment
Sign
uf-cma
A,
FDH
(
k
)
. This is because the hash queries made by
A
are answered by
B
with
values chosen uniformly at random in
Z
n
. Indeed, the query on
m
j
is answered by
the randomly chosen
y
and the queries on messages
m
i
for
i
=
j
are answered
:=
)
(σ
i
)
σ
i
. Since RSA
as
y
i
RSA
for randomly chosen
is a permutation of
(
n
,
e
(
n
,
e
)
Z
n
, these hash values are uniformly distributed in
Z
n
, which matches the expected
behavior of the random oracle
H
. In addition to all this, we also remark that
A
does
not obtain any information about the value
j
that was randomly chosen by
B
. Thus
the probability that
outputs a valid forgery is the same as its probability of success
in the experiment
Sign
uf-cma
A
A
,
FDH
(
k
)
and hence is equal to
ε(
k
)
.
In this case, if the output of
A
is
(
m
,σ)
and
m
=
m
j
we have that
Ve r
e
mod
n
(
pk
,
m
,σ)
=
1 and hence
σ
=
y
, so that
B
succeeds in the
RSA
B
,
Gen
RSA
(
k
)
