Cryptography Reference
In-Depth Information
The tracer will variate the parameter s ∈{0,1,...,q} effectively causing
a certain set of users to switch from decrypting plaintext m
0
to plaintext
m
1
depending on the set of keys that a user has in the column l that is
used for variating the plaintext. At this moment it should be noted that
for any single user of the system the ciphertexts that are produced during
tracing are computationally indistinguishable from ciphertexts transmitted
during normal system operation. This suggests that tracing in the Kiayias-
Yung scheme is alfresco.
After a su
cient number of queries, it will be feasible for the tracer to
deduce a key from each column. This will enable the tracer to construct the
pirate codeword that is consisting of the keys used by the adversary. Provided
that
F
is (ε
f
,t)-identifier, the Identify algorithm of the underlying finger-
printing code will output a traitor with a small error probability as long as
the traitor coalition is bounded by t.
We next prove the traceability of the construction.
Theorem 3.24. Consider the binary multiuser encryption scheme
ME
KY [
F
]
that employs a symmetric encryption scheme that is ε
p
-insecure in the sense
of Definition
2.5
and an (`,n,q) fingerprinting code
F
that is (ε
f
,t)-identifier.
Also consider a plaintext distribution over M
2
with limited crossover γ.
For any n ∈ N, > 0,
ME
KY [
F
]
is an alfresco black-box traitor trac-
ing scheme for t-coalitions with success probability 1 −ε−ε
f
against reset-
table σ-pirates with σ > 10qε
p
+ 2γ. It further holds that trover[
ME
BN[
F
]
] =
O(
`q
3
·log(`/ε)
(σ−2γ)
2
).
Proof. Consider an adversary A that is given access to the key material
{sk
u
}
u∈C
for some subset C ⊆ [n] where (tk,ek,sk
1
,...,sk
n
) is distributed
according to KeyDist
F
(1
n
).
The tracing party T
KY
interacts with A in the following fashion. T
KY
will submit queries to the adversary that are regular transmissions where
l ∈{1,...,`} and s ∈{0,1,...,q}. We consider each transmission q together
with the response of the adversary a to be an experiment that is successful
if it holds that the adversary's response is equal to the plaintext m
b
(i.e.,
the plaintext that is selected to be the only one transmitted in the case the
parameter s = 0). Each experiment type (l,s) will be repeated K times where
K is a parameter to be determined later.
Now we define p
s,l
the probability that the experiment at column l and
symbol location s is successful. In the sequence of experiments that the tracer
performs we then denote by ρ
s,l
as the number of times in {0,...,K} that
the experiment was successful.
Now observe that for any l ∈{1,...,`} it holds that p
0,l
≥ σ−γ since the
ciphertexts submitted by the tracer are identical to those in normal system
transmission, the adversary has to decrypt correctly with probability σ. Note
that the scheme is binary so the alternative plaintext can also be returned
but due to the limited crossover we have that the probability drop in the
