Broadcast Encryption

Amos Fiat and  Moni Naor


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(k2 log2 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 log2 k log (1/p)) messages.

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

Related On-Line Papers:

Back to On-Line Publications

Back Home