Cryptography Reference
In-Depth Information
of the set system Φ SD compared to the complete subtree is mainly in that it
satisfies the following:
Proposition 2.43. For any subset S ∈ Φ SD and an atom u, it holds that
ord((S) ∩P u ) ≤ 3.
Proof. Suppose S has the encoding j = (L,R). If mbr (j,u) = 0, then the
intersection itself equals to the ideal (S), hence the proposition holds. If not,
then L would be a prefix of u while LR is not a prefix of u. Then we can
write u = LL 0 bU where LL 0 is the longest common prefix of LR and u so that
LR = LL 0 bR 0 and |LL 0 bU| = log N for some U,R 0 . Observe that b ∈ {0,1}
necessarily exists, but U and R 0 may possibly be empty strings.
Consider now the subsets, j 1 = (L,L 0 ), j 2 = (LL 0 b,U), j 3 = (LL 0 b,R 0 )
where j 2 , j 3 are well defined in case U,R 0 exist respectively. It is easy to observe
that none of these subsets are intersecting. Indeed if mbr (j 1 ,v) = 1 for some
v, then it holds that LL 0 is not a prefix of v, so mbr (j 2 ,v) = mbr (j 3 ,v) = 0.
Similarly, if mbr (j 2 ,v) = 1, then it holds that LL 0 b is a prefix of v so LL 0 b not
while v is explicitly excluded from j 1 ; the same reasoning applies to j 3 .
On the other hand, it is easy to verify that any v ∈ S \{u} would be
included in one of the above subsets. Indeed, v ∈ S implies that L is a prefix
of v while LR is not. There are two mutually exclusive cases : (i) either LL 0
is not a prefix of v or (ii) LL 0 c is a prefix of v for some c ∈{0,1}:
Case (i) implies that mbr (j 1 ,v) = 1. On the other hand, for case (ii) if
c = b, then it holds that mbr (j 2 ,v) = 1; otherwise it holds that mbr (j 3 ,v) = 1.
Next we observe that for j 0 ∈ {j 1 , j 2 , j 3 } and i = 1,2,3,4, it holds that
cvr (j 0 ,i) would either contain u or are outside (S). This establishes the fact
that the above subsets correspond to the principal ideals of the lower-maximal
partition of (S) ∩P u .
Applying Theorem 2.36 provides an upper bound on the transmission over-
head for the subset difference set system, resulting in an overhead of 2r + 1.
A simple observation would refine this bound: in particular if S is the subset
for whole receiver population, i.e. the encoding of S is , then j 2 and j 3 would
not exist in the above formulation, in such case the first chopping for Theo-
rem 2.36 will result a lower-maximal partition of order 1. Hence, the overall
transmission overhead will amount to 2r−1.
A direct revocation algorithm.
We also describe a direct revocation algorithm for the subset difference set
system that has the same performance as the generic algorithm described
above. This is useful for historical reasons and in order to provide further
intuition for the way the set system works. The algorithm utilizes the Steiner
Tree induced by the set of revoked users R and the root as well. In this case,
Steiner(R) is the minimal subtree that connects all the leaves corresponding
the user set R. We compute the “broadcast pattern” that is covering the users
Search WWH ::




Custom Search