Cryptography Reference
In-Depth Information
ord((S
0
) ∩ P
u
0
) ≤ k · t(d) for any S
0
∈ LTrans
k
(Φ) and any atom u
0
∈
LTrans
k
(Φ).
(ii) if there exists a key-assignment technique for Φ such that the key-
storage for each user is bounded by s(d) for some function s(·) and the com-
putation overhead is bounded by c(d) for some function c(·), then there is a
key-assignment technique that the key-storage in LTrans(Φ) is bounded by
k· s(d) and computation overhead is bounded by c(d).
(S
0
)∩P
u
0
= (S
0
). Otherwise, consider the leaf-to-root path from u
0
to the root
of the key-poset of the set system LTrans(Φ). This path passes over a sequence
of nodes that are at the leaf level of the component set systems, i.e., given
that u
0
∈ [d
k
] can be represented by a string b
1
b
2
...b
k
with b
i
∈ {1,...,d}
for i ∈ [k], the path passes through the set systems Φ
s
0
,Φ
s
1
,...,Φ
s
k−1
where
s
0
= and s
i
= b
1
...b
i
is a substring of the d-digit representation of u
0
with length i. It holds that S
0
belongs to Φ
s
j
for some j ∈{0,...,k−1}. We
observe next that the lower maximal partition of the intersection (S
0
) ∩ P
u
0
will include t(d) sets for each one of the k −j levels starting from the j-th
level and going to the lowest one for a total of (k−j) · t(d). This completes
the proof of item (i).
(ii) The key-assignment for the new set system can be done by employing
the key-assignment independently for each underlying set system. This will
yield a key-storage for a user to be k · s(d) since a user u ∈ [d
k
] with a d-
digit representation of length k is related to k basic set systems in the new
key-poset. On the other hand, the computation time will be same as if the set
system is Φ, since the key of a subset is derivable within the basic set system
that contains this subset.
Applying the layering transformation to the KCT set system.
We next give an example for the application of the layering transformation.
The set system based on Key Chain Tree enjoys a transmission overhead that
is same as the transmission overhead for the Subset Difference along with a
logarithmic key storage while the Subset Difference method has a log-square
key storage. On the other hand the Key Chain Tree method suffers from the
computation overhead in the worst case which is linear in number of receivers.
Consider the set system Φ
KCT
of key chain tree for d receivers. The trans-
formation described in definition
2.48
will yield factorizable set systems over
exponentially growing receiver populations that satisfy the statement of the
theorem
2.50
.
2.6.2 X-Transformation
In this section we describe another transformation of set systems that also
preserves the factorizability property and has superior performance charac-
teristics compared to the layering transformation. The transformation has no
