Cryptography Reference
In-Depth Information
garding the parameters of the set system AS
Φ
{1,2}
that is the factorizable set
sytem defined over a set of size n = 2
2
k
, we have the following immediate
corollary.
Corollary 2.58. Consider the broadcast encryption scheme based on the set
system AS
Φ
{1,2}
where k = log log n; the transmission overhead for the ci-
phertext revoking r users is O(r log log n). The key-storage for each receiver
is O(log log n· log n), and the computation overhead for a receiver is bounded
by log n.
Fig. 2.21. (left) the key-forest of the set system AS
Φ
{1,2}
. The edges define the
trees in the key-forest. (right) the filter for a specific user, the black nodes represent
the roots of the trees in the intersection of the key-forest and the filter.
2.7 Bibliographic notes
The concept of broadcast encryption was introduced in the work by Berkovits
[
10
]. Combinatorial broadcast encryption schemes can be constructed by em-
ploying probabilistic techniques or with explicit combinatorial constructions.
Examples of this category include the first paper [
42
] that introduced the first
formal construction of a broadcast encryption and employed a probabilistic
design as well as others such as [
87
,
53
] that employed explicit combinator-
ial constructions such as the ones we focused on in this chapter. Recall that
structured broadcast encryption schemes utilize the key-space so that it has
some structure that enables the preparation of ciphertexts that are decipher-
able only by the enabled users. Examples of this category include schemes
that are based on polynomial interpolation [
90
,
37
] where keys are points of
a polynomial over a finite field and schemes based on bilinear maps such as
[
18
] where the discrete-logarithms of the keys over an elliptic curve group are
different powers of the same base.
Given that the intended application of broadcast encryption is content dis-
tribution, it is expected that the scheme would handle large messages. This
