Pirate Evolution - Encryption for Digital Content - page 174

The ciphertext c distributed according to Encrypt(ek,m,ψ) contains the
encryption of message m with the key L j u , if it holds that u ∈ [n] \R where
ψ encodes a revocation instruction that excludes the set R. Observe that this
scheme is equivalent to the linear length multi-user encryption scheme we
discussed in the previous chapter. Since the set system Φ L is fully exclusive
and BE Φ L

basic matches the template of Figure 2.2 , Theorem 4.8 suggests that
the “linear length” scheme is a trace and revoke scheme. We next show that
it also possesses immunity to pirate evolution.

Theorem 5.3. The broadcast encryption scheme BE Φ L

basic is immune to pi-
rate evolution, i.e. for all polynomial-time adversaries P and for any key
leaking incident Leaking, the GenDisable algorithm of figure 4.1 satisfies
PE R,GenDisable
P,Leaking

(t) ≤ t.

Proof of Theorem 5.3 : We fix a certain n ∈ N and we will prove the claim
by induction on the number of traitors, t.
Let the scheme BE Φ L

basic = (KeyGen,Encrypt,Decrypt) be the broad-
cast encryption scheme that matches the template of Figure 2.2 where
Φ L = {S j u } u∈[n] is generated by KeyGen as well as {k j u } are selected ran-
domly and independently.
(i) Base case t = 1: This case states that the linear length trace and revoke
scheme is secure against any polynomial pirate evolution attackP with respect
to any key leaking incident Leaking provided that the number of traitors is
1, i.e. t = 1. Let v ∈ [n] \R be the traitor index.
First, observe that the ψ that encodes a set R to be revoked contains the
subset S j u = {u} for any u ∈ [n] \ R. Let the MasterBox constructed by
P produce a pirate decoder B 1 . Since the only key available to the pirate
is k j v , the broadcast pattern disabling B 1 , i.e. GenDisable(ψ,B 1 ,σ), does
not contain S j v . That is equivalent to saying GenDisable(ψ,B 1 ,σ) encodes
the set R ∪{v} to be revoked given the fact that no legitimate user is hurt
after tracing. That concludes PE R,GenDisable

P,Leaking (1) = 1 since the security of the
broadcast encryption scheme requires the traitor with index v not to recover
the message unless the broadcast pattern contains S j v .
(ii) Induction hypothesis: The linear length trace and revoke scheme
is secure against pirate evolution attacks for all polynomial adversary P
and for any key leaking incident Leaking provided that |T| = t − 1. i.e.
PE R,GenDisable

P,Leaking (t−1) = t−1.
(iii) Induction step: Let the number of traitors be t. First, observe that
the ψ that encodes the set R to be revoked contains the subset S j u for any
u ∈ [n] \R. Suppose the master box MasterBox constructed by P initially
produces a pirate decoder B 1 . We next compare the broadcast patterns ψ and
ψ 0 = GenDisable(ψ,B 1 ,σ).
The disabling process should not harm any uncorrupted user decrypting
the ciphertext, i.e. for any user j u ∈ [n] \ (R ∪ T) the subset S j u is among
the enabled users in both revocation instructions ψ,ψ 0 . Now given that all