Trace and Revoke Schemes - Encryption for Digital Content - page 158

attack of B in the conditional space b = 0, the adversary B kem (1 n ) operates
identically to the distribution Encrypt v−1 (ek,m,ψ) while in the conditional
space b = 1 it operates identically to the distribution Encrypt v (ek,m,ψ).
Based on this we easily derive the proof of the statement of the lemma.

Let us denote by p v the probability that the decoder box decodes the spe-
cial tracing ciphertext Encrypt v (ek,m,ψ). Suppose, now, that the key k j v is
not available to the adversary. As we show in Lemma 4.4 it holds that the pi-
rate decoder distinguishs between the random variables Encrypt v−1 (ek,m,ψ)
and Encrypt v (ek,m,ψ) only with small probability that is related to the in-
security of the underlying encryption scheme E . As a result, it holds that
|p s−1 −p s | is relatively small assuming that the advantage ε p of breaking the
security of the underlying encryption primitive is also small.
On the other hand, for a pirate decoder we postulate that it holds that
p 0 ≥ σ due to the constraint placed on A as detailed in the revocation game.
It is relatively straightforward to see that p s ≤ 1

|M| (recall that M denotes
the plaintext space and we assume a random plaintext distribution). Hence
there must be at least one 0 < v ≤ s for which |p v−1 − p v | ≥ σ−1/|M|

s by
the triangular inequality. Similar to the traceability of linear length scheme of
Chapter 3 , we now can find such index v under some specific conditions that
we will see later.
Recall that the output of the revocation game RG B ψ = hKeyGen,Q Encryp ψ ,
R Encrypt i needs to be a revocation instruction ψ 0 that satisfies the conditions
given in Definition 4.1 for some revocation-suitable relation over Ψ = 2 [n] ×
L. Jumping ahead, an algorithmic description of the tracer can be found in
Figure 4.2 . In this description we have a step (line 4) that approximates the
pirate box decoding capability: this abstracts the standard statistical test of
querrying the decoder with the tracing ciphertexts many times by resetting
the pirate decoder to locate the subset containing a traitor. The procedure
uses the threshold parameter σ as determined by the σ-admissibility property.
The Lemma 4.4 ensures that the set S of line 7 in figure 4.2 contains
a traitor. The revocation algorithm then splits this subset and updates the
revocation instruction to include the split-pair while removing the original
subset from the broadcast pattern. The resulting pattern produced by this
process should be better with respect to a revocation-suitable relation defined
over the key poset Ψ = 2 [n] ×L which we will define accordingly.
Here, it should be noted that the e ciency of the tracing algorithm given in
Figure 4.1 depends on how the function spt(·) operates on a subset. Relatively
evenly balanced splits will result to a better convergence.
We return now to introduce a revocation-suitable relation SC (SC stands
for Subset Cover as the following relation is very specific to subset cover
schemes with bifurcation property) over Ψ = 2 [n] ×L. We have Ψ = 2 [n] ×L
with the set of revocation instructions L sampled from KeyGen(1 n ) based
on a set system Φ that fits the template of Figure 2.2 . Specifically, consider
two elements of the set Ψ, i.e. (C,ψ) and (C 0 ,ψ 0 ). We define ψ[u] as the