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

to the revocation instruction that disables the rogue decoder (which cannot
reach the required threshold σ).
This suggests that the revocation game should be defined on suitable
posets over Ψ = 2 [n] ×L. In particular we would be interested in partial
orders for which any maximal element (C,ψ) in the poset satisfies that ψ
encodes an instruction that revokes a set R that satisfies C ⊆ R. In such a
case, when a topmost (C,ψ) is reached, it is easy to see that the adversary
A, given the key materials of the corrupted parties {sk u } u∈C , can recognize
whether the pair (m,c) is a valid plaintext-ciphertext pair, where c is distrib-
uted according to Encrypt(ek,·,ψ), with probability less than ε where the
broadcast encryption scheme BE is ε-insecure in the sense of Definition 2.2 .
We next define the condition imposed on as follows:

Definition 4.2. A partial order relation over Ψ = 2 [n] ×L, where L is a lan-
guage encoding subsets from 2 [n] , is revocation-suitable, if (i) for any C ∈ 2 [n]
and for any ψ ∈L, (C,ψ) is a maximal element in implies that ψ encodes
some subset R such that C ⊆ R, (ii) elements of the form (C,ψ), (C 0 ,ψ 0 ) for
C 6= C 0 are incomparable, and (iii) all chains in are finite.

Based on this notion we define next a trace and revoke scheme in a generic
way and discuss two variants of the definition afterwards:

Definition 4.3. We say a broadcast encryption scheme BE = (KeyGen,
Encrypt,Decrypt) for t-coalitions is a trace and revoke scheme with prob-
ability α for σ-adversaries if there exists a tracer T and a revocation-suitable
relation over Ψ = 2 [n] ×L for which the following holds:
For any number of users n ∈ N and revocation instruction ψ ∈ L, the
revocation game RG B ψ = hKeyGen,Q Encryp ψ ,R Encrypt i for t coalitions is
winnable by T with respect to (Ψ,) with probability α against σ-adversaries.
We define the revocation overhead rvover[ BE ,T ] of the broadcast encryption
as the supremum of all rvover[ RG B ψ ,T ].

We will now discuss how to use a trace and revoke scheme BE = (KeyGen,
Encrypt,Decrypt) as defined above to disable an actual decryption algo-
rithm represented by the adversary. An adversary, corrupting a set of traitors
T ⊆ [n], constructs a decryption algorithm using the key materials of the
traitors. More specifically, a pirate decryption algorithm B is any polynomial-
time bounded algorithm that receives as input a ciphertext and is successful
at decrypting it for at least some broadcast pattern ψ ∈ L T , i.e. B satis-
fies Prob[B(Encrypt(ek,m,ψ)) = m] ≥ σ where σ is a lower bound for
the success probability of decryption, i.e. the admissibility requirement of the
tracer-adversary pair (below that bound no decoder is deemed useful for the
application at hand; this parameter in practice would be depending on the
application domain). We associate to each decryption algorithm the collection
of patterns from L T that the decoder is decrypting with probability at least
σ. Note that the language L T has an e cient probabilistic membership test.