Cryptography Reference
In-Depth Information
SD
method are represented by pairs of nodes. We, first, recall the structural
definitions for the Subset Difference Method.
The receiver population corresponds to the set [n] and can be thought to
be placed on the leaves of a full binary tree. We define an index for each node
in the binary tree in a top-down manner similar indexing as in the Complete
Subtree method: the root of the binary tree is encoded by (the empty string),
an index of a left child is constructed by appending '0' to its parent's index
while an index of a right child is constructed by appending '1' to its parent's
index. An encoding j ∈J
SD
is a pair of strings (x,z) where the concatenated
string xz has a length at most log n with the length of z is at least 1. Denoting
the node corresponding to the string y by v
y
for any y ∈ {0,1}
i
such that
0 ≤ i ≤ log n, we let S
j
to be the set of users/leaves in the subtree rooted at
v
x
but not of v
xz
where j = (x,z).
We next define the function
users : {(v
x
,v
y
) | x,y ∈{0,1}
∗
s.t. |x|,|y|≤ log n}→ 2
[n]
such that users(v
x
,v
y
) = S
(x,z)
if there exists a string z that satisfies y = xz
and |z|≥ 1 otherwise users(v
x
,v
y
) returns emptyset. Observe that the inverse
function users
−1
(S
j
), for j ∈J
SD
, returns the pair of nodes encoded by j. Since
S
j
is somehow related to a tree, we still use root(S
j
) to output v
x
provided
that j = (x,z). We finally, enhance the definition of Steiner tree as follows: we
say the Steiner tree Steiner(T,v
x
,v
y
) is the minimal subtree of the binary tree
rooted at v
x
, excluding the descendants of v
y
, that connects all the leaves in
T∩users(v
x
,v
y
) as well as node v
y
.
figure, we picture the set of revoked users R (the black leaves) and the set
of traitors T = {T
1
,T
2
,T
3
,T
4
} (the squared leaves). The pair of nodes, con-
nected with an edge, correspond to the subsets in the broadcast pattern that
is resulted by Steiner(R, [n]), which equals to Revoke(Φ
SD
,R) where the al-
gorithm Revoke of the set system Φ
SD
outputs the revocation instruction
that encodes the set R.
Fig. 5.6. Subset difference method example with set cover and a set of traitors.
