Generic Transformation for
Scalable Broadcast Encryption Schemes
Jung Yeon Hwang, Dong Hoon Lee, and Jongin Lim
Graduate School of Information Security CIST,
Korea University, Seoul 136-701, Korea{videmot, donghlee, jilim}@korea.ac.kr

Abstract. Broadcast encryption schemes allow a message sender to broadcast an encrypted data so that only legitimate receivers decrypt it. Because of the intrinsic nature of one-to-many communication in broadcasting, transmission length may be of major concern.
Several broadcast encryption schemes with good transmission overhead have been proposed. But, these broadcast encryption schemes
are not practical since they are greatly sacrificing performance of other efficiency parameters to achieve good performance in transmission length.
In this paper we study a generic transformation method which transforms any broadcast encryption scheme to one suited to desired application environments while preserving security. Our transformation reduces computation overhead and/or user storage byslightly increasing transmission overhead of a given broadcast encryption scheme. We provide two transformed instances. The first instance is comparable to the results of the stratified subset difference (SSD) technique by Goodrich et al. and firstly achieves O(loglog nn) storage, O(log n) computation, and O( log log n r ) transmission, at the same time, where n is the number of users and r is the number of
revoked users. The second instance outperforms theone-way chain based broadcast encryptionof Jho et al., which is the best

known scheme achieving less than r transmission length with reasonable communication and storage overhead.

1. Introduction

applications and moreover support the creation of potential ap-

In recent years broadcast encryption schemes have been inten-

plication scenarios. Since a message sender in BE schemes

sively studied for lots of applications such as satellite-based

broadcasts a message to possible huge number of users, efficien-

commerce, multicast communication, secure distribution of

cy in transmission overhead has been considered as a critical

copyright-protected material and DRM(Digital Rights Manage-

measure by service providers. Therefore, reducing storage orment), etc. Broadcast encryption (BE) schemes are one-to-computation overhead without greatly sacrificing transmission

many communication methods in which a message sender canoverhead is important.

broadcast an encrypted data to a group of users over an insecure

In most practical applications of BE, a group of users may

channel so that only legitimate receivers decrypt it. Especially,

be quite huge and BE schemes should basically provide scalabil-a stateless BE scheme has a useful property that any legitimate

ity, i.e., suitability for a large number of group users. But, unfor-

receiver with its initial set-up can obtain the current group ses-

tunately, most of transmission-efficient BE schemes are notsion key only from the current transmission without the history

scalable since they requires large storage or computation at aof past transmissions. One of main security concerns in theuser device. Especially, these schemes are not suitable to wire-stateless broadcast encryption schemes is how to efficiently ex-less networks where users are holding strictly resource-restrict-clude illegal (revoked) users from a privileged set, that is, how

ed mobile devices.

to ensure that only legal users decrypt an encrypted broadcast
message.

40

OUR CONTRIBUTIONS. In the paper we study a modular ap-

Various BE schemes have been designed to improve effi-

proach to transform an arbitrary BE scheme to a scalable one ef-

ciency. Efficiency of BE schemes is mainly measured by threeficiently while preserving the security of the underlying

parameters: the length of transmission messages, user storage,

scheme.We construct a compiler of which resulting scheme, forand computational overhead at a user device. The ultimate goala large number of group users, maintains transmission overhead

would be to achieve the best efficiency of all three parametersof the original scheme asymptotically but gains reduction insimultaneously. But it seems, to date, that there exists no BE

users storage and/or computation overhead. Hence, by applying

scheme achieving this goal. As an alternative treatment, a trade-our compiler to a known transmission-efficient BE scheme

off between the parameters has been considered. In fact,which is impractical due to large computation or user storage

schemes with a various efficiency trade-off fit into many realfor keys, we can inexpensively construct an efficient and scal-

NAIS Journal

able solution regardless of the structure of the underlying BE

cently Goodrich et al. [9] firstly proposed the stratified subset

scheme.

difference (SSD) method which satisfies O(log n) keys storage

To illustrate our transformation, we concretely present

per user (this is called the log-key restriction) and O(r) transmis-

two compiled instances which provide a good performance insion overhead simultaneously but requires O(n d ) computation

various aspects, in fact, outperform the previously known

overhead where d is a predetermined constant. Their security de-schemes:

pends on the existence of pseudo-random sequence number gen-

- Goodrich et al. [9] proposed the stratified subset difference (SSD) method, which achieves O(r) transmission1d1

erator.
To achieve more efficient transmission overhead, someand O(n ) computation and O(log n) storage overhead perschemes have used algebraic properties such as secret-sharing

user, where n is the number of users, r is the number of re-[15,3]. But these schemes have to broadcast at least r transmis-

voked users, and d is a predefined constant. This is thesion messages in order to expose the shares of revoked users.

best scheme achieving O(r) transmission and O(log n)

Recently, a notable work based on a one-way accumulator wasstorage overhead simultaneously. But under O(log n) com-suggested by Attrapadung et al. to achieve O(1) transmission

1
2
putation restriction, the scheme needs O( log (logn) log n)complexity [2]. Their method uses a trade-off between security

2

storage, which is closer to O(log n) storage overhead per

against collusion and non-secret storage size. However, despiteuser. This should be undesirable in memory-constrainedof constant transmission complexity, their scheme is consideredenvironments. Our first example is a BE scheme which

as impractical in the case of large number of users because oflog nachieves O( log log n r ) transmission, O(log n) computation

massive requirement in non-secret keys and computation cost at

overhead, and O(log n) (precisely log n+1) user storage, atuser side. Boneh and Silverberg [6] proposed a zero-message

