Cryptography Reference
In-Depth Information
1. If
H
1
(
ID
∗
)
=
w
0
,then
B
aborts.
randomly picks
r
1
,r
2
∈
Z
p
,astring
σ
∗
∈{
n
, and a random
2. Otherwise,
B
0
,
1
}
,where
U
1
=
g
r
1
,
sets the ciphertext
C
∗
=
U
1
,U
2
,V
∗
,W
∗
bit
β
∈{
0
,
1
}
.
B
n
.Noticethat
g
r
1
1
=
U
2
=
g
r
2
,
V
∗
,
W
∗
are two random strings from
{
0
,
1
}
)
r
1
/x
,
g
r
2
=(
g
y−w
0
+
w
0
)
r
2
/y
, thus the real randomness factors are
(
g
x−w
0
+
w
0
1
2
with
C
∗
.
We remark that
C
∗
is a valid ciphertext with probability at most 1
/p
. However,
two claims below show that this does not affect the validity of the security
reduction at all.
Phase 2.
r
1
=
r
1
/x
,
r
2
=
r
2
/y
.
B
responds to
A
B
proceeds in the same way as it did in Phase 1.
outputs its guess
β
for
β
.
Guess.
A
When the
IND
-
ID
-
CCA
game finishes, for each tuple
v
1
,v
2
,θ
on the
L
2
list,
B
computes
Z
1
=
v
1
/r
1
1
,
Z
2
=
v
1
/r
2
,
T
x
=(
Z
1
/T
1
)
1
/c
0
,
T
y
=(
Z
2
/T
2
)
1
/c
0
,then
submits (
T
x
,T
y
)toitstwin
q
-BDHI decision oracle until the decision oracle
returns true.
B
outputs the associated (
T
x
,T
y
) as its answer to the twin
q
-BDHI
challenge.
It is easy to see that if
queries
H
2
at (
v
1
,v
2
), where
v
1
=
e
(
g
1
,g
1
)
r
1
/x
and
v
2
=
e
(
g
2
,g
2
)
r
2
/y
,then
Z
1
=
e
(
g
1
,g
1
)
1
/x
=
e
(
g
1
, g
1
)
f
(
x
)
2
/x
,
Z
2
=
e
(
g
2
,g
2
)
1
/y
=
e
(
g
2
, g
2
)
f
(
y
)
2
/y
;
Z
1
/T
1
=
e
(
g
1
, g
1
)
c
0
/x
,
Z
2
/T
2
=
e
(
g
2
, g
2
)
c
0
/y
. Therefore, the as-
sociated
T
x
=(
Z
1
/T
1
)
1
/c
0
=
e
(
g
1
, g
1
)
1
/x
and
T
y
=(
Z
2
/T
2
)
1
/c
0
=
e
(
g
2
, g
2
)
1
/y
are the desired answer. We borrow the proving technique from [7] to show that
if algorithm
A
does not abort, it outputs the correct answer (
T
x
,T
y
)withprob-
ability at least 2
.
Let
B
B
aborts during the simulation above,
F
be
abort
be the event that
the event that algorithm
A
issues a query for
H
2
(
v
1
,v
2
) during the simulation
above. Define event
F
=
F
, which means the probability that at the end
of the simulation (
v
1
,v
2
) appears in some entry on
L
2
if
|
abort
B
does not abort. We
show that Pr[
F
]
outputs (
T
x
,T
y
)with
probability at least 2
if it does not abort. We also study the event
F
in the
real attack game, namely the event that
≥
2
. This will prove that algorithm
B
issues a query for
H
2
(
v
1
,v
2
)when
communicating with a real challenger and a real random oracle for
H
2
.
A
Claim 1:
Pr[
F
] in the simulation above is equal to Pr[
F
] in the real attack.
Proof.
Let
F
be the event that
makes a query for
H
2
(
v
1
,v
2
)inoneofitsfirst
queries to the
H
2
oracle in the simulation that
A
B
does not abort. Let
F
be
makes a query for
H
2
(
v
1
,v
2
)inoneofitsfirst
queries to the
H
2
oracle in the real attack. We prove by induction on
that Pr[
F
]isequalto
Pr[
F
] in the simulation for all
the event that
A
0. Clearly Pr[
F
0
]=Pr[
F
0
] = 0. Now suppose
that for some
>
0wehavethatPr[
F
−
1
]isequaltoPr[
F
−
1
]. We show that
the same holds for
F
and
F
. We know that:
Pr[
F
]=Pr[
F
|
≥
F
−
1
]Pr[
F
−
1
]+Pr[
F
|¬
F
−
1
]Pr[
F
−
1
]
¬
=Pr[
F
−
1
]+Pr[
F
|¬
F
−
1
]Pr[
F
−
1
]
¬
(4)
Search WWH ::
Custom Search