Corrupting one vs. corrupting many: the case of broadcast and multicastencryption

Authors: Daniele Micciancio, Saurabh Panjwani

International Colloquium on Automata, Languages and Programming - Proceedings of ICALP 2006, Venice, Italy. Springer LNCS 4052, pp.70-82 (July 2006)

[BibTeX] [Postscript] [PDF]

Abstract: In this paper, we analyze group key distribution protocols for broadcast and multicast scenarios that make blackbox use of symmetric encryption and a pseudorandom generator in deriving the center's messages. We first show that for a large class of such protocols, in which all communication consists of sequences of ciphertexts of the form Enc(K1,K2) (i.e., a random or pseudorandom key K2 encrypted under some other random or pseudorandom key K1), security in the presence of a single malicious receiver is equivalent to that in the presence of collusions of multiple corrupt receivers. On the flip side, we find that if a protocol is allowed to nest the encrytion function (that is, generate ciphertexts created by enciphering ciphertexts themselves), this equivalence relation breaks down: there exist protocols, even for stateless receivers, that use nested encryption, are secure against single miscreants but are totallyinsecure when receiver collusions are permitted.

Our equivalence and separation results are proven first in a symbolic model of computation, treating encryption and pseudorandom generators as abstract operations with perfect security properties. Via a computational soundness theorem, we then translate the same results into a richer computational model, closer to the real implementations of protocols. Our equivalence result on single-encryption based protocols holds in the computational setting, provided certain simplesyntactic restrictions (like the absebse of encryption cycles) are obeyed by the protocol. For the case of stateful protocols (corresponding to the multicast encryption model), equivalence is achieved for non-adaptive corruption of receivers while for stateful ones (akin to broadcast encryption), adaptive corruptions are also captured by the result.

We apply our results to the analysis of eleven existing protocols for broadcast and multicast encryption. Eight of these protocols had not been proven to be secure (in a strong computational sense) prior to our work. While our results directly establish the security of most of these eight protocols, we uncover weaknesses in some of them. For the insecure protocols, we provide an appropriate fix and establish security of the fixed protocol.