the same time.

BE scheme which requires only constant amount of non-secret- Very recently, Jho et al. [14] proposed theone-waystorage by using n-linear maps of which construction seems tochain based broadcast encryption schemes of which one

be very difficult for n > 2. Very recently, Boneh et al. [5] pro-is the best scheme achieving less than r transmission mes-

posed a (public-key) BE scheme using bilinear maps where

sages with user computation overhead proportional to n attransmission length is O(√n), user key storage is a constant size

the worst case. But their scheme is still considered non-and computation overhead is O(√n). Security of their scheme isscalable because of excessive storage requirement, i.e., forbased on the so-called Bilinear Diffie-Hellman Exponent as-a predetermined constant k, (n −k 1) keys storage at a user de-sumption.

vice. The second example is a BE scheme in which thenumber of transmission messages is less than r only ex-

ORGANIZATION. The rest of this paper is organized as follows.

cept for a small number of revoked users, i.e., 0.75% of n,

We review and define some notions of broadcast encryption inwhile user storage and computation overhead are in a rea-

Section 2 and construct our compiler and analyze its efficiency

sonable bound.

in Section 3. We illustrate two compiled instances of our compiler in Section 4. We compare the resulting schemes with the

RELATED WORK. Since the first formal work of BE by Fiat andSD [16], LSD [13], SSD [9], one-way chain based BE [14]Naor [8], many researches [12] have been done to improve theschemes in Section 5. Finally, we conclude with some remarks

efficiency in various aspects by using various trade-off methods

on other issues in Section 6.

and design approaches, i.e., combinatorial designs, logical key
trees, algebraic approaches such as secret sharing, multi-linear

2. Broadcast Encryption

mapping, and cryptographic tools such one-way accumulator.

In this section we briefly review and define the notion of broad-

Some BE schemes based on combinatorial design are sug-cast encryption. Generally BE schemes are classified into twogested to provide information-theoretical security [10,11,17,18].

types: symmetric key and public key based BE schemes. In theBased on a logical key tree structure, a number of broad-symmetric key setting, the only trusted group center GC cancast encryption schemes [20,19,1,2,16,13,9] have been suggest-

generate a broadcast message to users while, in the public key

ed. Significant works among them are the Subset Difference

setting, any users are allowed to broadcast a message. We de-(SD) scheme [16] by Naor et al. and its improvement, thenote by U the set of users and by R ⊂ U the set of revokedlayered SD scheme [13] by Halevi and Shamir. These schemes

users. The following is a formal definition of a symmetric key

achieve O(r) transmission complexity while maintaining O(logbased BE scheme.

2n) computation overhead and O(log n) key storage per user. Re41

Generic Transformation for Scalable Broadcast Encryption Schemes

BROADCAST ENCRYPTION SCHEME. A BE scheme B is a triple

since the information are equivalently needed for all BEof polynomial time algorithms (SetUp, BEnc, Dec), i.e., setup,schemes.

broadcast encryption, and decryption:- SOB(n): User storage overhead is defined as the maxi-- SetUp, the randomized algorithm takes as input a securi-

mum number of private keys initially given to a user.

ty parameter 1λ and user set U. It generates private infor-- COB(n): Computational overhead is defined as the maxi-

mation SKEYu for user u ∈ U. Private information of

mum number of basic computation done by a user device.

group center GC is defined as the set SKEYU of private information of all users.

SECURITY. Basically a BE scheme should provide resiliency to- BEnc, the randomized algorithm takes as input a security

collusion of any set of revoked users. According to the capabili-

λparameter 1 , private information SKEYU of GC, a set R

ties of an adversary and security goal, we can formally defineof revoked users, and a message M to be broadcast. It first

several types of the security notion of broadcast encryption.

generates a session key GSK and outputs (HdrR,CGSK,M)

Here we briefly present the so-called CCA1-security [4] (cho-where a header Hdr is information for a privileged user tosen ciphertext security in the pre-processing mode [7]) of broad-compute GSK and CGSK,M is a ciphertext of M encrypted

cast encryption, which is believed to be sufficient for most ap-

under the symmetric key GSK.

plications. Especially we note that the Subset-Cover framework

Broadcast message consists of [R, HdrR, CGSK,M].
The pair (R, HdrR) and CGSK,M are often called the fullof [16] in which computationally independent keys are used asa message encryption key, is suitable to this notion.
To measure the CCA1-security of a BE scheme B we con-header and the body, respectively.
- Dec, the (deterministic) algorithm takes as input a usersider the following game between an adversary A and a challeng-index indu, private information SKEYu of u, the set of re-er which models adaptive adversarial actions, user corruption

voked users R, and a header HdrR. If u ∈ U＼R then it out-

and chosen ciphertext attack, etc:
- Setup. The challenger runs SetUp(1λ, U) algorithm andputs the session key GSK.
In public key broadcast encryption, the setup algorithm addition-

generates private information of users u ∈ U.

ally generates the public keys PKU of users and PKU instead of- Adversarial Action. A corrupts any user u'

the private information SKEYU of GC is taken as input in the al-vate information SKEYu'

gorithms BEnc and Dec.

ed) user to decrypt a ciphertext C created by A. A also gets

Input terms in the above description may be extended by

