Cryptography Reference
In-Depth Information
3.2 Proof of Lemma 3
such that
Pr [
X
i
]
Pr [
X
i−
1
]
is non-
Proof.
Assume existing 1
≤
i
≤
n
−
t
p
−
negligible. We construct an adversary
C
i
who succeeds in breaking selective-tag
CCA of
as a subroutine.
Just as the “global” setting of the games sequence,
TBE
by using
A
C
i
first chooses a one-time
signature key pair (
vk
∗
,sk
∗
)
←
Gen
(
λ
), then outputs the challenge tag
τ
∗
=
vk
∗
.
C
i
gets a public key
pk
for
1)
public/secret keys by himself. These public keys, as well as the last
t
p
secret keys,
are given to
TBE
,sets
pk
i
=
pk
, and generates the remaining (
n
−
A
.Adversary
C
i
honestly simulates the running of Game
i−
1
/Game
i
until
A
submits the challenge (
m
0
,m
1
). At this point
C
i
chooses a random bit
b
,
computes the shares (
s
1
, ..., s
n
)
Share
(
m
b
), and prepares
c
j
←
for
j
=
i
just as
C
i
outputs the challenge (
s
i
,
0) in its own
CCA experiment. Upon receiving ciphertext
in Gamei.
i−
1
and Game
i
.Furthermore,
c
∗
,itsets
c
i
c
∗
, signs whatever
=
is needed, and give the challenge ciphertext
c
∗
to
A
.
We specify how
C
i
deals with oracle queries of
A
.Noticethat
C
i
can decrypt
all ciphertexts
c
j
for
j
=
i
by himself, since the corresponding decryption keys
are known. As for
c
i
, by Lemma 2
does not reuse the challenge value
vk
∗
,this
A
means that
C
i
can always submit
c
i
to its own decryption oracle using the tag
=
vk
∗
. Finally
τ
=
vk
C
i
outputs 1 iff
A
correctly predicts
b
. This completes the
description of
C
i
, and it is not hard to see that
C
i
gives a perfect simulation of
depending on which of
s
i
either game Game
i−
1
or Game
i
or 0 was encrypted.
It is easy to know that the advantage of
C
i
to attack selective-tag CCA of
TBE
Pr [
X
i−
1
]
.
According to the assumption at
the beginning of the proof, we obtain that
Adv
tbe
-
stag
-
cca
TBE,C
i
(
λ
)=
2
Pr [
X
i
]
is
Adv
tbe
-
stag
-
cca
TBE,C
i
−
(
λ
) is non-negligible,
this is a contradiction to the security of
TBE
scheme.
4
Selective-Tag CCA Secure TBE
In this section, we demonstrate a public key encryption which is secure against
selective-tag and adaptive chosen ciphertext attack, from lossy trapdoor function
[23]. Peikert and Waters proved that the scheme is passively chosen ciphertext
secure (CCA1). However, we show that it also give adaptive chosen ciphertext
security under a selective-tag setting. We first review some useful definitions.
Lossy Trapdoor Functions.
A collection of (
n,
)-lossy trapdoor functions is
a triplet of PPT algorithms (
S
ltf
,F,F
−
1
) such that:
1.
S
ltf
(
λ,
injective
) outputs a pair (
s, td
)
∈{
0
,
1
}
n
×{
0
,
1
}
n
. The algorithm
n
,and
F
−
1
(
td,
F
(
s,
·
) computes an injective function
f
s
(
·
{
0
,
1
}
·
)over
)com-
putes
f
−
1
s
).
2.
S
ltf
(
λ,
lossy
) outputs
s
(
·
n
. The algorithm
F
(
s,
∈{
0
,
1
}
·
) computes a func-
n
whose image has size at most 2
n−
.
3. The description of functions sampled using
S
ltf
(
λ,
injective
)and
S
ltf
(
λ,
lossy
) are computationally indistinguishable.
tion
f
s
(
·
)over
{
0
,
1
}
