Cryptography Reference
In-Depth Information
Fig. 5.4. Steiner Trees of the traitors and generation of pirate boxes (cf. figure 5.2 )
provided that v is less than the number of nodes in the forest of trees
{Steiner(T,S) | S ∈ ψ}.
Proof of Theorem 5.6 : Suppose that the pirate box B v+1 uses the key
associated to some node j, i.e. B v+1 = CSBox j holds. Due to the evolution
strategy of the pirate in Figure 5.3 such node exists iff v + 1 is less than or
equal to the number of nodes in the forest of trees {Steiner(T,S) | S ∈ ψ}.
If it exists, then there are two cases possible on node j: j is an encoding of
either (1) an internal node or leaf, or (2) a root of one of the trees in the forest
{Steiner(T,S) | S ∈ ψ}.
(1) Suppose j is an encoding of an internal node of Steiner(T,S) for
some S ∈ ψ. In this case, there exists a B i = CSBox j 0 ,i ≤ v such that
root(Steiner(T,S)) = root(S) = j 0 (this is obvious from the way that the
evolving pirate operates). Due to the evolution strategy of Figure 5.3 , we
can associate the box B k , for i ≤ k ≤ v + 1, with a subset S j 0 for which
root(S j 0 ) is an internal node in the Steiner tree Steiner(T,S j 0 ). Furthermore,
there exists a subsequence of pirate boxes B i = B i 0 ,B i 1 ,B i 2 ,···,B i s = B v+1
such that root(S j k ) is parent of root(S j k+1 ) where we have B i k = CSBox j k for
k = 0,1,...,s−1.
Since S j 0 ∈ ψ (S j 0 is one of the subsets forming a Steiner tree), we claim
that S j k ∈ GenDisable(ψ,hB i 0 ,B i 1 ,B i 2 ,···B i k−1 i,σ), for 1 ≤ k ≤ s (Claim
1).
Proof of Claim 1: We will prove by induction:
(i) Base case with k = 1: Recall that root(S j 1 ) is a child of root(S j 0 ) and
B i 0 = CSBox j 0 . First, the Lemma 5.5 implies that S j 1 ∈Revocation(ψ,B i 0 ,σ).
Observe also that the GenDisable invokes the Revocation algorithm only
once, hence we obtain S j 1 ∈GenDisable(ψ,B i 0 ,σ) which completes the proof
for base case.
(ii) Induction assumption: S j k ∈GenDisable(ψ,hB i ,B i 1 ,B i 2 ,···B i k−1 i,σ),
for 1 ≤ k < s.
 
Search WWH ::




Custom Search