This work is about constructing methods for simultaneously broadcasting multimedia data privately to a set of subscribers, and on various connections among important efficient variants of the general paradigm. Broadcast Encryption is such a fundamental primitive supporting sending a secure message to any chosen target set of N users. While many efficient constructions are known, understanding the efficiency possible for an “Anonymous Broadcast Encryption” (\(\mathsf {AnoBE}\)), i.e., one which can hide the target set itself, is quite open. The best solutions by Barth, Boneh, and Waters (’06) and Libert, Paterson, and Quaglia (’12) are built on public key encryption (\(\mathsf {PKE}\)) and their ciphertext sizes are, in fact, N times that of the underlying \(\mathsf {PKE}\) (rate=N). Kiayias and Samary (’12), in turn, showed a lower bound showing that such rate is the best possible if N is an independent unbounded parameter. However, when considering certain user set size bounded by a system parameter (e.g., the security parameter), the problem remains interesting. We consider the problem of comparing \(\mathsf {AnoBE}\) with \(\mathsf {PKE}\) under the same assumption. We call such schemes Anonymous Broadcast Encryption for Bounded Universe – \(\mathsf {AnoBEB}\).
We first present an \(\mathsf {AnoBEB}\) construction for up to k users from \(\mathsf {LWE}\) assumption, where k is bounded by the scheme security parameter. The scheme does not grow with the parameter and beat the PKE method. Actually, our scheme is as efficient as the underlying \(\mathsf {LWE}\) public-key encryption; namely, the rate is, in fact, 1 and thus optimal.
More interestingly, we move on to employ the new \(\mathsf {AnoBEB}\) in other multimedia broadcasting methods and as a second contribution, we introduce a new approach to construct an efficient “Trace and Revoke scheme” which combines the functionalites of revocation and of tracing people (called traitors) who in a broadcasting schemes share their keys with the adversary which, in turn, generates a pirate receiver. Note that, as was put forth by Kiayias and Yung (EUROCRYPT ’02), combinatorial traitor tracing schemes can be constructed by combining a system for small universe, integrated via an outer traceability codes (collusion-secure code or identifying parent property (\(\mathsf {IPP}\)) code). There were many efficient traitor tracing schemes from traceability codes, but no known scheme supports revocation as well. Our new approach integrates our \(\mathsf {AnoBEB}\) system with a Robust \(\mathsf {IPP}\) code, introduced by Barg and Kabatiansky (IEEE IT ’13). This shows an interesting use for robust \(\mathsf {IPP}\) in cryptography. The robust \(\mathsf {IPP}\) codes were only implicitly shown by an existence proof. In order to make our technique concrete, we propose two explicit instantiations of robust \(\mathsf {IPP}\) codes. Our final construction gives the most efficient trace and revoke scheme in the bounded collusion model.
