Cryptography Reference
In-Depth Information
Hence, in any case, there will be a corresponding subset in the Stratified
Subset Difference for each subset in the Key Chain Tree.
In the formalization of the Key-Poset framework we introduced in this
chapter, the subset cover families of [
6
,
50
,
87
,
122
] are all factorizable (see
Section
2.5
) and thus the results we laid out provide a unified way for solving
revocation e
ciently and optimally in all these schemes.
The transformation we discussed in section
2.6.1
was introduced in [
55
]
to reduce the computation overhead sacrificing some transmission and key-
storage capacity. A similar technique was already discussed in [
6
,
50
], and
employed to improve the computation overhead. The generic transformation
described in [
55
] increases the transmission overhead by a factor of k. To take
the transmission back from 2kr to 2r, the work [
56
] presented a technique that
works only for the schemes based on key-chains [
6
,
50
,
122
]. This technique
will result in, not suprisingly, the basic set system depicted on the left of the
Figure
2.16
.
In Section
2.6.2
we presented a new generic transformation that gives rise
to new schemes with different e
ciency parameters. We presented an instan-
tiation of the transformation, which ignoring log log n factors, is a scheme
that simultaneously achieves communication overhead proportional to r (the
number of revoked users), receiver storage log n, and receiver computation
proportional to log n. The same e
ciency parameters are exhibited by the
general Layered Subset Difference (LSD) method (see ([
53
])), and it turns
out that this instantiation is an isomorphic representation of the general LSD
method (in particular when the LSD is used for the optimal depth of layer-
ing). It worth pointing out that the description of the LSD is different from
the recursive application of XTrans presented in this chapter and it requires
some effort to observe the equivalence. We leave it as an exercise to establish
formally this equivalence.
Subset cover schemes that have been discussed in this chapter are designed
for stateless receivers. A stateless receiver need not maintain state from one
transmission to the next. It can go arbitrarily o
ine without losing its recep-
tion capability in the long run. It is also independent of changes within the
receiver population, in particular, the decryption capability of receiver keys
do not change if other receivers join or leave the system.
While stateless receivers are more easy to administer in a system deploy-
ment they affect the revocation capability as well as the e
ciency of the
system. Suppose that the revocation list of a system employing broadcast en-
cryption scheme increases as time passes. The state-of-the-art suggests that
this would yield an increase in the transmission overhead of at least linear in
the number of revocations. Such increase can be unbearable for many applica-
tion scenarios. For instance, systems that employ smart-card like devices can
only handle limited computation and storage. Refreshing keys in a fully state-
ful manner has been discussed in the context of key-management protocols
such as the Logical Key Hierarchy, cf. [
25
,
26
,
107
,
121
,
125
]. A hybrid ap-
