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

decrypt ciphertexts that are encrypted with revocation instructions encoded
from the set:

L T = {ψ ∈L| ψ encodes R s.t. T * R}

Revocation of the rogue decoders that follow the code of that adversary
amounts to finding an encoding from the language L of the broadcast encryp-
tion scheme for which all legitimate receivers can decode correctly, nevertheless
if the decoder is invoked on that ciphertext it is incapable of decrypting it.
Such an encoding can be determined easily if we are able to recover the whole
traitor coalition and include it in the set of revoked receivers. However, the
rogue decoder might be constructed in such a way that it does not reveal all
information about the traitor identities, i.e. the decoder might work only for
particular choices from the sublanguage L T . Therefore, it follows that without
making strong assumptions regarding the construction specifics of the rogue
decoder or restricting ourselves to specific broadcast schemes, one cannot rely
on identifying all traitors as the means to successful revocation.
This puts forth the basic question : if finding the identities of the traitors
is not the primary target of the tracer in the revocation game what else can it
be? We will formalize the goal of a tracer, that has input a revocation instruc-
tion, as the discovery of an improved revocation instruction that reveals more
information on the traitor coalition compared to the given instruction. This
means that the tracer may actually walk over all possible revocation instruc-
tions until a suitable one is discovered by playing a sequence of revocation
games successively.
This successive improvement approach calls for an ordering between the
encodings in L that is based on the traitor coalition. For now it su ces to
say that we have a partial order over the Cartesian product Ψ = 2 [n] ×L.
Given such partial order the goal of the tracer would be to improve with
respect to the ordering. We are now ready to formalize the notion of winning
a revocation game.

Definition 4.1. For a broadcast encryption scheme BE = hKeyGen,Encrypt,
Decrypti, for n ∈ N and ψ ∈ L we say that the revocation game RG B ψ =
hKeyGen,Q Encryp ψ ,R Encrypt i is winnable by a tracer T for t-coalitions with
respect to (Ψ,) with probability α for σ-adversaries if for all A that make
the pair hA,Ti σ-admissible the following holds. For any C ⊆ [n], |C|≤ t and
(ek,sk 1 ,...,sk n ) distributed according to KeyGen(1 n ),
• The output of the game ψ 0 6= ψ, that is distributed according to hA,Ti(ek,
sk 1 ,...,sk n ,C), satisfies (C,ψ) (C,ψ 0 ) with probability at least α.
• Suppose c = Encrypt(ek,m,ψ 0 ) for some m ∈M. For all u ∈ [n]\(R∪C)
it holds that Decrypt(sk u ,c) = m where R ⊆ [n] is the revocation subset
that is encoded by ψ.

Provided that RG B ψ is winnable by a tracer T , we define the revocation
overhead rvover[ RG B ψ ,T ] of the revocation game RG B ψ

as the supremum of all