Cryptography Reference
In-Depth Information
with tag
τ
∗
. Finally,
outputs a
b
for the guess of
b
.If
b
=
b
then
wins
the game. Just as the selective-tag CCA experiment, our goal is to prove that
Adv
tbe
-
stag
-
cca
TBE,A
A
A
(
λ
) is negligible.
Game
1
:
This game is identical to Game
0
, except that when the simulator gen-
erates the (
pk, dk
), the simulator replace (
s
,td
)
S
abo
(
λ,
0
v
)with(
s
,td
)
←
S
abo
(
λ, τ
∗
). Notice that in this game, the simulator still decrypts queries using
the injective function trapdoor
td
, and the ABO function trapdoor
td
is never
used.
←
Game
2
:
This game is identical to Game
1
, except that when the simulator de-
crypts queries, it replaces
x
=
F
−
1
(
td, c
1
)with
x
=
G
−
1
(
td
,τ,c
2
). Note that
the simulator performs all the consistency checks, and
is not allowed to make
queries with tag
τ
∗
, the simulator can always answer the query. Also note that
the injective function trapdoor
td
isneverusedinthisgame.
A
Game
3
:
This game is identical to Game
2
, except that when the simulator gen-
erates the (
pk, dk
), the simulator replaces (
s, td
)
←
S
ltf
(
λ,
injective
)with
(
s,
⊥
)
←
S
ltf
(
λ,
lossy
).
Game
4
:
This game is identical to Game
3
, except that when the simulator gen-
erates the challenge ciphertext
c
∗
=(
c
1
,c
2
,c
3
), it replaces
c
3
=
m
b
⊕
h
(
x
)with
c
3
=
r
ρ
.
←{
0
,
1
}
Observe that the adversary's views in Game
4
are identical for either choice of
b
∈{
0
,
1
}
, because
b
is never used in the game. We show the following results.
Lemma 6.
The adversary's views in Game
0
and Game
1
are computationally
indistinguishable, assuming the hidden lossy branch property of the ABO trapdoor
functions.
Proof.
We show that the adversary's views in Game
0
and Game
1
, conditioned
on any fixed value of
τ
∗
, are computationally indistinguishable.
For any fixed
τ
∗
, assume the adversary's views in Game
0
and Game
1
are dis-
tinguishable, we construct a PPT adversary
to distinguish lossy branches 0
v
B
and
τ
∗
of ABO trapdoor functions. Given an ABO function index
s
which is
generated as either (
s
,td
)
S
abo
(
λ,
0
v
)or(
s
,td
)
S
abo
(
λ, τ
∗
),
←
←
B
generates
, and outputs
pk
=(
s, s
,h
).
(
s, t
)
imple-
ments decryption oracle and generates challenge ciphertexts exactly as in Game
0
and Game
1
which are identical. Note that
←
S
ltf
(
λ,
injective
), and
h
←H
B
B
can do so because it generates the
injective function trapdoor
td
itself.
By the construction the view generated by
is exactly Game
0
when
s
is gen-
erated by
S
abo
(
λ,
0
v
), and is exactly Game
1
when
s
is generated by
S
abo
(
λ, τ
∗
).
Proof is completed.
B
