Cryptography Reference
In-Depth Information
Fig. 5.2. Complete subtree method example with set cover and a set of traitors.
Lemma 5.5. Consider an adversary using the pirate box CSBox
j
. Suppose
S
j
= S
j
l
∪S
j
r
where the node j
l
(resp. j
r
) is left (resp. right) child of the node
with index j. If S
j
∈ ψ then it holds that S
j
l
∈Revocation(ψ,CSBox
j
,σ) and
S
j
r
∈Revocation(ψ,CSBox
j
,σ) for any 0 < σ ≤ 1.
contains the encryption of the message by using the key associated to S
j
. The
pirate box B = CSBox(j) then, by definition, decrypts Encrypt(ek,·,ψ) with
probability meeting the threshold σ. The revocation procedure in Figure
4.2
against the box B will identify the subset S
j
as the subset containing the
traitor. The tracing algorithm will partition S
j
into two equally-sized subsets
S
j
l
and S
j
r
as it is the case that the split algorithm spt(S
j
) of the Complete
Subtree returns the children of the node corresponding to the encoding j.
The pirate box B will not be able to decrypt with the given partition
ψ
0
= (ψ\{S
j
})∪{S
j
l
,S
j
r
}. As a result the outcome of the winnable revocation
game will be ψ
0
as the broadcast pattern against the pirate decoder B, i.e.
Revocation(ψ,CSBox
j
,σ) = ψ
0
.
Consider an adversary who has access to the key material sk
u
for which
u ∈ S
j
holds. Suppose that this adversary constructs the pirate decoder CSBox
j
and uses for illegal reception of the tranmissions. The adversary will be able
to produce a new version of pirate box even though the pirate decoder CSBox
j
is caught and disabled by the tracer. That is true due to the above lemma
because the revocation instruction ψ
0
that disables the decoder CSBox
j
still
includes a subset that contains the traitor. Indeed, the traitor with index u
is either in S
j
l
or S
j
r
, and the pirate still will be able to produce a new box
by using the key associated to S
j
l
( or S
j
r
depends on which one contains u).
The evolving pirate will be exploiting the above observation to successively
generate pirate boxes.
We define the master pirate box MasterBox produced by the adversary
P
Encrypt
(T,{sk
u
}
u∈T
) as producing a vector of pirate boxes. MasterBox
constructs the sequence of pirate boxes by walking on the nodes of the forest
