Cryptography Reference
In-Depth Information
F
(
u
)
P
u
=
N
\ F
(
u
)
.
u
u
Fig. 2.14. The P(u) and F(u) sets for a user u in the subset difference key poset
for 8 receivers.
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 easy to see that either of the
following cases holds : (i) one is covering the other entirely, (ii) their union is
equal to the subset (M,b) where L
1
= L
2
= Mb and |b| = 1, (iii) their union
is equal to the subset of all users. In all three cases the union belongs to the
set systems.
In the other case we assume without loss of generality that |L
1
| < |L
2
|.
Then it holds that L
1
is a prefix of L
2
. Moreover, mbr(j
1
,u) = 1 implies that
L
1
R
1
is not a prefix of u while L
2
is a prefix of u, hence L
1
R
1
can not be a
prefix of L
2
. Then we have two cases: (i) either the common prefix of L
1
R
1
and L
2
is shorter than L
2
, or (ii) L
2
is prefix of L
1
R
1
.
For case (i), since L
1
R
1
is not a prefix of L
2
, this case implies that the
common prefix is also shorter than L
1
R
1
. Observe now that for any user u
that satisfies mbr(j
2
,u) = 1, it also holds that mbr(j
1
,u) = 1. Hence one is
covering the other, and their union, the superset among the two, is included
in the set system.
For case (ii) observe that for any user u with a prefix L
1
either satisfies
mbr(j
1
,u) = 1 or satisfies mbr(j
2
,u) = 1. Hence, the union of these two
subsets would either correspond to the subset (M,b) where L
1
= Mb with
|b| = 1 or the set of all users if L
1
= .
Given that the subset difference set system satisfies the factorizability
property, the revocation algorithm given in Figure
2.9
provides the optimal
solution.
Transmission overhead.
As the theorem
2.36
illustrates the transmission overhead depends on the order
of the lower maximal partition of an intersection (S) ∩P
u
. The superiority
