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

adversarial decoder is not capable of decrypting while any other legitimate
receiver is not revoked.

Disabling in Parallel

We denote the successive applications of any Disable algorithm to a sequence
B 1 ,...,B v of pirate decoders by Disable(ψ,hB 1 ,...,B v i,σ). This notation
implies the following: we first start with invocation of Disable(ψ,B 1 ,σ) that
returns ψ 1 and continue with ψ i+1 = Disable(ψ i ,B i+1 ,σ) for i ≥ 1. After
invoking the process for each decoder once, we continue in a circular fashion
from the beginning, as it might be the case that the decoder B 1 becomes
active for the revocation instruction ψ v . The algorithm Disable terminates
after observing no change for v invocations of the Disable algorithm.

Pattern Optimization

The structural properties of the set system may allow operating on ψ to
improve its performance as a revocation instruction. This step if available
would replace line 5 of Figure 4.1 . In particular there will be an operation
ψ = Compact(ψ,aux) where Compact is the optimization operation and
aux is some auxiliary information extracted from the tracing operation (in
case such extra information is useful for optimization). While there is not a
generic technique to perform optimization, techniques for specific schemes will
be discussed later in the chapter.
We note that one has to be careful with the exit condition of the Disable
algorithm when using an optimization as depending on the setting it may be
the case that the algorithm Compact affects the success rate of the adver-
sarial decoders.

4.2 Tracing and Revoking in the Subset Cover
Framework

We will now show that the broadcast encryption scheme BE = hKeyGen,
Encrypt,Decrypti based on a subset cover set system Φ that fits the tem-
plate of Figure 2.2 is a trace and revoke scheme against resettable pirate
decoders. As we do not put any constraint on the type of queries the tracer is
allowed, we may consider the whole operation in the black-box setting. Recall
that resettable pirate decoders allow the tracer to reset the adversary and to
receive fresh responses that are oblivious to the history of the tracer-adversary
interaction. This is a key fact in our choice of tracing queries; in particular we
will deviate from the normal set of random variables Q Encryp ψ and query the
decoder with some special tracing ciphertexts as we have done in Chapter 3
for traitor tracing. However, this time the output of a similar interaction will
be a subset in the revocation instruction ψ that contains a traitor involved in
piracy.