Cryptography Reference
In-Depth Information
To understand the way merging can be applied in the context of the subset
difference method consider the following simple lemma.
Lemma 5.12. Let v
x
,v
c
1
,v
c
2
,···v
c
d
,v
y
be any sequence of vertices which oc-
cur in this order along some root-to-leaf path in the tree corresponding to the
subset users(v
x
,v
y
). Then users(v
x
,v
y
) = users(v
x
,v
c
1
)∪users(v
c
1
,v
c
2
)∪···∪
users(v
c
1
,v
y
).
users(v,z) is defined as a set difference B \ C for some sets of leaves that
satisfy C ⊆ B ⊆ A. The sets are clearly disjoint, and their union is A \ C
which is the definition of users(u,z). Using that simple observation, one could
say users(v
x
,v
y
) = A \ B, users(v
x
,v
c
1
) = A \ A
1
, users(v
c
k
,v
c
k+1
) = A
k
\
A
k+1
, for 0 < k < d, and users(v
c
d
,v
y
) = A
d
\ B such that B ⊆ A
d
⊆
A
d−1
⊆···⊆ A
1
⊆ A. Thus, the telescoping formula for set differences yields
the desired result.
Using the above, whenever the partition contains a series of subsets
{users(v
x
,v
1
),users(v
c
1
,v
c
2
),···,users(v
c
d
,v
y
)} they can potentially be merged
using Lemma
5.12
into one single subset users(v
x
,v
y
). We denote the disabling
algorithm, that employs a compaction algorithm to merge subsets if possible
on top of GenDisable, by SDDisable. Some care is needed : in general,
merging will occur whenever it is allowed based on lemma
5.12
with the fol-
lowing exception: S
j
1
will not be merged if the partition contains another
subset S
j
2
such that they have resulted from a split of a single subset at
an earlier iteration of the Revocation procedure (without this restriction
the Revocation procedure may enter an infinite loop). More explicitly we
SDDisable(pattern ψ, pirate box B, σ)
1.
repeat
2.
if Prob[B(Encrypt(ek,m,ψ)) = m] < σ then break
ψ
0
= Revocation(ψ,B,σ)
3.
Construct new ψ by merging all subsets of ψ
0
4.
that belong to ψ∩ψ
0
using lemma
5.12
.
5.
6.
until break
7.
output ψ
/* ψ is a pattern that disables B */
Fig. 5.7. The algorithm that disables a pirate decoder applying the improvement
of lemma
5.12
to the GenDisable algorithm of figure
4.1
.
We now present an evolving pirate strategy based on the forest of Steiner
trees {Steiner(T,v
x
,v
y
) | users(v
x
,v
y
) ∈ ψ} by walking on the paths of Steiner
trees that will be predefined according to a scheduling of traitors. Unlike our
evolving pirate strategy for the GenDisable algorithm, we are focusing on
