Cryptography Reference
In-Depth Information
2.6.1 Layering Set Systems
In this section, we present a generic transformation of a set system to a new
set system that supports a greater number of receivers. A k-layering of a
set system over d receivers is a transformation that produces a set system
over d
k
receivers where k is an positive integer parameter. While the new set
system supports an exponential in k increase in the number of receivers, the
transmission overhead and the key storage will increase by a factor of only k
while the computation overheadfor key decompression will remain the same.
Such a change in e
ciency parameters has different net effects depending
on the underlying basic set system and may yield advantageous trade-offs
between the transmission and computation overheads and the key storage
needed at the receiver side.
Provided that the computation overhead for copmression of the basic set
system is linear in number of receivers, the transformation results in a set-
system such that the computation overhead is reduced by a 1/k root. Provided
that transmission overhead and/or the key storage is linear in number of
revoked users the parameters in the transformed system would increase by a
multiplicative factor of k; in case the dependency is logarithmic in the number
of receivers there would be no change. The usefulness of the transformation
can be immediately evidenced by applying the transformation over the key
chain tree set system of the previous section. This will yield a non-trivial
trade-off between the transmission overhead and the computation overhead.
Recall that the key chain tree set system enjoys a logarithmic key-storage and
a transmission overhead that is linear in number of revoked receivers while it
suffers from a computation overhead that is linear in number of receivers. The
resulting set system would decrease the computation overhead by an 1/k-th
root while sacrificing somewhat the transmission overhead which will bear an
increase by a multiplicative factor of k.
We describe the transformation in detail next. Let Φ
BS
d
be the basic set
system defined over a set [d] = {1,...,d} on which we apply the transforma-
tion. The k-layering of the basic set system is constructed by generating
d
k
−1
d−1
copies of the basic set system and connecting them in a top-down manner by
merging a leaf of an upper-level set system with the root of a lower-level set
system. We formally, define the transformation as follows:
Definition 2.48. The transformation k-LTrans, given a key-poset of set sys-
tem Φ
BS
d
over [d] = {1,...,d}, outputs a new key-poset of a set system over
a set [d
k
] = {1,...,d
k
}. The construction for the new key-poset will be as
follows:
d
k
−1
d−1
copies of Φ
BS
d
, and label each one with a string s ∈
{1,...,d}
x
where 0 ≤ x ≤ k − 1. We denote the copy with a label s
by Φ
BS
s
.
1. Generate
