Cryptography Reference
In-Depth Information
We claim that for any v = 0,...,t
|p
1
−p
2
|≤ 2ε
1
We next prove the claim. Consider the following key indistinguishability
adversary for some parameter v. B
1
follows the structure of the experiments
Exp
1
,Exp
2
. It first provides as output the index j[w]; this would be the key
that will be attacked for key indistinguishability. Following the game-based
definition, B
1
receives the keys of all users that are outside of S
j[w]
as well
as it is given oracle access to encryption and decryption for any key j that
corresponds to a subset of S
j[w]
. B
1
proceeds to simulate the challenger and
the adversary A as in Exp
2
. Based on the key material that is available to
B
1
, it can perform the simulation without di
culty except when the adver-
sary decides to corrupt a user u ∈ S
j[w]
. In such case B
1
fails and returns
0. This completes the description of B
1
. Based on our assumption about key
indistinguishability we know that |Prob[Exp
key−ind
B
1
(1
n
)] −1/2|≤ ε
1
.
We observe that Prob[Exp
key−ind
B
1
(1
n
)|b = 0] = 1−p
1
. This holds as the
only seeming difference between the way B
1
operates in the conditional space
b = 0 and the experiment Exp
1
is the event when a party in S
j[w]
is corrupted.
In this case B
1
returns 0. For the same event in the experiment Exp
1
we
observe that the end condition will force also a 0 output. In a similar fashion
it holds that Prob[Exp
key−ind
B
1
(1
n
)|b = 1] = p
2
. Based on this we obtain the
proof of the claim.
We next claim that for any v = 1,...,t,
|p
v−1
2
−p
2
|≤ 2ε
2
We prove the claim. Consider the following CCA1 key encapsulation ad-
versary with a parameter v. B
2
follows the structure of the experiment Exp
2
.
To break the security claim of the underlying symmetric encryption scheme
(
E
,
D
), B
2
, is given access to encryption-decryption oracle of the primitive. B
2
has also access to the decryption/encryption under a key k that is unknown
to her. She is then challenged with plaintext-ciphertext pair (c,m
1
) for which
either c =
E
k
(m
1
) or c =
E
k
(m) for some random message m that has the same
length with m
1
. She is asked to test if the pair is a correct plaintext-ciphertext
pair.
B
2
will simulate the experiment Exp
2
. B
2
will focus its attack on the key of
the j[w]-th subset. In the initial stage it will simulate A as in the experiment
Exp
2
by answering all queries except those that involve the j[w]-th subset
that will be answered by the encryption and decryption oracle available to
B
2
. In the second stage, B
2
will be given the challenge (c,m) where either
m is the proper plaintext of c or it is randomly selected. B
2
will prepare a
challenge for A in the security game Exp
2
by setting the v-th location of the
challenge ciphertext with c and the remaining positions from v+1,...,s with
the appropriate encryptions of m as dictated in the revocation instruction ψ
∗
