Cryptography Reference
In-Depth Information
we claim that users(B
y
) ∈ SDDisable(ψ,hB
1
,B
2
,···B
y−1
i,σ) provided that
y ≤ height(Tree) +A
u
. This can be proven by induction by using the result of
Lemma
5.11
. The induction is similar to the induction made in the proof of
Theorem
5.6
. Note that the last box SDBox(u
s−1
, sibling(u
s
),u) decrypts the
ciphertext iff users(u
s−1
, sibling(u
s
)) = {u} is in the partition. Tracing against
all boxes would end up with revoking u entirely.
Regarding statement (2) of the lemma, we consider first the case l < m.
It is easy to see by induction that the following two claims hold :
Claim 1. Consider y = 2,...,l−1. Then it holds that the pattern SDDisable(ψ,
hB
1
,B
2
,···B
y
i,σ) contains the sets
users(k
1
,k
y
),users(k
y
,k
y+1
),users(k
y+1
,k
m
)
Claim 2. Consider j = 2,...,s − 1 and y = l + j. Then it holds that the
pattern SDDisable(ψ,hB
1
,B
2
,···B
y
i,σ) contains the sets
users(u
1
,u
j
),users(u
j
,u
j+1
),users(u
j
, sibling(u
j+1
))
Based on the above it is easy to see that ψ after the tracing process, it
will hold that users(v
x
,v
y
) would substituted by users(k
1
,k
l−1
),users(k
l
,k
m
)
and users(u
1
,u
s
).
The case of l < m can be argued in exactly the same way with the only
difference that there will be no “left-over” set users(k
l
,k
m
) in the pattern as
we have in the case l < m.
We next describe our evolving pirate strategy against the
SD
set sys-
tem. We define the master pirate box MasterBox produced by the adver-
sary P
Encrypt
(T,{sk
u
}
u∈T
) for a set of traitors T as follows: MasterBox
recursively runs a procedure for each subset users(v
x
,v
y
) ∈ ψ which is
called
makeboxes
, with input the traitor annotated Steiner tree Tree =
Steiner(T,v
x
,v
y
). Observe below that whenever the recursive call is made,
the annotation of Tree satisfies that the root is annotated with ⊥. The basic
procedure works as follows:
The root v
x
is annotated as ⊥. Let u-path(Tree) = hu
1
,u
2
,···u
s
i be the
shortest path hanging off the ⊥-path(Tree). The master box MasterBox con-
structs SDBox(v
x
,v
y
,u) and more pirate decoders following the way tracing
works as described in lemma
5.11
. After creating pirate boxes as many as the
height of Tree (plus one possibly if A
u
= 1, cf. lemma
5.14
), the traitor u will
be entirely revoked by the system. Lemma
5.14
tells us that the partition af-
ter revoking u will include the subsets users(v
x
,parent(u
1
)) and users(u
1
,u
s
).
We update the path hu
1
,u
2
,···u
s
i in Steiner(T,u
1
,u
s
) by annotating it by
⊥ since u is no more in users(u
1
,u
s
). The master box MasterBox then runs
makeboxes independently on both of the trees Steiner(T,v
x
,parent(u
1
)) and
evolving pirate strategy.
In the following theorem we prove the correctness of the strategy, i.e. that
each box will decrypt the ciphertexts that are generated assuming all previous
