Cryptography Reference
In-Depth Information
Consider the first traitor u that belongs to T∩users(v,v
0
) and is selected
in line 3 of Figure
5.11
. We have that the number of boxes produced will equal
to l−1 + s−1 + A
u
, where l−1 is the number of nodes in the ⊥-path from
v to the junction for the u-path and s is the number of nodes in the u-path.
It is immediate that the height of the node u
0
as defined in the theorem's
statement based on u will be exactly l + s − 2; it follows that the number
of boxes contributed by traitor u will be height(top
f
(u
0
)) + A
u
. Based on the
way the makeboxes procedure works, the same exact argumentation applies
to theremaining traitors in T∩users(v,v
0
).
This completes the argument on the number of boxes the MasterBox
of Figure
5.11
produces. We denote this number by K. We next prove by
induction on k that if Equation
5.1
holds, i.e. k < K, then we obtain:
Prob[B
k+1
(Encrypt(ek,m,ψ
k
)) = m] ≥ σ
where B
i
← MasterBox(1
t+log n
,i) and ψ
k
is the revocation instruction
produced by SDDisable(ψ,hB
1
,B
2
,···,B
k
,σ).
(i) Base case with k = 0: as there is no pirate box other than B
1
we have
ψ
0
= ψ. Denote the first box produced by makeboxes(Steiner(T,v,v
0
),f) as
B
1
where (v,v
0
) is a pair of nodes such that users(v,v
0
) ∈ ψ. Since the ⊥-path
of the Steiner tree starts with v and ends with v
0
, the box will be of the form
SDBox(v,v
0
,u) for the traitor u whose traitor path is the shortest path hanging
off the ⊥-path. It is immediate that Prob[B
1
(Encrypt(ek,m,ψ
0
)) = m] ≥ σ.
(ii) Induction assumption for some 0 ≤ k < K −1: We assume that
Prob[B
k
(Encrypt(ek,m,ψ
k−1
)) = m] ≥ σ
holds for ψ
k−1
= SDDisable(ψ,hB
1
,B
2
,···,B
k−1
,σ).
(iii) Induction step: We have two cases; either the pirate decoders B
k
and
B
k+1
are generated subsequently in the same batch of a call of makeboxes
on some Tree, or B
k+1
is the first output of a new call while B
k
is the last
output of a previous call to makeboxes.
The first case: Suppose that B
k
and B
k+1
are produced by the key of a
traitor u ∈ T whose traitor path is the shortest path hanging off the ⊥-path of
the Tree. Note that if the ⊥-path = hv
1
,...,v
m
i for some m, then Tree would
be of the form Steiner(T,v
1
,v
m
).
Let us suppose that B
k
= SDBox(x
1
,y
1
,u) and B
k+1
= SDBox(x
2
,y
2
,u)
for some nodes x
1
,y
1
,x
2
,y
2
. The induction assumption along with the defin-
ition of SDBox yield the fact that users(x
1
,y
1
) ∈ ψ
k−1
. Due to the evolution
strategy given in Figure
5.11
observe that the set users(x
2
,y
2
) is a subset of the
set users(x
1
,y
1
) and we have that users(x
2
,y
2
) ∈ SDDisable(ψ
k−1
,B
k
,σ).
Next we observe that ψ
k
= SDDisable(ψ,hB
1
,B
2
,···,B
k
,σ) is equal to
SDDisable(ψ
k−1
,B
k
,σ) due to the way we define the successive revocation
over a sequence of pirate decoders. Hence we obtain users(x
2
,y
2
) ∈ ψ
k
. Recall
that B
k+1
= SDBox(x
2
,y
2
,u), the definition of SDBox completes the final
argument:
