Cryptography Reference
In-Depth Information
parameters and requires a certain property from the underlying set system,
called the X− property, that we will define herein. The number of users in
the resulting set system equals the square of the number of users of the un-
derlying set system while the transmission overhead increases by a constant
amount while the storage approximately doubles. The transformation pre-
serves a logarithmic computation overhead, i.e. given that the computation
overhead of the basic set system is logarithmic in the number of receivers, the
new computation overhead remains logaritmic in the new size of the receiver
population.
In order to understand the transformation it will be helpful to think of the
set system as the graph corresponding to the transitive reduction diagram
of the corresponding poset. The X-property that is required by the basic set
system is crucial in curbing the increase in the parameters of the set system
while squaring the number of receivers. More formally, the property is defined
as follows.
Definition 2.51. We say a fully-exclusive set system (Φ,⊆) defined over a
set M = {1,...,2 m } satisfies the X−property if
1. There exist two elements S 1 ,S 2 ∈ Φ so that F(S 1 ) and F(S 2 ) are disjoint
full binary trees of height m−1. We denote them by F Φ and F Φ respectively.
2. For each user u ∈M, the complement of the atomic filter F(u) intersects
with the above binary trees on a single path of length m; i.e. P u ∩ (F(S 1 ) ∪
F(S 2 )) = { u p ,..., u p } where u p is a node in the key poset of the set system Φ
that is a parent of u i−1
for i = 2,...,m.
Observe that due to the structure imposed by the X− property the top
leaves of the binary tree filters F(S 1 ) and F(S 2 ) will be as many as the number
of receivers in the set system. The second requirement of the X − property
ensures that each leaf is uniquely related to an atom, and further it will hold
that the leaves represent the subsets of the form C u = df M\{u}.
The goal of the transformation is to expand the receiver population covered
by the set system in a non-trivial way. This will be again through generat-
ing many copies of the basic set system and combining them in a non-trivial
way. The first requirement in the X−property gives a way to combine a set
system with an upper level copy and connecting non-trivial edges between
those two set systems. Recall that the k-layering transformation doesn't sup-
port such interaction between the copies. The second requirement not only
helps in supporting edge-transitions between upper and lower level copies but
also makes it easier to employ the computational key assignment discussed
in Definition 2.21 . Such employment will make the transformation keep the
computation overhead logarithmic while giving a reasonable increase in key
storage. We next define the transformation formally.
Definition 2.52. The transformation XTrans is a mapping over set systems
that satisfy the X−property. The transformation takes the key-poset of a set
system Φ over M = {1,...,2 m } and outputs a new key-poset of a set system
 
 
Search WWH ::




Custom Search