Cryptography Reference
In-Depth Information
Fig. 5.10. The user paths due to the annotation given in Figure
5.9
.
Lemma 5.14. Consider the revocation instruction ψ = Revoke(Φ
SD
,R) that
encodes the set R where Revoke is the algorithm described in Figure
2.9
.
Let Tree = Steiner(T,v
x
,v
y
) ∈ {Steiner(T,g,r) | users(g,r) ∈ ψ} be one of
the Steiner trees for a traitor coalition T. Consider the annotation f of Tree
given in Figure
5.9
. Suppose the shortest path hanging off the ⊥-path(Tree)
is annotated by u. Let u
1
= top
f
(u) and u
s
= bottom
f
(u) where s is the
length of the u-path(Tree). It holds that: (1) There exists a sequence of pi-
rate boxes B
1
,B
2
,···B
h
, each using a private key derived from sk
u
where
h = height(Tree) + A
u
and A
u
∈ {0,1} such that A
u
= 1 if and only if
sibling(u
1
) has a single child in Tree. (2) SDDisable(ψ,hB
1
,B
2
,···B
h
i,σ) =
(ψ \ users(v
x
,v
y
)) ∪ {users(v
x
,parent(u
1
)),users(u
1
,u
s
)} ∪ L
u
, where L
u
=
{users(sibling(u
1
),v
y
)} if A
u
= 1 and ∅ otherwise.
path hk
1
,k
2
,···k
m
i. Note that k
1
= v
x
and k
m
= v
y
. The shortest path
hanging off the ⊥-path is related to the maximum l such that sibling(k
l
) is a
node in Tree, i.e. l = max(l : sibling(k
l
) ∈ Tree). Provided that this shortest
path is annotated by u, denote the u-path by hu
1
,u
2
,···u
s
i. In light of the
facts that k
l
and u
1
are siblings in the Tree, and u
s
is a leaf, the length (in
number of nodes) of the path from v
x
to u
s
equals to height(Tree) + 1. It
follows that, l− 1 + s = height(Tree) + 1. Observe that A
u
as defined in the
statement of Lemma
5.14
, satisfies that A
u
= 0 if l = m and A
u
= 1 if l < m.
We define the sequence of pirate boxes B
1
,B
2
,···B
h
as follows:
8
<
9
=
SDBox(k
y
, k
m
, u) 0 < y < l
SDBox(k
l−1
, k
l
, u) (y = l) ∧ (A
u
= 1)
SDBox(u
j
, sibling(u
j+1
), u) y = l + A
u
+ j −1 for 0 < j ≤ s−1
B
y
=
:
;
Observe that h = height(Tree) + A
u
holds. We next prove the correctness,
i.e. the next generation should be able to decrypt the message encrypted after
tracing has disabled all previous boxes.
For simplicity, for a given B = SDBox(g,r,u) for a pair of nodes g,r,
let us define users(B) as the set users(g,r). Recall that users(k
1
,k
m
) ∈ ψ,
