A combinatorial study of communication, storage and traceability in broadcast encryption systems

In this thesis we analyze a model of broadcast encryption based on that of Fiat and Naor. In this model a center needs to allocate keys to users in order to be able to broadcast to selected sets of users with security. A protocol for each subset of users defines which subsets of keys are sufficient to receive the broadcast. There is a trade-off between the number of keys each user stores and the number of transmissions the center needs to make in order to establish a common key amongst the users in a specific subset. The more keys each user has, the fewer the number of transmissions that are necessary, and vice versa. We prove lower bounds on the maximum and average number of keys per user for a class of protocols (called consistent protocols) that are fairly general and also easy to implement. We show that the same lower bounds hold when the protocols are arbitrary, if the number of transmissions is restricted. We describe a construction of a broadcast encryption system that is close to optimal with respect to these bounds and uses the most secure form of protocol (the OR protocol). We describe constructions with less secure protocols that are within a constant factor of the bounds. One of these constructions uses AND protocols, which are complementary to OR protocols.; We also consider the problem of traitor users pooling their keys to construct a pirate decoder. A broadcast encryption system is said to have traceability if it is possible to identify at least one traitor user upon confiscation of a pirate decoder. We prove a necessary condition and a sufficient condition for traceability, each of which is helpful in determining the traceability of specific broadcast encryption systems. Traceability is {dollar}Theta(sqrt{lcub}t{rcub}){dollar} in the OR protocols construction. At the other end of the spectrum, a sufficiently optimal broadcast encryption system with AND protocols has only 1-traceability. The traceability of the AND protocols construction meets this bound.