Cryptography Reference
In-Depth Information
Fig. 2.12. A graphical depiction of the subset difference key poset for 8 users.
where the concatenated string LR has a length at most log n. We refer reader
to the Figure
2.13
for the computational specification of Subset Difference in
the KP framework.
The key-forest for compression.
Consider the set of trees of the following form : let L ∈{0,1}
x
with 0 ≤ x ≤
log n − 1 and b ∈ {0,1}. We have that F
Lb
is a binary tree constructed as
follows: it includes as root the node that corresponds to the subset j where
j = (L,b). In addition, F
Lb
includes all the nodes that can be added recursively
following this rule : for any node j
0
in F
Lb
, the first child of j
0
is cvr(j
0
,2) and the
second child of j
0
is cvr(j
0
,3) (see Figure
2.13
for computational specification
of the Subset Difference). The subset encoded by that contains the whole
user population also forms a tree by itself as a single node that is denoted by
F
ε
. The family of trees is denoted by F
SD
.
Proposition 2.41. The set F
SD
= {F
s
| s ∈ {0,1}
x
,x = 0,..., log n} is a
key-forest of the set system Φ
SD
with degree 3.
Proof. Due to the definition of F
Lb
for any L ∈{0,1}
x
with 0 ≤ x ≤ log n−1
and b ∈{0,1}, it is easy to observe that the tree edges follow the superset rela-
tion, i.e. it holds that a parent of a node is a subset of that node. Now consider
any four nodes in the tree F
Lb
denoted by (L
1
,R
1
), (L
2
,R
2
), (L
3
,R
3
), (L
4
,R
4
)
for which it holds that R
1
is a prefix of R
2
,R
3
and R
2
,R
3
are both prefixes of
R
4
. While this condition is necessary for a cycle (albeit not su
cient) it also
suggests that R
2
,R
3
must satisfy that one is a prefix of the other and thus
the four nodes cannot be in a cycle.
