tain ciphertexts D = C + Ôłç and D = C + Ôłç, and
Software Encryption, FSEÔÇ™99, Lecture Notes in
decrypts them to plaintexts Q and Q . The choice Computer Science, vol. 3404, ed. L.R. Knudsen.
of Ôłç is such that the difference propagates to the Springer-Verlag, Berlin, 156ÔÇ“170.
difference Ôłç Ôł— in the decryption direction through
the lower half of the cipher. For the right quar-
tet of texts, difference Ôł— is created in the mid-
dle of the cipher between partial decryptions of D
and D which propagates to the difference in the
CONCEPT DEFINITION APPLICATIONS:
plaintexts Q and Q . This can be detected by the AND
attacker. The concept of broadcast encryption deals with
Moreover, working with quartets (pairs of pairs) methods that allow to ef´¬üciently transmit infor-
provides boomerang attacks with additional ´¬ültra- mation to a dynamically changing group of priv-
tion power. If one partially guesses the keys of the ileged users who are allowed to receive the data.
top round one has two pairs of the quartet to check It is often convenient to think of it as a revoca-
whether the uncovered partial differences follow tion scheme, which addresses the case where some
the propagation pattern, speci´¬üed by the differen- subset of the users are excluded from receiving the
tial. This effectively doubles the attackerÔÇ™s ´¬ültra- information.
tion power. The problem of a center transmitting data to
The attack was demonstrated with a practical a large group of receivers so that only a pre-
cryptanalysis of a cipher which was designed with de´¬üned subset is able to decrypt the data is at
provable security against conventional differen- the heart of a growing number of applications.
tial attack , as well as on round-reduced ver- Among them are pay-TV applications, multicast
sions of several other ciphers. The related method (or secure group) communication, secure distribu-
of the inside out attack was given in the same pa- tion of copyright-protected material (e.g., music),
per. Further re´¬ünements of the boomerang tech- digital rights management, and audio streaming.
nique have been found in papers on so-called am- Different applications impose different rates for
pli´¬üed boomerang and rectangle attacks [1, 3]. In updating the group of legitimate users. Users are
certain cases a free round in the middle may be excluded from receiving the information due to
gained due to a careful choice of the differences payments, subscription expiration, or since they
coming from the top and from the bottom [2, 5]. have abused their rights in the past.
One special case is when the receivers are state-
Alex Biryukov less. In such a scenario, a (legitimate) receiver is
not capable of recording the past history of trans-
missions and change its state accordingly. Instead,
its operation must be based on the current trans-
mission and its initial con´¬üguration. Stateless re-
 Biham, E., O. Dunkelman, and N. Keller (2002).
ceivers are important for the case where the re-
ÔÇťNew results on boomerang and rectangle attacks.ÔÇŁ
ceiver is a device that is not constantly on-line,
Fast Software Encryption, FSE 2002, Lecture Notes
such as a media player (e.g., a CD or DVD player
in Computer Science, vol. 2365, eds. J. Daemen and
where the ÔÇťtransmissionÔÇŁ is the current disc [4,10],
V. Rijmen. Springer-Verlag, Berlin, 1ÔÇ“16.
a satellite receiver (GPS) and perhaps in multicast
 Biryukov, A., C. De Cannire, and G. Dellkrantz
(2003). ÔÇťCryptanalysis of SAFER++.ÔÇŁ Advances applications).
in CryptologyÔÇ”CRYPTO 2003, Lecture Notes Broadcast encryption can be combined with
in Computer Science, vol. 2729, ed. D. Boneh. tracing capabilities to yield trace-and-revoke
Springer-Verlag, Berlin. NES/DOC/KUL/WP5/028. schemes. A tracing mechanism enables the ef´¬ücient
Full version available at http://eprint.iacr.org/2003/
tracing of leakage, speci´¬ücally, the source of keys
used by illegal devices, such as pirate decoders or
 Kelsey, J., T. Kohno, and B. Schneier (2001). ÔÇťAm-
