Cryptography Reference
In-Depth Information
After the introduction of Subset Cover Framework by Naor, Naor and
Lotspiech in [
87
], this combinatorial framework gave rise to a diverse number
of fully-exclusive set systems: Complete Subtree and Subset Difference [
87
],
the Layered Subset Difference [
53
], the Key Chain Tree [
122
], the Stratified
Subset Difference [
50
], the Subset Incremental Chain [
6
] and the class of set
systems of [
55
] as well as that of [
56
,
57
].
The Key Chain Tree [
122
], the Stratified Subset Difference [
50
] and the
Subset Incremental Chain [
6
] are all employing the same set system with
slight differences in their key-handling procedures. Those differences result in
different e
ciency parameters but still they utilize the exact same key-poset.
It is quite easy to observe that [
6
] and [
122
] have the same key-poset whereas
it is more involved to see the isomorphism of the set system Stratified Subset
Difference ([
50
]) to the former two without explicitly thinking of the key-poset
of [
50
]. We refer the reader to [
105
] for more information on partial ordered
sets.
As a short diversion within this short set of bibliographic notes, we will
show that, indeed, the key-poset of the Stratified Subset Difference is isomor-
phic to the key-poset of Key Chain Tree. In a nutshell, the set system Φ
SSD
of [
50
] consists of subsets that are formed as follows. Consider a subset of a
SD method, and denoted by S
j
where j = (v
i
,v
k
) is a pair of nodes in the
binary tree that has leaves the set of users. The set S
j
∈ Φ
SSD
is defined as
the set of nodes rooted at v
i
and located on the left of the nodes rooted at
v
k
. The set S
j
∈ Φ
SSD
is defined as the set of nodes rooted at v
i
and located
on the right of the nodes rooted at v
k
. Observe that both subsets S
j
and S
j
consist of continuous nodes at the leaf level in the subtree rooted at node v
i
.
Theorem 2.59. The key poset of Stratified Subset Difference is equal to the
key poset stemming from the schemes of [
6
,
122
] that is depicted in figure
2.16
.
Proof. of Theorem
2.59
It is quite obvious that any subset described in the
stratified subset difference exists in the set system of Key Chain Tree. We
will, now, complete the proof by showing that for any subset S
j
k
∈ Φ
KCT
there
exists some S
j
s
∈ Φ
SSD
that satisfies S
j
k
= S
j
s
:
We have two cases for the location of leaves in S
j
k
= {u
1
,...,u
t
}:
(i) S
j
k
is set of consecutive leaves rooted at a minimal node v
1
so that u
1
is the leftmost leaf of v
1
. Denote the least common ancestor of u
t
and u
∗
by
v
2
where u
∗
comes after the leaf u
t
in the left-to-right ordering of the leaves.
Consider the right child of v
2
and name it by v
3
. Observe now that the subset
S
j
s
for j
s
= (v
1
,v
3
) contains all leaves rooted at v
1
and located on the left of
the nodes rooted at v
3
.
(ii) S
j
k
is set of consecutive leaves rooted at a minimal node v
1
so that u
t
is the rightmost leaf of v
1
. Denote the least common ancestor of u
1
and u
∗
by v
2
where u
∗
comes before the leaf u
1
in the right-to-left ordering of the
leaves. Consider the left child of v
2
and name it by v
3
. Observe now that the
subset S
j
s
for j
s
= (v
1
,v
3
) contains all leaves rooted at v
1
and located on the
right of the nodes rooted at v
3
.
