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

Revocation(pattern ψ, pirate box B, σ)
1. Let ψ = {S j 1 ,S j 2 ,...,S j s }
2. if Prob[B(Encrypt(ek,m,ψ)) = m] < σ then return ∅
3. else
4. for i = 0 to s approximate
5. p i ≈ Prob[B(Encrypt i (ek,m,ψ)) = m]
6. for i = 1 to s
7. if |p i−1 −p i |≥ σ−1/|M|
s

then set S = S j i and break

8. ψ 0 = ψ\S
9.

If |S| > 1 then (S 1 ,S 2 ) = Φ.spt(S)

ψ 0 = ψ 0 ∪{S 1 ,S 2 }

10.

return ψ 0 11.

Fig. 4.2. The algorithmic description of the tracer (cf. Theorem 4.8 ) that makes
the revocation game for subset cover schemes winnable.

element in the broadcast pattern ψ that contains u, i.e. ψ[u] ∈ ψ such that
u ∈ ψ[u]; if such element does not exist then we say ψ[u] = ∅. We now define
(C,ψ) SC (C 0 ,ψ 0 ) if and only if the following hold: (i) C = C 0 , (ii) for all
u ∈ C we have ψ 0 [u] ⊆ ψ[u].
We next show that the relation is revocation-suitable.
Lemma 4.5. The relation SC over Ψ = 2 [n] × L, as defined above, is
revocation-suitable.

Proof. Suppose that SC does not satisfy property (i) of revocation-suitable
relation, i.e., there is a C corresponding to a set of corrupted users and a ψ
so that (C,ψ) is a maximal element of the relation SC but ψ encodes some
subset R for which it holds that C 6⊆ R, i.e., there is a u ∈ C \ R. Observe
that this also implies that ψ[u] 6= ∅. Now consider the pair (C,ψ 0 ) where ψ 0
is defined in the same way as ψ, but it holds that the element ψ[u] of ψ is
substituted in ψ 0 with a sequence of elements that covers ψ[u] \{u} (and as
a result ψ 0 [u] = ∅). The existence of this sequence is based on the exclusive
property of the underlying family Φ. It is easy to see that (C,ψ) SC (C,ψ 0 )
thus contradicting the maximality of (C,ψ). Properties (ii), (iii) are easy to
follow from the definition of the relation and the fact that Φ is a finite set
system.
We will, now, prove formally that a broadcast encryption scheme based
on any exclusive set system is a trace and revoke schemes with respect to the
relation SC .
Theorem 4.6. Let BE be a broadcast encryption scheme based on an (n,r,s)-
exclusive set system Φ that fits the template of Figure 2.2 . BE is a trace
and revoke scheme for n-coalitions with probability 1 − ε against resettable
σ-adversaries with σ > 4nε p + 1

|M| .
Furthermore it holds that rvover[ BE ,T SC ] ≤ O( s 3 ·ln(1/ε)

(σ−1/|M|) 2 ).