Broadcast Encryption

Amos Fiat and Moni Naor

Abstract:

We introduce new theoretical measures for the qualitative and quantitative assessment of encryption schemes designed for broadcast
transmissions. The goal is to allow a central broadcast site to broadcast secure transmissions to an arbitrary set of recipients while minimizing key management related transmissions. We present several schemes that allow a center to broadcast a secret to any subset of privileged users out of a universe of size n so that coalitions of k users not in the privileged set cannot learn the secret.
The most interesting scheme requires every user to store O(k log k log n) keys and the center to broadcast O(k² log²k log n) messages
regardless of the size of the privileged set. This scheme is resilient to any coalition of k users. We also present a scheme that is resilient with
probability p against a random subset of k users. This scheme requires every user to store O(log k log (1/p)) keys and the center to broadcast O(k log²k log (1/p)) messages.

This is a revised version of the Crypto'93 paper:
Postscript, gzipped Postscript.

Related On-Line Papers:

Cynthia Dwork, Jeff Lotspiech and Moni Naor, Digital Signets: Self-Enforcing Protection of Digital Information, Abstract , Postscript, gzipped Postscript
Dalit Naor, Moni Naor and Jeff Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Abstract, Postscript, gzipped Postscript
Moni Naor and Benny Pinkas, Threshold Traitor Tracing, Crypto 98. Postscript, gzipped Postscript
Moni Naor and Benny Pinkas, Efficient Trace and Revoke Schemes, FC'2000. Postscript, gzipped Postscript

Back to On-Line Publications

Back Home