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.