Broadcast Encryption - Encryption for Digital Content - page 35

ment mapping. In the setting of combinatorial schemes, we can think that each
key corresponds to a set of users. The transmission problem then becomes a
type of a set-cover problem: given the set of enabled users N\R find the best
way to cover it using the subsets that correspond to the assigned keys. Com-
binatorial schemes can be constructed by employing probabilistic techniques
or with explicit constructions. The second category of broadcast encryption,
that can be called structured, assumes that the key-space has some structure
that enables the preparation of ciphertexts that are decipherable only by the
enabled users. For example a polynomial function can be used as a master
key and each user can own a point of this polynomial. Messages can be en-
crypted under a point of a related polynomial and successful decryption can
be achieved by the ability to interpolate the related polynomial.
In this chapter we will focus on explicit combinatorial schemes. An im-
portant characteristic of such schemes is that they are suitable for e cient
implementation as they can be readily paired with an e cient underlying
block-cipher such as the Advanced Encryption Standard 1 to yield very effec-
tive broadcast encryption in the symmetric key setting. The explicitness of
such constructions guarantees that there is no error probability in the expres-
sion of their e ciency and security guarantees. Moreover, for such schemes, as
we will illustrate, there is a way to express su cient requirements for effective
broadcast encryption in a compact algebraic fashion.
We note that most broadcast encryption schemes incur an overhead in
the transmission that makes them unsuitable for the delivery of long plain-
texts due to e ciency degradation. This issue is fairly common with crypto-
graphic functions with special properties with the most prominent example
being public-key encryption that includes schemes such as ElGamal and RSA.
The way this is dealt in practice is through a hybrid approach. In particular
two levels of encryption are used: at the first layer, the encryption is em-
ployed to encrypt a one-time key. Next, at the second layer, an e cient block
or stream cipher is employed in combination with the one-time key. In this
chapter we will assume that this approach is taken for the deployment of a
broadcast encryption scheme.
2.1 Definition of Broadcast Encryption
A broadcast encryption scheme BE is a triple (KeyGen,Encrypt,Decrypt)
of algorithms. The parameter of the scheme is n, the number of receivers and is
associated with three sets K,M,C corresponding to the sets of keys, plaintexts
and ciphertexts respectively. We describe the I/O of these algorithms below:
• KeyGen. It is a probabilistic algorithm that on input 1 n , it produces
(ek,sk 1 ,...,sk n ). The decryption key sk i is to be assigned to the i-th user
1 The Advanced Encryption Standard [ 32 ] is a symmetric encryption scheme
adopted by the National Institute of Standards and Technology, USA in 2002.