Cryptography Reference
In-Depth Information
Recall that the broadcast encryption scheme
BE
based on a subset cover set
system Φ and transmits a vector of ciphertexts h
E
k
j
1
(m),...,
E
k
j
s
(m)i where
(
E
,
D
) is the underlying symmetric encryption scheme of
BE
and the key k
j
i
is
the key that corresponds to the subset S
j
i
. We denote the tracer by T
SC
who
queries the transmissions of the form Encrypt
v
(ek,m,ψ) for v = 0,1,...,s
for which it holds that we have substituted the first v plaintexts with random
strings. Specifically,
Encrypt
v
(ek,m,ψ) = hj
1
,..., j
s
,
E
k
j
1
(R
1
),...,
E
k
j
v
(R
v
),
E
k
j
1
(m),...,
E
k
j
s
(m)i
(4.1)
where R
i
is a random string of the same length as the message m. Given
that the adversary-tracer pair is σ-admissible the adversary will be required
to respond to the queries of type Encrypt
0
(ek,m,ψ) such that the predicate
R
Encrypt
is satisfied with probability at least σ. On the other hand note
that the predicate necessarily fails with overwhelming probability for queries
of type Encrypt
s
(ek,m,ψ). This suggests that the tracer can progressively
randomize the pattern of the ciphertext until a position is identified that
the pirate-box fails to decrypt successfully whenever it queries the tracing
ciphertext. In other words we can locate a subset that intersects with the
traitor coalition in this fashion.
The soundness of the above argumentation is supported by the following
lemma (which is similar to Lemma
3.17
):
Lemma 4.4. Let ψ = {S
j
1
,...,S
j
s
}. Assuming that C ∩ S
j
v
= ∅, any prob-
abilistic polynomial-time adversary A, given {sk
u
}
u∈C
, distinguishes the dis-
tributions Encrypt
v−1
(ek,m,ψ) and Encrypt
v
(ek,m,ψ) with probability at
most 2ε
p
where (ek,sk
1
,...,sk
n
) ←KeyDist(1
n
) and the underlying encryp-
tion scheme (
E
,
D
) is ε
p
-insecure in the sense of Definition
2.5
.
Proof. Consider the following CCA1 key encapsulation adversary B that will
be able to break the symmetric encryption scheme (
E
,
D
) in the sense of Defi-
nition
2.5
with probability at least ε
p
by simulating the adversary A.
To break the security claim of the underlying symmetric encryption scheme
(
E
,
D
), B, is given access to encryption-decryption oracle of the primitive. B has
also access to the decryption/encryption under a key k that is unknown to her.
She is then challenged with a plaintext-ciphertext pair (c,m) for which either
c =
E
k
(m) or c =
E
k
(R) for some random string R that has the same length
with m. She is asked to decide if the pair is a correct plaintext-ciphertext pair.
B will simulate the distribution Encrypt
v
(ek,m,ψ) in a suitable way. Let
B be given the challenge (c,m) where either m is the proper plaintext of c or
it is randomly selected. B will prepare a ciphertext for A by setting the v-th
location of the challenge ciphertext with c and the remaining positions from
v + 1,...,s with encryptions of m.
Based on the assumption on the underlying encryption scheme we have
that |Prob[Exp
kem
B
(1
n
)]−1/2|≤ ε
p
. We observe that in the key encapsulation
