Broadcast Encryption - Encryption for Digital Content - page 56

the design of the underlying set systems. So far we have considered BE basic ,
where each subset in the set system has a unique key selected independently.
This means that for each user u, for which we have K u = {k j | j ∈ J u } and
J u := {j | u ∈ S j }, the user needs to store all the k j keys in a resulting
key vector of length |J u |. This approach provides the key-indistinguishability
property perfectly as we have seen in Proposition 2.7 .
Nevertheless, there are advantages in employing large set systems that
exhibit tradeoffs betwen the communication overhead and the number of sub-
sets a user belongs to. In such case, it can easily become very uneconomical
to follow the independent key assignment approach above. For this reason we
will see alternative strategies that enable the receiver to compress the key
material. The compression mechanisms we are interested in should facilitate
the selective decompression of the needed keys on the fly.
In this section, we will give a general key material compression technique
that works for any set system. In a nutshell, the technique works as follows:
some “select” subsets are assigned keys independently while the keys of the
remaining subsets are derivable through computations employing the keys
of the select subsets. The challenge that immediately springs up with this
methodology is to ensure that key-indistinguishability is preserved.
Next we describe the compression technique in more detail. We will split
the key poset into a forest F of “upward” looking trees so that the root of
any tree is the smallest subset compared to the other subsets in its tree in
the poset partial order. Hence, keys in each tree of F are supersets of the
root and any path of the tree from root to leaf is a chain of the underlying
poset Φ. In each tree the keys will be dependent and in particular any key
that corresponds to a node in a tree would be derivable from the key of any
ancestral node.
From the receiver perspective, a receiver u should be capable of computing
the keys of the subsets in the filter F(u), i.e., all those subsets that contain u.
It follows that u would need to store all the keys of the roots of the trees in
the intersection forest F ∩ F(u) (by slightly abusing notation whenever F is
a forest and A is a set of nodes, we denote F∩A as the forest that is derived
from F after removing any node that is not in A). It is clear that u will be
able to derive any key in its filter from the keys given to it. But to preserve
key-indistinguishability, we need to employ a suitable cryptographic primitive
for deriving keys. We define this next.
Definition 2.19. Let K be a key space and c ∈ N. We say that the function
f c : K 7→ K c is a c-fold key-extender with ε-insecurity if any polynomial-time
test exhibits statistical distance at most ε between the distribution f c (k) and
the distribution hk 1 ,...,k c i where k,k 1 ,...,k c are random variables uniformly
distributed over K.
Note that K would be typically the set of all bitstrings of a particular
length so a key-extender in such case would be a pseudorandom bit sequence
generator that extends its seed by a multiplicative factor of c.