clones. Trace-and-revoke schemes are of particu-
pli´¬üed boomerang attacks against reduced-round
lar value in many scenarios: they allow to trace
MARS and Serpent.ÔÇŁ Fast Software Encryption,
the identity of the user whose key was leaked; in
FSE 2000, Lecture Notes in Computer Science,
turn, this userÔÇ™s key is revoked from the system
vol. 1978, ed. B. Schneier. Springer-Verlag, Berlin,
for future uses.
Broadcast encryption 57
What are the desired properties of a broadcast attentiveness. On the other hand, in the stateful
encryption scheme? A good scheme is character- case, gradual revocation of users is particularly
ized by ef´¬ücient.
r Low bandwidthÔÇ”we aim at a small message The logical-tree-hierarchy (LKH) scheme, sug-
expansion, namely that the length of the en- gested independently in the late 1990s by Wallner
crypted content should not be much longer than et al.  and Wong et al. , is designed to
the original message. achieve secure group communication in a multi-
r Small amount of storageÔÇ”we would like the cast environment. Useful mainly in the connected
amount of required storage (typically keys) at mode for multicast re-keying applications, it re-
the user to be small, and as a secondary objec- vokes or adds a single user at a time, and up-
tive the amount of storage at the server to be dates the keys of all remaining users. It requires
manageable as well. a transmission of 2 log N keys to revoke a single
r AttentivenessÔÇ”does the scheme require users user, each user is required to store log N keys and
to be on-line ÔÇťall the time?ÔÇŁ If such a require- the amount of work each user should do is log N
ment does not apply, then the scheme is called encryptions (the expected number is O(1) for an
stateless. average user). These bounds are somewhat im-
r ResilienceÔÇ”we want the method to be resilient proved in [2, 3, 12, 16, 17], but unless the storage
to large coalitions of users who collude and at the user is extremely high they still require a
share their resources and keys. transmission of length (r log N). This algorithm
In order to evaluate and compare broadcast en- may revoke any number of users, regardless of the
cryption methods, we de´¬üne a few parameters. Let coalition size.
N be the set of all users, |N | = N, and R ÔŐ‚ N be Luby and Staddon  considered the infor-
a group of |R| = r users whose decryption privi- mation theoretic (see computational complexity,
leges should be revoked. The goal of a broadcast information theory, and security) setting and de-
encryption algorithm is to allow a center to trans- vised bounds for any revocation algorithms under
mit a message M to all users such that any user this setting. Garay et al.  introduced the no-
u Ôłł N \ R can decrypt the message correctly, while tion of long-lived broadcast encryption. In this sce-
a coalition consisting of t or fewer members of R nario, keys of compromised decoders are no longer
cannot decrypt it. The important parameters are used for encryptions. The question they address is
therefore r, t, and N. how to adapt the broadcast encryption scheme so
A system consists of three parts: (1) a key assign- as to maintain the security of the system for the
ment scheme, which is an initialization method for good users.
assigning secret keys to receivers that will allow CPRM, which stands for content protection for
them to decrypt. (2) The broadcast algorithmÔÇ” recordable media,  is a technology for protect-
given a message M and the set R of users to revoke ing content on physical media such as recordable
outputs a ciphertext message M that is broad- DVD, DVD Audio, Secure Digital Memory Card,
cast to all receivers. (3) A decryption algorithmÔÇ” and Secure CompactFlash. It is one of the meth-
a (nonrevoked) user who receives ciphertext M ods that explicitly considers the stateless scenario.
should produce the original message M using its There, the message is composed of r log N encryp-
secret information. tions, the storage at the receiver consists of log N
keys, and the computation at the receiver requires
HISTORY PROBLEM: The issue of se- a single decryption. It is a variant on the tech-
niques of .
cure broadcasting to a group has been investi-
The subset difference method for broadcast en-
gated earlier on, see for example . The ´¬ürst
cryption, proposed by Naor, Naor, and Lotspiech
formal de´¬ünition of the area of broadcast encryp-
[13, 14], is most appropriate in the stateless sce-
tion, including parameterization of the problem
nario. It requires a message length of 2r Ôł’ 1 (in
and its rigorous analysis (as well as coining the
the worst case, or 1.38r in the average case) en-
term) was done by Fiat and Naor in  and has
cryptions to revoke r users, and storage of 1 log2 N
received much attention since then; see for exam- 2
keys at the receiver. The algorithm does not as-
ple [2, 6, 8, 9, 11, 13ÔÇ“15, 18, 19]. The original broad-
sume an upper bound of the number of revoked
cast encryption method of  allows the removal
receivers, and works even if all r revoked users
of any number of users as long as at most t of them
collude. There the message length is O(t log2 t), a collude. The key assignment of this scheme is com-
putational and not information theoretic, and as
user must store a number of keys that is logarith-
such it outperforms an information theoretic lower
mic in t and the amount of work required by the
╦ť bound on the size of the message . A rigor-
user is O(r/t) decryptions. The scheme can be used
ous security treatment of a family of schemes,
in a stateless environment as it does not require
58 Broadcast encryption
including the subset difference method, is pro- information. The idea then is to obtain a scheme
vided in . Halevy and Shamir  have sug- for larger t by various partitions of the user set,
gested a variant of subset difference called LSD where for each such partition the basic scheme is
(layered subset difference). The storage require- used.
ments are reduced to O(log1+╬µ N) while the mes-
Logical Key Hierarchy
sage length is O(r/╬µ), providing a full spectrum
between the complete subtree and subset differ-
The LKH (logical key hierarchy) scheme [18ÔÇ“20]
ence methods. A reasonable choice is ╬µ = 2.
maintains a common encryption key for the active
Both LKH and the subset difference methods
group members. It assumes that there is an initial
are hierarchical in nature and as such are partic-
set N of N users and that from time to time an ac-
ularly suitable to cases where related users must
tive user leaves and a new value for the group key
all be revoked at once, for instance, all users whose
should be chosen and distributed to the remain-
subscription expires on a certain day.
ing users. The operations are managed by a center
It is also important to realize that many imple-
which broadcasts all the maintenance messages
mentations in this ´¬üeld remain proprietary and
and is also responsible for choosing the new key.
are not published both for security reasons (not to
When some user u Ôłł N is revoked, a new group
help the pirates) as well as for commercial reasons
key K should be chosen and all nonrevoked users
(not to help the competitors).
in N should receive it, while no coalition of the
revoked users should be able to obtain it; this is
CONSTRUCTIONS: A high level overview of three called a leave event. At every point a nonrevoked
fundamental broadcast encryption constructions user knows the group key K as well as a set of
is outlined below. Details are omitted and can be secret ÔÇťauxiliaryÔÇŁ keys. These keys correspond to
found in the relevant references. One technique subsets of which the user is a member, and may
that is commonly used in the key assignment of change throughout the lifetime of the system.
these constructions is the derivation of keys in a Users are associated with the leaves of a full bi-
tree-like manner: a key is associated with the root nary tree of height log N. The center associates a
of a tree and this induces a labeling of all the nodes key Ki with every node vi of the tree. At initial-
of the tree. The derivation is done based on the ization, each user u is sent (via a secret channel)
technique ´¬ürst used by Goldreich, Goldwasser, and the keys associated with all the nodes along the
Micali (GGM) . path connecting the leaf u to the root. Note that
the root key K is known to all users and can be
used to encrypt group communications.
In order to remove a user u from the group (a
leave event), the center performs the following op-
The idea of the construction in  is to start with
erations. For all nodes vi along the path from u
the case where the coalition size (the number of
to the root, a new key Ki is generated. The new
users who collude and share their secret informa-
keys are distributed to the remaining users as fol-
tion) is t and reduce it to the case where the coali-
lows: let vi be a node on the path and v j be its
tion size is 1, the basic construction. For this case,
child on the path and v its child that is not on the
suppose that there is a key associated with each
path. Then Ki is encrypted using K j and K (the
user; every user is given all keys except the one as-
latter did not change), i.e., a pair of encryptions
sociated with it. (As an illustration, think of the
EK j (Ki ), EK (Ki ) . The exception is if vi is the par-
key associated with a user as written on its fore-
ent of the leaf u, in which case only a single encryp-
head, so that all other users except for itself can
see it.) To broadcast a message to the group N \ R, tion using the sibling of u is sent. All encryptions
are sent to all the users.
the center constructs a broadcast key by Xoring
all keys associated with the revoked users R. Note
that any user u Ôłł N \ R can reconstruct this key, Subset Difference
but a user u Ôłł R cannot deduce the key from its
own information. This naive key assignment re- The subset difference construction de´¬ünes a col-
quires every user to store N Ôł’ 1 keys. Instead, by lection of subsets of users S1 , . . . , Sw , Sj ÔŐć N . Each
deriving the keys in a GGM tree-like process, the subset Sj is assigned a long-lived key L j; a user u
key assignment is made feasible by requiring ev- is assigned some secret information Iu so that ev-
ery user to store log N keys only. ery member of Sj should be able to deduce L j from
its secret information. Given a revoked set R, the
The construction is then extended to handle the
case where up to t users may share their secret remaining users are partitioned into disjoint sets
Broadcast encryption 59
Si1 , . . . , Sim from the collection that entirely cover  Goldreich, O., S. Goldwasser, and S. Micali (1986).
ÔÇťHow to construct random functions.ÔÇŁ JACM, 33
them (every user in the remaining set is in at least
one subset in the cover) and a session key K is en-
 Halevy, D. and A. Shamir (2002). ÔÇťThe LSD Broad-
