Broadcast Encryption - Encryption for Digital Content - page 98

Observe that a user u is able to derive the keys for each subset C u 0 in the
body. Each subset C u is the root of an upward binary tree for which the user
requires all or some of the keys. Specifically, based on the X-property there
is a single binary tree for which the user u requires only a subset of the keys
and in fact he would need exactly m keys as it needs a key for each sibling of
a node in the path that excludes u. Hence, employing a 3-fold key extender
to derive the keys for all the nodes in the binary trees using the keys of the
C u sets as the locals a user needs to store m extra keys (the labels of the
nodes that are siblings of the nodes in the unique path that excludes the
user) and thus the computation overhead is bounded by m. It follows that the
key storage is bounded by 2s(m) +m. The computation overhead is bounded
by the maximum of c(m) and m.

Instantiation for X-Transformation

Theorem 2.55 proves that the X-transformation of a set system squares the size
of the population, while the e ciency parameters increase only linearly. This
motivates us to apply successive applications of the transformation described
in Definition 2.52 over a fully-exclusive set system.

Definition 2.56. Let Φ (d) be a factorizable set system defined over a set [d] =
{1,...,d} and further satisfies X− property. We define AS Φ (d) as the fully-
exclusive factorizable set system defined over a set of n = d 2 k

users where

AS j

Φ (d) ) for j = 1,...,k with AS Φ (d) = Φ (d) .
Theorem 2.36 and Theorem 2.55 implies the following corollary which
provides an upper bound on the transmission overhead of the set system
AS Φ (d) and the e ciency of the key-assignment technique.

Φ (d) = XTrans(AS j−1

Corollary 2.57. Let n = d 2 k for some d,k ∈ N and Φ (d) is a factorizable set
system defined over a set of size d that satisfies the X−property. Suppose that
for any subset S ∈ Φ (d) and an atom u of Φ (d) it holds that ord((S)∩P u ) ≤ t(d)
within the poset Φ, the key storage is bounded by s(d) and the computation
overhead is bounded by c(d) for some functions t(·), s(·) and c(·). Consider
now the set system AS Φ (d) over n users:
1. If d = O(1), then the transmission overhead to disable a set of r users in
the set system AS Φ (d) would be O(r(2 log log n)), the key storage is O(log log n·
log n) and the computation overhead would be O(log n).
2. If k = O(1), then the transmission overhead to disable a set of r in the
set system AS Φ (d) would be r(2k + t(d)), the key storage is 2 k · s(d) + k log n

2

and the computation overhead would be max(c(d), log n).

Proof of Corollary 2.57 : Due to the theorem 2.55 the order of a lower
maximal partition of (S∩P u ) for any subset S ∈ AS Φ (d) and any atom u ∈ [d 2 k ]
can be bounded by incrementing t(d) with 2k.