Cryptography Reference
In-Depth Information
only with small probability that is related to the insecurity of the underlying
On the other hand, the σ-admissibility of the tracer adversary pair im-
plies that a pirate decoder decrypts the ciphertext Transmit
CFN[
F
]
(ek,m) =
Transmit
0,j
CFN[
F
]
(ek,m) with probability at least σ for j = 1,...,`,
i.e.
1
p
0,j
≥ σ. On the other hand, p
q,j
can be at most
|M|
since the share m
j
is entirely replaced by a sequence of random values. Hence, by applying
the triangular inequality, there must be some w
j
∈ {1,...,q} such that
|p
w
j
−1,j
− p
w
j
,j
| >
σ−1/|M|
q
. Along similar lines to the analysis of the lin-
ear length multiuser encryption scheme, the tracer will be able to locate such
value with small failure probability for a slightly shorter probability differ-
ence. This same experiment will be run over each j = 1,...,` individually to
identify the traitor key for the j-th column that is manifested by the pirate
decoder.
Theorem 3.21. Consider the multiuser encryption scheme
ME
CFN[
F
]
that em-
ploys a symmetric encryption scheme that is ε
p
-insecure in the sense of Def-
inition
2.5
and an (`,n,q) fingerprinting code
F
that is (ε
f
,t)-identifier.
For any n ∈ N, > 0, the
ME
CFN[
F
]
is a black box traitor tracing scheme
for t-coalitions with success probability 1−ε−ε
f
against resettable σ-pirates
where σ > 10qε
p
+
1
|M|
. It further holds that trover[
ME
CFN[
F
]
] = O(
`q
3
·log(`/ε)
(σ−1/|M|)
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
).
tracer will interact with the adversary by submitting suitable queries. A
query of type (i,j), for i = 0,1,...,q and j = 1,...,`, would correspond
to Transmit
i,j
the adversary after each query. Each query q together with the response a of
the adversary is thought of as an experiment of type (i,j) that is successful
provided that : R
BB
(C,tk,ek,sk
1
,...,sk
n
,q,a) = 1.
Let p
i,j
be the success probability of the experiment of type (i,j). Each
experiment type will be repeated K times where K is a parameter that will
be determined below. We define ρ
i,j
∈{0,...,K} the number of successes of
all the experiments of type (i,j).
For each j = 1,...,`, the tracer finds the smallest s ∈ [q] that satisfies
|ρ
s−1,j
− ρ
s,j
| ≥
5
· K
σ−1/|M|
q
. Then, the tracer sets w
j
= s. The tracer
will fail if such s does not exist for some j. Finally, the tracer constructs
a codeword p = hw
1
,...,w
`
i. It then outputs Identify(tk,p) where
F
=
(CodeGen,Identify). Consider, now, the following arguments:
1. Using lemma
3.18
the choice K ≥
75q
2
·ln(8`/ε)
(σ−1/|M|)
2
su
ces to locate a value
w
j
∈{1,...,q}, for all j = 1,...,`, such that |p
w
j
−1,j
−p
w
j
,j
|≥
σ−1/|M|
5q
holds with probability 1−ε.
