Cryptography Reference
In-Depth Information
1. For each set(v
x
,v
y
) ∈ ψ
2. Compute f = annotation(Steiner(T,v
x
,v
y
))
3. Run makeboxes(Steiner(T,v
x
,v
y
), f) till the `-th pirate box is produced (fail if
there is no `-th box).
makeboxes( Tree Tree, annotation f)
1. Let ⊥-path in Tree be hk
1
,k
2
,···k
m
i. Note that k
1
= v
x
and k
m
= v
y
2. Choose the shortest path hanging off the ⊥-path,
i.e. pick l = max(l : sibling(k
l
) ∈ Tree).
if no such path exists, exit.
3. Set u = f(sibling(k
l
));
4. Denote u-path by hu
1
,u
2
,···u
s
i
5. Output SDBox(k
1
,k
m
,u),SDBox(k
2
,k
m
,u),···SDBox(k
l−1
,k
m
,u)
6. Output SDBox(k
l−1
,k
l
,u) iff l < m.
7. Output SDBox(u
1
, sibling(u
2
),u),SDBox(u
2
, sibling(u
3
),u),...,
SDBox(u
s−1
, sibling(u
s
),u)
8. Update f(u
i
) =⊥, for 0 < i ≤ s
9. makeboxes(Steiner(T,u
1
,u
s
), f)
10. makeboxes(Steiner(T,k
1
,k
l−1
), f)
Fig. 5.11. The description of master box program MasterBox(1
t+log n
,`) parame-
terized by ψ,T, sk
u
for u ∈ T that is produced by the evolving pirate for the subset
difference method.
boxes are traced. We also show the maximum number of pirate decoders that
can be created.
Theorem 5.15. Let B
1
,B
2
,···,B
k+1
be a sequence of pirate boxes constructed
by the pirate evolution strategy described in Figure
5.11
parameterized by ψ
and T. Let 0 < σ ≤ 1. Suppose ψ
k
= SDDisable(ψ,hB
1
,B
2
,···,B
k
i,σ), then
it holds that
Prob[B
k+1
(Encrypt(ek,m,ψ
k
)) = m] ≥ σ
provided that
0
1
X
X
@
A
height(top
f
(u
0
)) + A
u
k <
(5.1)
users(v,v
0
)∈ψ
u∈T∩users(v,v
0
)
where f is the traitor annotation described in Figure
5.9
and u
0
depends on
u as follows u
0
is the traitor (possibly ⊥) such that the u-path(Steiner(T,v,v
0
))
hangs off the u
0
-path.
on input T and ψ produces as many boxes as the number given in the equa-
the algorithm produces for this subset.
