Cryptography Reference
In-Depth Information
Observe that the trees with a maximum chain-length are F
fl
and F
fr
,
hence the computation overhead is bounded by n function evaluations. The
key storage for a user u is the number of trees in the forest |F
KCT
∩ F(u)|
where F(u) refers to the filter of the user u in the key-poset. Recall that user u
is given the label of the root of each tree in the intersection |F
KCT
∩F(u)|. We
will count the number of trees by counting over each intersection F
Lb
∩F(u):
1. if Lb is not a prefix of u; then F
Lb
∩F(u) is empty.
2. if Lb is a prefix of u, then the intersection F
Lb
∩F(u) is a subchain of F
Lb
.
The second case happens for log n−1 different choices of Lb 6= as a prefix
of u, (Lb can not be equal to u). Including also the subchains from F
fl
and
F
fr
, the total key storage of a user would be 1 + log n.
Factorizability of the KCT set system.
We next show that the key chain tree set system satisfies the factorizability
property and thus we ensure the existence of an e
cient revocation algorithm.
Proposition 2.46. The set system Φ
KCT
is a factorizable set system.
Proof. Our proof will take advantage of the alternative characterization for
factorizability, the diamond property, given in definition
2.32
which is shown
to be equivalent with factorizability (see Theorem
2.33
)
Now consider two subsets j
1
= (L
1
,b
1
R
1
) and j
2
= (L
2
,b
2
R
2
) that are
intersecting. We show that their union is in the set system. Since they are
intersecting there is a common element u for which it holds that L
1
and L
2
are prefixes of u. If L
1
= L
2
, then it is obvious that either one is covering the
other in case b
1
= b
2
, or their union corresponds to a subset in Φ
KCT
that is
containing all leaves rooted at node v
L
1
in case b
1
6= b
2
.
Otherwise, without loss of generality say |L
1
| < |L
2
| and we have that L
1
is a prefix of L
2
. We have two cases: either (1) L
1
b
1
is not a prefix of L
2
or
(2) L
1
b
1
is a prefix of L
2
.
(1) This case implies that all leaves in the subtree rooted at v
L
2
are in-
cluded in the subset encoded by j
1
, hence one is j
1
covers j
2
.
(2) Suppose that L
1
b
1
is a prefix of L
2
. We consider the cases (a) L
2
is a
prefix of L1b
1
R
1
and (b) L
2
is not a prefix of L
1
b
1
R
1
.
• Case (a) : The union of j
1
, j
2
can be expressed as the set (L
1
,b
1
R
0
) where
R
0
is defined by requiring that (L
1
b
1
R
0
,) to be respectively the rightmost
(b
1
= 1) or leftmost (b
1
= 0) leaf of the sets j
1
, j
2
.
• Case (b) : The only feasible arrangement of the sets j
1
, j
2
is that j
2
is
entirely contained in j
1
.
With the above we showed that the union of the two subsets is always in the
family.
Since the set system of Key Chain Tree method satisfies the factorizability
property, our revocation algorithm given in Figure
2.9
applies and is optimal.
