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-

BROADCAST ENCRYPTION

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 [4], 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,

References

its operation must be based on the current trans-

mission and its initial con¬guration. Stateless re-

[1] 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

[2] 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

109/

used by illegal devices, such as pirate decoders or

[3] 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.

75“93.

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. [18] and Wong et al. [19], 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 [11] 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. [6] 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, [4] 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-

OF THE

niques of [5].

cure broadcasting to a group has been investi-

The subset difference method for broadcast en-

gated earlier on, see for example [1]. 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 [5] 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 [5] 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 [11]. 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 [14]. Halevy and Shamir [8] 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) [7]. 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.

Fiat“Naor Construction

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 [5] 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 [7] 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

(4), 792“807.

one subset in the cover) and a session key K is en-

[8] 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- [9] 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.

[10] 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

[11] 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. [12] 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/

sherman/

to requires a user to store O(N) key. Instead, this

[13] Naor, D. and M. Naor (2003). “Protecting crypto-