Cryptography Reference
In-Depth Information
|µ
s−1
−µ
s
|≥|ρ
s−1
−ρ
s
|−2γ
with probability at least (1 −ε/4)
2
≥ 1 −ε/2. Given that we have γ =
K(p
0
−p
N
)
5N
we obtain that with probability at least 1−ε/2 it holds that:
|p
s−1
−p
s
|≥
p
0
−p
N
5N
This completes the proof of claim 1.
Claim 2. We next claim that there is an s ∈ {1,...,N} for which it holds
|ρ
s
−ρ
s−1
|≥
5
·K(p
0
−p
N
)/N with probability at least 1−ε/2.
Observe that there exists an s ∈{1,...,N} for which it holds |p
s
−p
s−1
|≥
(p
0
−p
N
)/N. Indeed otherwise for any s it holds |p
s
−p
s−1
| < (p
0
−p
N
)/N and
thus |p
0
−p
N
|≤
P
s=1
|p
s
−p
s−1
| < N|p
0
−p
N
|/N = |p
0
−p
N
|, a contradiction.
For this s we will show that |ρ
s
−ρ
s−1
|≥
5
·K(p
0
−p
N
)/N. We know that
|µ
s
−µ
s−1
|≥ K(p
0
−p
N
)/N. As before we know that with probability 1−ε/2
we will have |µ
s−1
−ρ
s−1
| ≤ γ and |µ
s
−ρ
s
| ≤ γ, as a result |ρ
s
−ρ
s−1
| ≥
|µ
s
−µ
s−1
|−2γ.
We conclude that with probability 1−ε/2 there exists some s ∈{1,...,N}
for which it holds |ρ
s
−ρ
s−1
|≥
5
·K(p
0
−p
N
)/N. This completes the proof
of claim 2.
By combining the two claims we obtain the statement of the lemma.
Following the above reasoning, we are, now, ready to prove that the
ME
L
is
a black-box traitor tracing scheme for which the corresponding tracing game
for n-coalitions is winnable by the tracer T
S
against any probabilistic poly-
nomial time adversarial algorithm A. As we have specified at the beginning
of this section, the tracer T
S
will queriy the special transmission of the form
Transmit
L
(ek,m) for s = 0,1,...,n where m is uniformly distributed.
Theorem 3.19. Consider a multiuser encryption scheme
ME
L
that employs a
symmetric encryption scheme that is ε
p
-insecure in the sense of Definition
2.5
.
For any n ∈ N, > 0, the scheme
ME
L
is a black box traitor tracing scheme
for n-coalitions with success probability 1−ε against resettable σ-pirates with
σ > 10nε
p
+
1
|M|
. It further holds that trover[
ME
L
] = O(
n
3
·ln(1/ε)
(σ−1/|M|)
2
).
Proof. Consider an adversary A that is given access to the key material
{sk
j
}
j∈C
for some subset C ⊆ [n] where (tk,ek,sk
1
,...,sk
n
) is distributed
according to KeyDist
L
(1
n
).
The tracer T
S
will interact with A by submitting suitable queries. A query
for i ∈{0,...,n}. The tracer will reset the adversary after each query. Each
query q of type i together with the response a of A can be thought as an
experiment of type i. The experiment is said to be successful if
R
BB
(C,tk,ek,sk
1
,...,sk
n
,q,a) = 1