crypted m times with Li1 , . . . , Lim . The message is
cast encryption scheme.ÔÇŁ Advances in Crypto-
then encrypted with the session key K.
logyÔÇ”CRYPTO 2002, Lecture Notes in Com-
Again, users are associated with the leaves of a
puter Science, vol. 2442, ed. M. Yung. Springer,
full binary tree of height log N. The collection of Berlin.
subsets S1 , . . . , Sw de´¬üned by this algorithm corre-  Kumar, R., R. Rajagopalan, and A. Sahai (1999).
sponds to subsets of the form ÔÇťa group of receivers ÔÇťCoding constructions for blacklisting problems
G1 minus another group G2 ,ÔÇŁ where G2 ÔŐ‚ G1 . The without computational assumptions.ÔÇŁ Advances in
two groups G1 , G2 correspond to leaves in two full CryptologyÔÇ”CRYPTOÔÇ™99, Lecture Notes in Com-
binary subtrees. Therefore, a valid subset S is rep- puter Science, vol. 1666, ed. J. Wiener. Springer-
resented by two nodes in the tree (vi , v j) such that Verlag, Heidelberg, 609ÔÇ“623.
 Lotspiech, J., S. Nusser, and F. Pestoni (2002).
vi is an ancestor of v j and is denoted as Si, j. A leaf
ÔÇťBroadcast encryptionÔÇ™s bright future.ÔÇŁ Computer,
u is in Si, j iff it is in the subtree rooted at vi but
35 (8), 57ÔÇ“63.
not in the subtree rooted at v j, or in other words
 Luby, M. and J. Staddon (1998). ÔÇťCombinato-
u Ôłł Si, j iff vi is an ancestor of u but v j is not.
rial bounds for broadcast encryption.ÔÇŁ Advances
The observation is that for any subset R of re- in CryptologyÔÇ”EUROCRYPTÔÇ™98, Lecture Notes
voked users, it is possible to ´¬ünd a set of at most in Computer Science, vol. 1403, ed. K. Nyberg.
2r Ôł’ 1 subsets from the prede´¬üned collection that Springer-Verlag, Heidelberg, 512ÔÇ“526.
cover all other users N \R.  McGrew, D. and A.T. Sherman (1998). Key es-
A naive key assignment that assigns to each tablishment in large dynamic groups using one-
user all long-lived keys of the subsets it belongs way function trees. Available: www.csee.umbc.edu/
to requires a user to store O(N) key. Instead, this
 Naor, D. and M. Naor (2003). ÔÇťProtecting crypto-