Cryptography Reference
In-Depth Information
Lemma 7.
The adversary's views in Game
1
and Game
2
are identical.
Proof.
Notice that Game
1
and Game
2
are identical except the decryption op-
erations. These two operations both check that
c
1
=
F
(
s, x
)and
c
2
=
G
(
s
,τ,x
)
for some
x
that they compute, and output
if not. Thus, it suces to show that
this
x
is unique, and both decryption manners find it. In both games, (
s, td
)is
generated by
S
ltf
(
λ,
injective
), and (
s
,td
) is generated by
S
abo
(
λ, τ
∗
).
F
(
s,
⊥
·
)
and
G
(
s
,τ,
=
τ
∗
) are both injective. Thus, there is a unique
x
such that
(
c
1
,c
2
)=(
F
(
s, x
)
,G
(
s
,τ,x
)). In Game
1
x
is found by computing
F
−
1
(
td, c
1
),
while in Game
2
by computing
G
−
1
(
td
,τ,c
2
).
·
)for(
τ
Lemma 8.
The adversary's views in Game
2
and Game
3
are computationally
indistinguishable, assuming the indistinguishability of injective and lossy func-
tions of lossy trapdoor functions.
Proof.
Assume the adversary's views in Game
2
and Game
3
are distinguishable,
then, we can construct a PPT adversary
C
to distinguish lossy and injective func-
tions.Givenanindex
s
which was generated as (
s, td
)
← S
ltf
(
λ,
injective
)or
(
s, ⊥
)
← S
ltf
(
λ,
lossy
),
generates (
s
,td
)
S
abo
(
λ, τ
∗
), and
h
imple-
ments decryption oracle and generates challenge ciphertexts exactly as in Game
2
and Game
3
.Noticethat
C
←
←H
.
C
generates the ABO trapdoor
td
itself, but does not
know the trapdoor
t
corresponding to
s
even if it exists. The views generated by
C
C
is exactly Game
2
when
s
is generated by
S
ltf
(
λ,
injective
), and is exactly Game
3
when
s
is generated by
S
ltf
(
λ,
lossy
). This concludes the lemma.
Lemma 9.
The adversary's views in Game
3
and Game
4
are statistically indis-
tinguishable.
)and
G
(
s
,τ
∗
,
Proof.
)are
lossy functions with image sizes at most 2
n−l
and 2
n−l
. Therefore, the random
variables (
c
1
,c
2
)=(
F
(
s, x
)
,G
(
s
,τ
∗
,x
)) can take at most 2
n−l
+
n−l
Observe that in Game
3
and Game
4
we have
F
(
s,
·
·
2
n−κ
values by our hypothesis in (1). By Lemma 4, and the independence of
x
from
s, s
,wehave
H
∞
(
x
≤
c
1
,c
2
,s,s
)
s, s
)
|
≥
H
∞
(
x
|
−
(
n
−
κ
)=
n
−
(
n
−
κ
)=
κ.
Since
2lg(1
/
) and Lemma 5, we have
Δ
(
c
1
,c
2
,h,h
(
x
))
,
(
c
1
,c
2
,h,r
)
ρ
≤
κ
−
≤
=
negl(
λ
)
,
where
r
←{
ρ
is uniform and independent of all other variables.
In Game
3
we have
c
3
=
m
b
⊕
0
,
1
}
h
(
x
), while in Game
4
we have
c
3
=
r
ρ
,
←{
0
,
1
}
r
. Thus, the two games are statistically
indistinguishable, and this completes the proof.
which is identically distributed to
m
b
⊕
5
Discussions and Comparisons
Discussions.
Since the scheme proposed in section 4 is a selective-tag CCA se-
cure TBE, It can be used as a component for our general threshold scheme. Re-
mark that the scheme proposed above actually is not full-tag CCA secure. We
can easily break the full-tag CCA security by simply XOR
c
3
with a message we
know and query to the decryption oracle. We also point out that our construction
