1. Field of the Invention
The present invention relates to broadcast encryption, and more specifically to implementing efficient broadcast encryption schemes with configurable tradeoffs among pre-broadcast transmission bandwidth, key storage cost, and key derivation cost.
2. Description of the Related Art
Broadcast encryption schemes allow a center to transmit encrypted data over a broadcast channel to a large number of users such that only privileged users, a select subset P of the users, can decrypt it. Traditional applications include Pay TV, content protection on CD/DVD/flash memory, secure Internet multicast of privileged content such as video, music, stock quotes, news stories, and the like. However, broadcast encryption schemes can be used in any setting that might require selective disclosure of potentially lucrative content.
Broadcast encryption schemes typically involve a series of pre-broadcast transmissions, at the end of which the users in P can decrypt a broadcast session key bk. The remainder of the broadcast is then encrypted using bk.
In terms of efficiency, the most important parameters of the broadcast encryption schemes are: 1) the number of pre-broadcast transmissions t made by the center; 2) the maximum amount of keying material k a user must persistently store; and 3) the maximum amount of computation c the user must perform to decrypt the broadcast session key bk from the pre-broadcast transmissions. In a system of n users, r of which are to be revoked, a broadcast encryption scheme must find a favorable balance among the parameters t, k, and c.
One variant of the broadcast encryption problem, for which finding an efficient solution has been difficult, is the so-called “stateless receiver” case. This variation includes the following requirements:
1. Each user in the privileged set P can decrypt the broadcast by himself.
2. No coalition of users outside the privileged set P can decrypt the broadcast.
3. Consecutive broadcasts may address unrelated privileged sets.
4. A user need not update its keys if other users leave or join the privileged set.
5. A user's keys are unaffected by its viewing history.
In this case, users are provided with some initial key or set of keys, and can only use this keying material when decrypting future broadcasts. Stateless receivers can store only the keys given at the initial stage such as manufacturing time. As a result, every broadcast message must contain enough information to enable non-revoked receivers to obtain the current session key using their initial receiver keys. The above definition can also be extended to allow some threshold of free riders, i.e. users outside of the privileged sets who might be able to decrypt the broadcast.
The stateless model is preferable since it does not involve any type of key update procedure, which is not only costly but also introduces additional points of failure. Since keys are not updated in the stateless model, they can be embedded in non-volatile tamper-resistant storage. This enhanced security reduces the possibility of piracy in broadcast settings.
The problem of stateless receiver broadcast encryption, a practical trade-off among pre-broadcast transmissions t, user key storage k, and user decryption computation c, is well-known in the literature. However, previously proposed solutions are all inefficient with respect to at least one of the parameters. Essentially, these proposals belong to one of three categories: 1) schemes using error-correcting codes, 2) schemes using key trees, and 3) schemes using RSA.
The schemes using error-correcting codes require the number of revoked user r be specified in advance, and one or more of the parameters t, k and c be at least linear with r. However, the number of revoked users r changes from time to time in practice. The key-tree-based stateless receiver broadcast encryption scheme needs to store log n (or more) keys in limited devices, such as tamper-resistant smart cards. The user key storage k is very high.
The RSA public-key encryption scheme was proposed in R. L. Rivest, A. Shamir and L. Adleman (RSA), A Method for Obtaining Digital Signatures and Public—Key Cryptosystems—Comm. Of the ACM (1978), vol. 21, 120-126. According to the RSA scheme, a keyholder chooses two large prime numbers p and q, and two exponents e and d such that ed≡1(mod Φ(n)), where Φ(n)=LCM(p−1)(q−1). The scheme publishes e and the product n=pq, but keeps d, p and q secret. To encrypt a message mε Z/nZ, a sender computes me (modn) and transmits this number to the keyholder. To decrypt, the keyholder computes m≡(me)d(modn). Over the past 27 years, numerous cryptographic inventions have used ideas related to RSA that were not envisioned by the inventors of RSA. The RSA encryption scheme does not, in itself, address the problem of broadcast encryption.
In S. G. Akl and P. D. Taylor, Cryptographic Solution to a Multilevel Security Problem—Crypto '82, Plenum Press (1982), 433-450, Akl and Taylor used techniques related to RSA to handle access control. In Akl-Taylor, each user is a member of one or more security classes. For any fixed set of security classes, each user in their scheme obtains a single “master key” that enables it to gain access to any security class of which it is a member. These security classes form a partially-ordered set (poset) under the inclusion relation. This poset can be modeled as a directed acyclic graph (DAG). Akl-Taylor uses RSA to generate a set of immiscible keys tailored for a given DAG. Nonmembers of a security class cannot collude to gain access to the security class. The center generates an RSA modulus n=pq and fixes some m∈(Z/nZ)*. Keys have the form ki=m1/ei(modn) for publicly known ei. An important property of RSA is that, given e, it is computationally easy to compute me (mod n) for any m, but it is computationally hard to compute m1/e (mod n), i.e., it is easy to compute eth powers but hard to compute eth roots. Thus, ki→kj if ej divides ei. In other words, if ej divides ei, keys kj can be computed from keys ki. More generally,{ki1, . . . kiz}→kj, if and only if ej divides LCM (ei1, . . . eiz)  (1)
Thus, key derivability is completely dictated by the factorization of the ei's. In Akl-Taylor, each vertex vi in the DAG is associated with a distinct prime pi, and ei=Πvi→vj Pj. The keys are immiscible, and nonmembers of a security class cannot collude to gain access. However, the cost of computing kj from ki in Akl-Taylor is very high. In addition, the Akl-Taylor scheme does not address the problem of broadcast encryption, where the privileged subsets may change from one broadcast to another.
In T. Asano, A Revocation Scheme with Minimal Storage at Receivers—Asiacrypt '02, Lecture Notes in Computer Science 2501 (2002), Springer-Verlag, 433-450, Asano proposes a stateless receiver broadcast encryption scheme in which each user only needs to store a single key. According to the Asano scheme, users are positioned as leaves in a hierarchical tree such that each node in the tree (other than the root) has a-1 siblings, wherein a denotes the branching factor. Each user is allowed to derive (2a−1−1)logan+1 subset keys, where each subset contains an ancestor of the user's leaf, together with some number (but not all) of the ancestor's siblings. These subsets form a poset under the inclusion relation, and key derivability can be modeled by a DAG. A privileged user can use its key to derive secondary keys, one of which is used to recover the broadcast session key bk and then the broadcast. The Asano scheme uses techniques related to the RSA encryption scheme to dictate which keys can be derived from other keys. However, the derivability graph that the Asano scheme uses is highly non-optimal. Fixing the number of transmissions to be t=O(r loga(n/r)), the user's computational requirement becomes c=O(2a loga n), which quickly becomes huge as a increases. Thus, although the Asano scheme has the advantage of requiring a user to store only one key, and of being able to trade off the number of pre-broadcast transmission for user decryption computation, the computation increases at an unacceptable rate as the transmission decreases.
In M. Luby and J. Staddon, Combinatorial Bounds for Broadcast Encryption—Eurocrypt '98, Lecture Notes in Computer Science 1403 (1998), Springer-Verlag, 512-526, Luby and Staddon considered a variant of unconditionally secure one-time broadcast encryption schemes (OTBESs). In this model, each user u is given some set K′u of keys. The Luby-Staddon scheme proves a combinatorial bound relating maxu|K′u| and the number of pre-broadcast transmissions t—namely,
                                          max            u                    ⁢                                                K              u              ′                                                  ≥                              (                                                                                (                                                                                            n                                                                                                                      r                                                                                      )                                                        1                    /                    t                                                  t                            -              1                        )                    /          r                                    (        2        )            
where n is the total number of users, and r is the number of users that are not entitled to the broadcast. However, there is no derivability among the keys, and keys are used only once (as a one-time pad).
Accordingly, there has been a need for a broadcast encryption scheme with an acceptable and configurable tradeoff among t, k and c.