Cryptography Reference
In-Depth Information
We argue that Pr[
F
|¬
F
]isequaltoPr[
F
|¬
F
−
1
] in the real attack. To see this
does not issue a query for
H
2
(
v
1
,v
2
), its view during
the simulation is identical to its view in the real attack (against a real challenger
and a real random oracle for
H
2
), because all responses to
H
1
,
H
2
queries and
the challenge are distributed as in the real attack. We also remark that if
observe that as long as
A
A
issues the query for
H
2
(
v
1
,v
2
),
A
will distinguish the simulation from the real
attack by detecting the challenge is not a genuine one, however, this does not
affect the security reduction. Therefore, Pr[
F
|¬
F
−
1
]
in the real attack. It follows by (4) and the inductive hypothesis that Pr[
F
]in
the real attack is equal to Pr[
F
] in the simulation. By induction on
we obtain
that Pr[
F
]isequaltoPr[
F
] in the real attack.
F
−
1
]isequaltoPr[
F
|¬
Claim 2:
In the real attack we have Pr[
F
]
≥
2
.
never issues a query for
H
2
(
v
1
,v
2
) then the
decryption of
C
is independent of
Proof.
In the real attack, if
A
's view (since
H
2
(
v
1
,v
2
) is independent of
A
's view). Therefore, in the real attack Pr[
β
=
β
|¬
A
F
]=1
/
2. By definition of
Pr[
β
=
β
]
A
, we know that in the real attack
|
−
1
/
2
|≥
. We show that these
two facts imply that Pr[
F
]
≥
2
. To do so we derive upper and lower bounds on
Pr[
β
=
β
]:
Pr[
β
=
β
]=Pr[
β
=
β
|¬
F
]+Pr[
β
=
β
|
F
]Pr[
¬
F
]Pr[
F
]
F
]+Pr[
F
]=
1
F
]+Pr[
F
]=
1
2
+
1
Pr[
β
=
β
|¬
≤
F
]Pr[
¬
2
Pr[
¬
2
Pr[
F
]
,
F
]=
1
1
2
Pr[
F
]
.
Pr[
β
=
β
]
Pr[
β
=
β
|
≥
=
F
]Pr[
¬
2
−
Pr[
β
=
β
]
1
It follows that
≤|
−
1
/
2
|≤
2
Pr[
F
]. Therefore, in the real attack
Pr[
F
]
≥
2
.
To complete the proof we still have to bound the probability that
B
aborts during
the game. Throughout the simulation,
B
will abort the game for the following
two reasons:
issues the private query on
ID
∗
, the probability of which is
Q
e
/Q
h
1
.
1.
A
does not choose
ID
∗
as the challenge identity, the possibility of which is
2.
A
1
−
1
/
(
Q
h
1
−
Q
e
).
So the probability that
B
does not abort during the simulation is
]=
1
=
Q
e
Q
h
1
1
Q
h
1
−
1
Q
h
1
Pr[
−
.
(5)
abort
Q
e
Therefore the advantage of
B
against strong twin BDHI problem is
1
Q
h
1
Adv-2BDHI
B
≥
Pr[
F
|
abort
]Pr[
]=2
·
.
(6)
abort
Search WWH ::
Custom Search