Cryptography Reference
In-Depth Information
We then define a series of games Game
1
,...,Game
n−t
p
with gradual changes as
follows: In general, for 1
t
p
,Game
i
is identical to Game
0
except for one
step in the computation of the challenge ciphertext
c
∗
. Recall, in Game
0
we have
c
j
←
TEnc
(
pk
j
,vk
∗
,s
j
), where
s
j
is the
j
-th share of the secret sharing scheme.
In Game
i
we instead do this only for
j>i
, but set
c
j
←
TEnc
(
pk
j
,vk
∗
,
0) for
j
≤
i
≤
n
−
t
p
,Game
i−
1
and Game
i
are identical except
Game
i−
1
sets
c
i
←
TEnc
(
pk
i
,vk
∗
,s
i
), while Gamei
i
sets
c
i
←
TEnc
(
pk
i
,vk
∗
,
0).
Denote by
X
i
for 1
≤
i
.Inotherwords,for1
≤
i
≤
n
−
t
p
the event
b
=
b
in Game
i
. We claim:
≤
i
≤
n
−
Pr[
X
i
]
Pr[
X
i−
1
]
is negligible.
Lemma 3.
For every
1
≤
i
≤
n
−
t
p
, we have
−
The proof of this lemma is given in section 3.2.
Let us now think about the game Game
n−t
p
. When encrypting the challenge
m
b
,only
t
p
shares are used in creating the challenge ciphertext. Then the privacy
of the secret sharing scheme implies that
1
is negligible.
We obtain the following result from the games and lemmas above.
|
Pr [
X
n−t
p
]
−
2
|
(
λ
)=
Pr [
X
0
]
2
Adv
the−cca
THE,A
1
−
=
2
Pr [
X
i−
1
]
Pr [
X
i
]
+Pr[
X
n−t
p
]
Pr [
X
0
]+
n−t
p
1
Pr [
X
0
]
−
−
−
i
=1
Pr [
X
0
]
Pr [
X
i
]
+
2
+
n−t
p
i
=1
1
≤
Pr [
X
0
]
−
Pr [
X
i−
1
]
−
Pr [
X
n−t
p
]
−
t
p
) is polynomial in
λ
,weget
Adv
the
-
cca
since (
n
−
(
λ
) is negligible in
λ
,Theorem
THE,A
1isproven.
3.1 Proof of Lemma 2
Proof.
to attack the one-time signature scheme
as follows: On receiving
vk
generated by
Gen
,
We construct a adversary
B
sets
vk
∗
=
vk
, and generate
B
(
PK,
−−
SK
)
←
ThGen
, and does the same as in Game
0
. Upon any decryption
query of the form
c
=(
c
1
, ..., c
n
,vk
=
vk
∗
,σ
) such that
Ver
(
vk, c
1
, ..., c
n
,σ
)=1,
B
immediately outputs (
c
1
, ..., c
n
,σ
) as a forgery and return
⊥
,otherwise
B
returns the decryption share.
When
creates the challenge ciphertext
c
∗
=(
c
1
, ..., c
n
,vk
∗
,σ
∗
) by running
ThEnc
(
PK,m
b
)exceptthatsignature
σ
∗
is
generated by querying
A
submits challenge plaintexts
m
0
,m
1
,
B
's signing oracle on message
c
1
, ..., c
n
.
It is clear by construction that
B
B
simulates Game
0
to
A
. We now show that if
event
F
happens then
B
outputs a valid forgery. If
F
happens before
A
is chal-
lenged on
c
∗
,then
outputs a valid signature without making any queries, which
is a forgery. If
F
happens after
B
receives
c
∗
viaaquery
c
=(
c
1
, ..., c
n
,vk
∗
,σ
),
A
=
c
∗
we must have (
c
1
, ...c
n
,σ
)
=(
c
1
, ..., c
n
,σ
∗
). In either case,
then because
c
B
's output (
c
1
, ..., c
n
,σ
) differs from its single signature query, and hence is a
forgery. Because the signature scheme is one-time strongly unforgeable, we con-
clude that event
F
happens with negligible probability, as desired.