to obtain pri-and asks to any (non-corrupt-

the encryption of a message M selected by itself when it

allowing additional input terms such as a revocation thresholdchooses a set R of revoked users.

value, i.e., the maximum number of users that can be revoked.

- Challenge. As a challenge, A outputs a message CM andIn [16] Naor et al. presented the so-called Subset-Covera set R'of revoked users including all ones corrupted byframework. The idea of this abstract method is to define a spe-

A. The challenger selects a random bit b∈{0, 1}. If b=1

cific subset and associate each subset with a (subset) key SK,

the challenger runs BEnc with R'

which is made available only to the users of the given subset.

CGSK,CM). Otherwise it computes C=(Hdr'R', CGSK',RM)

To cover the set U ＼R of privileged users, U＼R are partitioned

where RM is a random message whose length is similar to

into collection of such pre-defined subsets and the (subset) keys

that of the message CM. Then it gives C to A.

SKi associated to the subsets are used to encrypt a session key- Guess. A outputs its guess b'

to obtain C=(HdrR',∈{0, 1}.

GSK. In this case the header consists of ciphertexts of GSK,
(GSK), ...,
(GSK)] where is a symmeti.e., Hdr =[Let CGues denote the event that the adversary correctly guess-ric encryption scheme.

is defined as AdvA,B(λ)=｜2 ・ Pr[CGues] − 1｜ where

R

ε

SK1

ε

SKt

ε

es the bit b in the above game. The advantage of an adversary A
Pr[CGues] is the probability of CGues. We say that a BE

EFFICIENCY. Let n and r be the numbers of total users and re-scheme B is CCA1-secure if for any probabilistic polynomial

voked users for a given BE scheme B, respectively. Efficiency

time adversary A, the advantage AdvA,B(λ) is negligible.

of BE schemes is mainly measured by three parameters: transmission overhead, user storage, and computational overhead.

42- TOB(r, n): Transmission overhead is defined as the total

3. Generic Transformation for Scalable Broadcast

length (number of bits) of a header in a broadcast message

Encryption

transmitted. We exclude the information of indices of re-In this section we present a compiler transforming a broadcast

voked users and the body from the transmission overhead

encryption scheme impractical due to computation overhead or

NAIS Journal

user storage for huge number of users to a scalable one. We as-

is assigned user keys by Bb b・・・b . Let Kb b・・・b b +1 be thesume that the number of group users is denoted by n=ws. The

set of keys assigned to a node vb b・・・b b +1 in Sb b・・・b . Set-variables w and s are to be defined to reduce user storage or

Up then provides each leaf vb b・・・b (i.e., user) with a set

computation overhead in advance.

UKvb b・・・b =Kb ∪ Kb b ∪・・・∪ Kb b・・・b ,

0 1

0 1

0

j j

0 1

j j

j

s

0 1

s

0 1

We first provide an overview of our construction intuitive-

0 1

j

0 1

0 1

s

where Kb is a singleton set of an initial session key.
0ly. The main idea of our method is to apply a given broadcast- BEnc: For given message M and a set R of r revoke

encryption scheme B to a relatively small subset in a hierarchi-

users, it performs the followings to generate a broadcast

cal and independent manner. To implement such a concept, we

message: it first makes the Steiner Tree ST induced by R,

use a complete w-ary tree with height s, where each user is asso-that is, the minimal subtree of T｜w｜ which connects theciated with a leaf. In the tree the root is labeled with a special

root of T｜w｜to all leaves in R. Starting from ST as an ini-

symbol b0=e. If a node at depth less than s is labeled with βtial tree, it recursively removes leaves from ST until ST・・, w}.
then its bi-th child is labeled with βbi where bi ∈ {1,・becomes a single node.

That is, vb b・・・b

1. Find a sibling set S consisting of leaves of ST .

0 1

k−1

is a node in level k where b0b1・・・bk−1 is theconcatenation of all indices on the path from the root to thenode. Let sibling set Sb b・・・b be a set of nodes with a same par0 1j

2. If ｜S｜=w, then it removes from ST all leaves in S andmakes their parent node a leaf.

ent vb b・・・b in the tree. The BE scheme B is applied to each sib-

3. Otherwise, it applies revocation method of BEnc to S

0 1

jling set Sb b・・・b independently, as if nodes in Sb b・・・b are users

and generates ciphertexts of a group session key. Thenfor an independent BE scheme. To revoke a user, by consider-

it removes all leaves in S from ST and makes their par-ing all nodes on the path from the revoked leaf (i.e., user) to theent node a leaf.

0 1

0 1

j

j

root as revoked nodes, we independently apply the revocation- Dec: For given legal user vb b・・・b ∈ U＼R, it first finds

method of B to each sibling set including a node along in thethe user s ancestor vb b・・・b in the lowest level such thatpath from the root to the revoked leaf.

vb b・・・b c ・・・c is a revoked user. To decrypt a group ses-

s

0 1

0 1

0 1

t t+1

t

s

sion key, it uses a key assinged to revoke a node
3.1 Our Compiler

vb b・・・b c ・・・c from Sb b・・・b .
0 1

t t+1

0 1

s

t

Given any BE scheme B = (SetUp, BEnc, Dec), our compiler
constructs a BE scheme B = (SetUp, BEnc, Dec) as follows:

As an example shown in Figure 1, we consider a complete- SetUp: For given security parameter 1λ and a set U of・・, u125}.
5-ary tree with height 3 for a set of 125 users U={u1,・group users, the algorithm performs the following:

A leaf ve235, which is associated with user u40, receives a set of･ First SetUp makes a complete w-ary tree T｜w｜ in whichkeys UKve235=Ke ∪ Ke2 ∪ Ke23 ∪ Ke235 where Ke is a single-

each leaf is associated to each user. Next, (if necessary)
SetUp constructs a user structure for each sibling set in

ton set of an initial group session key, Ke2 is a set of keys assigned to a node ve2 in sibling set Se2 by B.SetUpe2, Ke23 is a

T｜w｜ according to B.

set of keys assigned to a node ve23 in sibling set Se23 by･ Independently running SetUp of B on each sibling sets-1), SetUp assigns keys to each node

B.SetUpe23 and Ke235 is a set of keys assigned to a node ve235
in the sibling set Se235 by B.SetUpe235, as in Figure 1.

(including an interior node). For distinction we denote

To revoke {ve125, ve434}, as in Figure 2, consider the mini-

the BE scheme B and its SetUp applied to Sb b・・・b by

mal subtree ST which connects the root to the leaves ve125 andBb b・・・b and B.SetUpb b・・・b , respectively. That is, eachve434. Taking all nodes with a same parent in ST revoked in

node (which is not actually a user in the tree) in Sb b・・・btheir sibling set Sα, we apply revocation method of Bα to the

Sb b・・・b , (0
0 1

j

j

0 1

0 1

0 1

j

j

j

0 1

j

sibling set Sα. Revocation methods of Be12, Be43, Be1, Be4, Be
R=revoked nodes
Key assignment ofsibling set
Se

1

2

3

4

5

B.SetUpe

1

4

B.BEncewith R=｛ve1, ve4,｝

3

B.BEnce4
with R=｛ve43｝

height s =3
Se2

1

2

3

4

5

Se23
1

2

3

4

B.SetUpe2

B.BEnce1
with R=｛ve12｝

B.SetUpe23

B.BEnce43
with R=｛ve125｝

5

Ve235

Fig.1. Key assignment in our compiler : a complete 5-ary tree

2

5

ve125

4

ve434

B.BEnce43
with R=｛ve434｝

Fig.2. Revocation in our compiler
43Generic Transformation for Scalable Broadcast Encryption Schemes

are sequentially applied to the sibling sets Se12, Se43, Se1, Se4,

COB(n)= Max {COBi (n1/s)｜1it}.

Se in a bottom-up manner, respectively.
In the construction of our compiler, a single broadcast en-

TRANSMISSION OVERHEAD. Generally it is not easy to analyze

cryption scheme are independently applied to each sibling set in

the asymptotic behavior of transmission overhead in compiled

T｜w｜. But the construction allows that different broadcast en-

BE schemes since BE schemes show various transmission over-cryption schemes are applied to different sibling sets, in orderhead. However we assume that transmission overhead in a giv-to provide flexibility depending on the resource restriction of

en BE scheme is monotone increasing (possibly non-decreas-

client devices.We observe that nodes in the higher level (i.e.,ing) as the number of revoked users increases. In this case,closer to the root) become useless more quickly as revokedtransmission overhead TOB(r, n) in a compiled BE scheme isusers are uniformly distributed. Utilizing this observation, we

upper-bounded by s・TOB(r, n1/s).

can use a BE scheme assigning less keys per node at a higher

In particular, if a given BE scheme satisfies the Subset-

level, which will increase the number of transmission messages

Cover framework we can concretely show that TOB(r, n) is re-slightly during initial period. This must be a good trade-off be-

cursively described as follows:cause the initial transmission overhead is relatively small.

r(s − i − 1)TOB(1, ω)+(r mod ωi)TOB(1 +

r−ωi
ωi

ω), ifiω,ω)+ (ωi − (r mod ωi))TOB( r−ωBasically the security of our modular method is based onithe security of a given BE scheme and the independence usager(s − i − 1)TOB(1, ω) + (ωi+1 − r)if ωiγ r

ωi+1.

of the scheme. By using a standard hybrid argument, we canwhere ω=n1/s and γis a number such that the maximum number

prove the following lemma. The proof will appear in the fullof transmission ciphertexts in B for γ revoked users is n−γ.

version of the paper.

The concrete analysis appears in Appendix.

Lemma 1. The compiled scheme preserves the security of the

4 Compiled Instances

underlying broadcast encryption scheme.

We apply our compiler to several transmission-efficient
schemes, which have inefficiency in computational overhead or

3.2 Performance Analysis

user keys storage for huge number of users, to gain scalable andWe analyze efficiency of the presented compiler with respect toefficient BE schemes. The transformation provides reduction inthree efficiency parameters: transmission overhead, user stor-

user storage and/or computation overhead by slightly increasing

age overhead, computational overhead at a user device.

transmission overhead of a given BE scheme.

USER STORAGE OVERHEAD. In a compiled BE scheme, the number

4.1 Broadcast Encryption Scheme for User Devices

of keys that a user should store is｜UKvb b b・・・b ｜=｜Kb0｜+｜Kb0b1｜

with Low-Resource+・・・+｜Kb0b・・bs｜= 1+s・SOB(n1/s). BE schemes satisfying O(log1・In this section we present a BE scheme which achieves O(log n)n) storage restriction have been considered important [9] sinceuser storage, O(log n) computation overhead, and O( log (log n) r)

they are well suited to low-memory devices in wireless mobiletransmission overhead at the same time. To achieve this goal,

networks. We note that the compiled BE scheme B preserves

we first construct a BE scheme B1 which requires 2r transmis-

O(log n) key restriction of the underlying BE scheme B. Con-

sion messages and only 1+log2 n key storage per user, but n op-

cretely, SOB(n) is O(log n) since 1 + s・SOB(n1/s)

erations per user. Next, by applying the compiler to B1, we

0 1 2

1

logw n S +1) = 1 + (c+1)・logw ns

1 + s・(c・

1 + (c+1)・log2 n where c is alog ngain the desired scheme.

constant factor. If storage size in the underlying scheme is lessthan logw n such as a constant then storage size in the compiled

Broadcast Encryption Scheme B1. As a structure of B1

scheme increases up to logw n which is still satisfying O(log n)scheme we consider a segment of the number line L where num-storage restriction.

bers are linearly ordered by their magnitude. For any points iand j (COMPUTATION OVERHEAD. In a compiled BE scheme, the maximum number of the basic operations which a user should per1i), we denote the set {k｜ikj}, called as a closed in-terval, by S[i,j]. For example, S[2,6]={2,3,4,5,6}.
We define two one-way chains, C + and C− associated[i,j]form is COB(n1/s)(=COB(n logw n )) since the size of each siblingwith S[i,j], and, for a given function F: {0, 1}

set at each level is n1/s.

values corresponding to them as follows:[i,j]→ {0, 1}, chain-

log nw
If s= logw(logthen n1/s=logw n. If t different BE schemes Bi (1
w n)

i
44

t) are used for sibling sets in the setup algorithm then+ is a one-way chain such that starts from i and posi- C[i,j]NAIS Journal

tively goes through i + 1,・・・, j − 1 and then ends at j. For a giv+
en sdi∈{0, 1}, the chain-value of C[i,j] is F｜j−i｜(sdi).
- C− is a one-way chain such that starts from j and nega-

t−i
j−t
C−
[t+1,j] are F (sdi) and F (sdj ), respectively.

tively goes through j − 1,・・・, i + 1 and then ends at i. For a giv−ij｜(sdj).
, the chain-value of −C is F｜

with one revoked user. In order to apply the method systemati-

Fd(sd) is computed by repeatedly applying the function F to sd

ly separating each pair of consecutive revoked nodes uij and uij+1

d times.

by performing a binary search on L. BEnc then partitions L so[i,j]en sdj∈{0, 1}[i,j]

For given r revoked users, BEnc applies the above single
revocation method to each disjoint sub-interval including one
cally BEnc uses a binary division. That is, for a given set of revoked points R={ui ,..., ui }, BEnc finds a division point di firstr

1・・∪ S[dr−1+1,dr] where ij∈S[dj−1,dj],that L = S[d0 ,d1]∪S[d1+1,d2]∪・λ

SetUp. For a given security parameter 1 and a set U of users,

d0=1 and dr=n. Finally BEnc covers each subset by using thethe algorithm SetUp performs the following: First it arranges

above single revocation method.

all users in U on a segment of the number line L linearly by the・・, u32}For example, as shown in Figure 4, for U={u1, ・magnitude. A point i in L is associated with a user ui. Next, toand R={u5, u11}, the set U＼R of remaining users is partitioned

give a user a set of private keys, it executes the following key

as follows:
L＼{5, 11}=S[1,8]∪S[9,32]= (C + ∪C− ) ∪(C +assignment.
Starting from S[1,n] as an initial closed interval SetUp performs the following recursively: For a given closed interval S[i,j] for 1

i＜jn, SetUp selects random and in-dependent labels sdi and sdj , and assigns these to users ui

[1,4]

−

[9,10]∪C[12,32]).

[6,8]Then four keys F 3(sd1), F 2(sd6), F 1(sd9), and F 20(sd32) are assigned to four one-way chains, C + , C− , C + , and C− ,
[1,4]

[6,8]

[9,10][12,32]

respectively.

and uj . SetUp computes chain-values by consecutively

After construction of cover sets, BEnc applies anotherapplying F to labels sdi and sdj , respectively. Then Set-

one-way function F'

Up assigns Fk−i(sdi) and Fj−k(sdj) to a user uk. Next Set-

sulting values as keys to encrypt a group session key.

to the chain-values and then uses the re-Up divides the closed interval S[i,j] to get two sub-interi+j−1
2. While a sub-inter-

Decryption. For given legal user uk ∈ U ＼ R, the decryption algo-val is not a singleton, SetUp applies the above assign-

rithm Dec first finds two consecutive revoked users uij and uij+1

vals S[i,m] and S[m+1, j] where m=ment method to the sub-intervals repeatedly. The label sdi

such that k∈S[ij ,ij+1]. Next, by using a binary search, Dec finds(sdj ), which is assigned to the previous closed interval, isreused in a sub-interval S[i,m] (S[m+1, j]) and label sdm

the division point d which firstly separates two points ij and ij+1. If
d k then it computes F k−ij (F d−k(sdd))=F d−ij (sdd). Otherwise,(sdm+1) is newly selected and assigned to a user

it computes Fij+1−k(F k−d−1(sdd+1)) =Fij+1−d−1(sdd+1).

um (um+1, respectively).
By using the above method, SetUp provides a user

SECURITY. We can easily show the correctness of B1 that every

with 1+log2 n keys since 1+log2 n closed intervals includ-privileged user can decrypt an encrypted group session key. Re-

ing the user are gained from the above binary division

voked users are excluded by onewayness of one-way chain andand, for each interval, only one key value is newly as-so cannot obtain useful information to decrypt an encrypted

signed to the user.
・・, u32}, SetUp proFor an example, for U={u1, ・

sd6

vides a user u6 with 6 (=1+log2 25) keys, i.e., chain-values

F（sd5 ）

2F（sd8）

F 5(sd1), F 26(sd32), F 10(sd16), F 2(sd8), F(sd5), and sd6 associated to 4 closed intervals, S[1,32], S[1,16], S[1,8], S[5,8]

5
F（sd
1）

and S[5,6], as in Figure 3.

F10（sd16 ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Broadcast Encryption. The revocation method of B1 is based

F26（sd32 ）32

Fig.3. Key assignment to u 6 in B1

on the following singleton revocation: For a given closed interval S[i,j] of L, to revoke a user ut, that is, a point t∈S[i,j], the reandmaining users are covered by two one-way chains C +

1

2

3

4

5

6

7

8

9 10 11 12 13

32[i,t−1]− , which proceed from each end point toward opposite diC[t+1,j]rections. The use of these two chains obviously excludes aandpoint t in a subset S . The keys associated with C +[i,j][i,t−1]3
2
F（sd1 ） F（sd8 ）

1
20
F（sd
9 ）F （sd32 ）Fig.4. Revocation in B1
45

Generic Transformation for Scalable Broadcast Encryption Schemesgroup session key. Formally, we show that B1 scheme is resil-storage overhead also becomes, rather than O(log n), closer toient to collusion of any set of revoked users by using the follow-

O(log2 n), which is relatively heavy and so undesirable in mem-ing lemma and the similar idea in [16]. In the lemma we as-

ory-constrained environments.

sume that F and F'

are pseudo random permutations in thesense that no probabilistic polynomial-time adversary can distin-

4.2

guish the output of F (and F'

Schemes) on a randomly selected input

Transmission-Efficient

Broadcast

Encryption

from a truly random string of similar length with non-negligible

In this section, to construct a scalable transmission-efficient BE

probability.

schemes, we further apply our compiler to a previously known
transmission-efficient BE scheme, but inefficient in computa-

Lemma 2. The above key assignment satisfies the key-indistinguishability condition [16] under the pseudo-randomness of giv-tion cost and user storage size for a huge number of users.
Recently, Jho et al. [14] have presented BE schemes
where the number of transmission messages is less than theen functions F and F' .

number of revoked users r, i.e., 1k ・ r for a predetermined conWe can prove the lemma by using a hybrid argument on

stant k. To bring the number of transmission messages down,

the length of oneway chains, i.e., showing that the gap between

they used a fine strategy to cover several subsets of privilegedtrue randomness and pseudorandomness is negligible.

users by using only one key. Their basic scheme requires O(nk)user storage overhead and O(n) computation overhead. To re-

EFFICIENCY. In the presented scheme, at most two ciphertexts ofduce storage and computation overhead further, they presented

a group session key per revoked user are generated. Hence theinterval or partition-based construction to deal with relatively

number of total ciphertexts consisting of a header Hdr is at

small number of users. Unfortunately, in their methods, usermost 2・r for r revoked users. But computation overhead is pro-storage overhead is still heavy or initial transmission length isportional to n.

relatively large.

When we apply the compiler to B1 scheme, in the result-

By applying our compiler to their schemes, we construct a

ing scheme B1, the compiled BE scheme B1 satisfies O(log n)scalable BE scheme B2, which has 12 ・r transmission messages

key restriction since user keys storage in the original BE(except only for a small number of revoked users) with a reason-

scheme B1 is 1 + log2 n. However, we can show that user stor-

able user storage and computation overhead. As the underlying

age overhead does not change, i.e., 1 + log2 n since one private

schemes for our compiler, we apply two different BE schemes

node key assigned to the parent node of a given node can be de-in [14] at different depth of a w-ary tree. One is the BE scheme

1sleted and so 1 − s + s・(log2 n +1) = 1 + log2 n.

using simple one-way ring where the number of transmission

1smessages is r. This scheme is applied to every sibling set not in

Computation overhead is reduced to O(n ) for s=logw n.
log2(log2 n)

2n
and s= loglog
then we2(log2 n)

the bottom level. The other is the BE scheme based on a so-

also reduce O(n ) computation overhead to O(log n). However

called HOC(2,[m,2]), which is a combination of HOC(2:m)

If we choose the variables w=nlog2 n1stransmission overhead slightly increases by at most a factor of swith simple hierarchical ring with depth 2 and OFBE(m:2) us-

from 2r. More precisely, transmission overhead is described bying 1-jump one-way chain. HOC(2,[m,2]) has

the recursive formula in Session 3.2 since B1 satisfies the Sub-sion ciphertexts and relatively low user storage compared to

set-Cover framework.

that of the one-way chain-based scheme. This scheme is ap-

1
2 r +1 transmis-

plied to every sibling set in the bottom level, i.e., sibling set conREMARK. Based on a similar approach using one-way chains,

sisting of leaves in the tree. The efficiency for B2 is as shown

Goodrich et al. [9] presented the SSD (stratified subset differ-in Table 1.

ence) scheme for low-memory devices. But, unlike the work in

We note that, for w(=n1/s)=100, n(s−1)/s is less than 1% of[9], our method does not use a tree structure. This eliminates

n. The compiled scheme B2 provides similar (or less) transmis-

the cost for traversing internal nodes in the tree, which causes

sion overhead, compared to the schemes in [14] while gains rea-increase in computation overhead. In addition, with respect tosonably low user storage and computation overhead. For com-efficiency, the SSD scheme achieves O(log n), more precisely

parison between the schemes, refer to Session 5.

2d log2 n, user storage overhead and O(r) transmission over1dhead, but O(n ) computation overhead where d is a predeter-

such as BE schemes based on a secret sharing [3,15], one-way

mined constant. When O(log n) computation restriction is strict-accmulators [2], or complicated operations etc., gives scalable

ly required, the constant d should be as large as
46

Similarly applying our compiler to other BE schemes

log2 nlog2(log2 n)

and usertransformations of these BE schemes under different security as-

NAIS Journal

acceptable in many applications.

Table 1. Efficiency of B2

In particular, B1 satisfies log-key restriction strictly, andTO B2（r,n）

SO B2（n）

CO B2（n）

suitable to lowmemory applications where the memory is less 1
Kbyte such as a smart card. This allows a message sender to revoke any r users with transmission overhead being similar tos-1< 12 r+n sB2（s-1）n1/s（n1/s ）2-2n1/s+24
+
8

1
s

-s

O（n ）

that of the SD scheme [16].
In Table 2.

in the first column means upper-boundof the number of transmission ciphertexts of a group session
sumptions in information theoretical or computational aspects.

key. Since the original BE schemes B1 and B2 are defined in
Subset-Cover framework transmission overheads in the com-

5 Efficiency Comparison Between Proposed Schemes

piled schemes B1 and B2 are described by the recursive formu-

In this section we compare the effciency between our compiled

la in Section 3.2. More concretely, if 10−4n

BE schemes with SD [16], LSD [13], SSD [9], (1,100)-π1 [14]TOB1(r, n)schemes. In the following we assume that the size of a key isr

4r+10−4n and TOB2(r, n)10−4 n then TO B1 (r, n)r

10−2n thenr+10−4n. Else 10−6n6r+10−4 n and TO B2 (r, n)−4n.

1.5r+10128 bits, which is considered reasonably secure currently. The
number of computations means the number of basic operations

6 Conclusionneeded to compute a key encrypting a group session key.
For a specific example, we consider the case of n=108

We have presented a modular method transforming broadcast

users and w=100. As we show in Figure 5, the number of trans-

encryption schemes, which are impractical due to computation

mission ciphertexts of B2 is similar to that of the SD scheme atcomplexity or user keys storage for huge number of users, toinitial interval where the number r of revoked users is smaller

scalable ones. As concrete examples, we have presented somethan 0.75% of the total users. But, except this interval, the num-compiled instances: The first is a BE scheme achieving O(logber of transmission messages of B2 becomes, at worst case,n) user storage, O(log n) computation overhead, and O( log log n・

about 1/4 of the number of transmission messages of the SDr) transmission overhead at the same time. The second is a trans-

scheme. The number of keys stored by a user in B2 is about 4

mission-efficient BE scheme with a reasonably low user stor-

times as many as that of the SD scheme. But this difference isage and computation overhead.

log n

Mbyte

Kbyte
LSD

SSD

B1

250.0

24

B2

SD
125.0

SD

6

SSD
LSD

4

B2

62.5

2

31.2
0.5%

2.0%

4.0%

6.0%

B1
2*107

8.0%
r/N*100%

Transmission Overhead

4*107

6*107

8*107

8

1*10
number of user

Storage Overhead

Fig.5. Transmission and storage overhead for n=10 8 for the worst case
Table 2. Comparison between B1, B2, SD[16], LSD[13], and SSD[9] for n=10 8
SchemeSD［16］

Transmission Overhead＜＿ 2r-1

User Storage Overhead

Computation Overhead368（ 5.74Kbyte）

27

LSD［13］＜＿ 4r

143（ 2.24Kbyte）

27

SSD［9］＜＿ 2sr（ s=4）213（ 3.33Kbyte）

100

（1，
100）-π［14］1＜＿ 2r＋0.01n＜＿ 2r＋0.01n5274（ 82.4Kbyte）

100

B1

27（ 0.442Kbyte）

100

B2

＜
＿ 0.5r+0.01n1528（ 23.875Kbyte）

100

47

Generic Transformation for Scalable Broadcast Encryption Schemes

For all schemes based on the Subset-Cover framework,
our compiler provides a traitor tracing method by using a similar method in [16]. Further study would be a method to applyω−r< ωs−1γ, (r mod ωs−1)TOB(1 + r−
ωs−1 ,ω)s−1rω
+ (ωs−1−(r mod ωs−1))TOB( −ωs−1 ,ω)ωs−1γ r < n, n− r
s 1

ωs−1

(8)
(9)

our modular approach to other traitor tracing methods.
Acknowledgments
The authors would like to thank the anonymous reviewers ofThis research was supported by the MIC(Ministry of Information andCommunication), Korea, under the ITRC(Information Technology Research Center) support program supervised by the IITA(Institute of Information Technology Assessment).

CRYPTO 2005 for giving helpful comments.
A Analysis of Transmission Efficiency of Our Compiler
Let ω=n1/s and γ be a number satisfying TOB (γ,ω)=ω−γ. To

Reference

analyze transmission efficiency, we use the following observa-

1. T. Asano,tions: The worst case occurs when revoked users have the least

Receivers , In Advances in Cryptology-Asiacrypt 2002, Spring-number of common ancestors. If there is no revoked user, thenA Revocation Scheme with Minimal Storage at

er-Verlag, LNCS vol. 2501, pp.433-450, 2002.

GC uses an initial group session key to cover all users and2. N. Attrapadung, K. Kobara and H. Imai,hence there is no transmission messages (ciphertext of thetion with Short Keys and Transmissions , ACM Workshop On

group session key). If r = 1, we obtain the formula (1) since

Digital Rights Management 2003, pp.55-66, 2003.

there is one revoked node in each level and so total s siblingsets to be covered, and TOB (1, ω) transmission messages foreach sibling set are required. If 2

r < ω, then there is r re-voked nodes in each level and total r(s − 1) sibling sets should

3. J. Anzai, N. Matsuzaki and T. Matsumoto,

Broadcast Encryp-

Quick Group Key

Distribution Scheme with Entity Revocation , In Advances in
Cryptology-Asiacrypt 1999, Springer-Verlag, LNCS vol. 1716,
pp.333-347, 1999.

be covered. In this case, if γ< r, then ω− r transmission messages are transmitted for the first level. Therefore, we obtain theformula (2) and (3) for 2

r < ω. If ω

4. M. Bellare, A. Desai, E.Jokipii and P. Rogaway,

A Concrete

Security Treatment of Symmetric Encryption: Analysis of ther < ωγ, then we do

DES Modes of Operation , In Proceedings of the 38th Annual

not need to consider nodes in the first level since all nodes in

Symposium on Foundations of Computer Science - FOCS'97,

the first level are revoked. In level 2, (r mod ω) sibling setsω
have 1+ r−
ω revoked nodes and ω−(r mod ω) sibling setsω
have r−ω revoked node. In level j (3 j s), r(s − 2) messages should be transmitted to cover r(s−2) sibling sets since

pp.394-403, 1997.

Available from http://eprint.iacr.org 2005. To appear in CRYP-

one revoked node exists in r sibling sets in level j (1TO 2005.

js−2). Hence we obtain the formula (4).
Now we can easily generalize the formula (3) and (4) tothe formula (5) and (6), and again the formula (5) and (6) to get

5. D. Boneh, C. Gentry and B. Waters,

Collusion Resistant

Broadcast Encryption With Short Ciphertexts and Private Keys ,6. D. Boneh and A. Silverberg,

Applications of Multilinear

Forms to Cryptography , Available from http://eprint.iacr.org
2002.

the formula (7), (8), (9) inductively.
2

r = 1, sTOB(1, ω)(1)r < γ, r(s − 1)TOB(1, ω) + TOB(r, ω)(2)

γ r < ω, r(s − 1)TOB(1, ω) + (ω− r)

ωi−1γ
ωi

8. A. Fiat and M. Naor,

(4)
(5)

i
ω)
+ (r mod ω)TOB(1 + r−ω
ωi ,
i
ω)
+ (ωi−(r mod ωi))TOB( r−ωωi ,r < ωs−1,rTOB(1, ω) + (ωs−1 − r)

Efficient Tree-

Based Revocation in Groups of Low-State Devices , In Advan3152, pp.511-527, 2004.

(6)

...

...

pp.480-491, 1994.

ces in Cryptology-CRYPTO 2004, Springer-Verlag, LNCS vol.

i

48

Broadcast Encryption , In Advancesin Cryptology-CRYPTO 1994, Springer-Verlag, LNCS vol. 773,

i , r(s − i − 1)TO (1, ω)
r < ωγBωs−2γ

pp.391-437, 2000.

9. M. T. Goodrich, J. Z. Sun, and R. Tamassia,r < ωi, r(s − i)TOB(1, ω) + (ωi − r)Nonmalleable

Cryptography , SIAM Journal on Discrete Mathematics, 30(2),

(3)

...

...

ω r < ωγ, r(s − 2)TOB(1, ω) + (r mod ω) TOB(1 +r−ω ω)+ (ω− (r mod ω))TO
B
ω ,
ω ω)
( r−
,
ω

7. D. Dolev, C. Dwork, M. Naor, and B. Pinkas,

10. J. A. Garay, J. Staddon, and A. Wool,

Long-Lived Broad-

cast Encryption , In Advances in Cryptology-CRYPTO 2000,(7)

Springer-Verlag, LNCS vol. 1880, pp.333-352, 2000.

NAIS Journal

11. E. Gafni, J. Staddon, and Y. L. Yin,

Efficient Methods for Inte-grating Traceability and Broadcast Encryption , In Advances in
Cryptology-CRYPTO 1999, Springer-Verlag, LNCS vol. 1666,
pp.372-387, 1999.
12. J. Horwitz,

A Survey of Broadcast Encryption , Manuscript,

2003.
13. D. Halevy and A. Shamir,

The LSD Broadcast Encryption

Scheme , In Advances in Cryptology-CRYPTO 2002, Springer-Verlag, LNCS vol. 2442, pp.41-60, 2002.
14. N.-S. Jho, J. Y. Hwang, J. H. Cheon, M. Kim, D. H. Lee and E.
S. Yoo,One-way Chain Based Broadcast Encryption Scheme ,In Advances in Cryptology-Eurocrypt 2005, Springer, LNCS vol.
3494, pp.559-574, 2005.
15. M. Naor and B. Pinkas,

Efficient Trace and Revoke Sche-me , Financial Cryptography FC 2000, Springer-Verlag, LNCS vol.
1962, pp.1-20, 2000.
16. D. Naor, M. Naor, and J. Lotspiech,

Revocation and Tracing

Schemes for Stateless Receivers , In Advances in CryptologyCRYPTO 2001, Springer-Verlag, LNCS vol. 2139, pp.41-62, 2001.
17. D. R. Stinson and T. V. Trung,

Some New Results on Key Dis-

tribution Patterns and Broadcast Encryption , Designs, Codes andCryptography, vol. 14, no. 3, pp.261-279, 1998.
18. D. R. Stinson and R. Wei,

Combinatorial Properties and Con-

structions of Traceability Schemes and Frameproof Codes , SIAM
Journal on Discrete Mathematics, vol. 11, no. 1, pp.41-53, 1998.
19. D. M. Wallner, E. G. Harder, and R. C. Agee,

Key Agreementfor Multicast : Issues and Architecture , In internet draft draft-waller-key-arch-01.txt, Sep, 1998.
20. C. K. Wong and S. S. Lam,

Digital Signatures for Flows andMulticasts , IEEE/ACM Transactions on Networking, vol. 7, no. 4:
pp. 502-513, 1999.

49