Broadcast encryption

From CryptoWiki
Revision as of 02:28, 22 November 2015 by 15-02-SaltanovaMV (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Broadcast encryption is a type of encryption scheme in which encrypted data is transmitted on the broadcast channel in such a way that only а privileged receivers could decrypt it.


Statement of problem

One way to arrange the secure transmission of information is achived through the use of public-key cryptography. For this system to work, communicating devices must know about each other and agree on encryption keys before transmission. In 1994 Amos Fiat and Moni Naor set a problem to prove that two devices, previously unknown to each other, can agree on a common key for secure communications over a one-way communication path. They were the first to pioneer the research in broadcast encryption. Broadcast encryption seeks to solve the problem of two devices, previously unknown to each other, agreeing upon a common key. This can allow for new devices, even if they did not exist when the encrypted data was made, to be added to a group of acceptable devices. Since the same data is being sent to all devices, instead of a separately encrypted message for each, broadcast encryption must also ensure that only those devices in the privileged group will be able to decode the message.

General scheme of a broadcast encryption

A true broadcast encryption scheme is one in which the same message is broadcast to all users, and those users in the privileged group recover the message while all others derive nonsense or nothing at all. The original broadcast encryption scheme designed by Fiat and Naor proposed the following scenario.

There exists a key distribution center and a group of users. There is a subgroup of privileged users among the receivers, which can be fixed, slowly changing, or rapidly changing. The center allocates predefined keys for all of the users. The center later wants to transmit to a privileged subset of users. For this to occur, this subset of users must recover a common key while not allowing any other users who are able to receive the transmission to recover this key. [F94]

Broadcast encryption schemes are based on a key management block. This is a block of data located at the beginning of a broadcast message or prerecorded onto some type of blank media, most often a smart card. From this key management block, each recipient can derive the management key. Users, who are not in the privileged group, even with access to the encoded data will derive the wrong answer from the key management block. Users can attempt to process the key management block but they will not yield the correct key.

Simple Broadcast Encryption Scheme

Resilient broadcast encryption scheme

A broadcast scheme is called resilient to a set S if for every subset T that does not intersect with S, no eavesdropper, that has all secrets associated with members of S, can obtain “knowledge” of the secret common to T. [G09] Here knowledge can have two different interpretations:

The secret common to T has some a-priori distribution (usually the uniform distribution) and given the keys of S and the message transmitted by the center the conditional distribution of the secret is not changed. This is the “information-theoretic” definition of security;

The secret of T is pseudo-random, i.e. no computationally bounded (by probabilistic polynomial time) eavesdropper can distinguish between the secret and a truly random string; even if the eavesdropper is provided with the keys of the coalition S the secret of T remains pseudorandom. This is the computational definition of security.

K-resilient broadcast encryption scheme

A scheme is called -resilient if it is resilient to any set SU of size k.

The original scheme designed by Fiat and Naor required that every user in the broadcast group store ШШ3.png keys and that the broadcast center transmit ШШ4.png messages. This scheme guaranteed that any coalition of k users could not acquire any information about the keys or the broadcast message and is called a k-resilient scheme.

Theorem: There exists a k-resilient scheme that requires each user to store ШШ13.png keys and the center need not broadcast any message in order to generate a common key to the privileged class.

Another example of k-resilient broadcast encryption scheme is a Zero Message schemes. This type of scheme does not require the center to broadcast any message in order for the member of the privileged group to generate a common key. It could be computed from information the user receives from the center, called the management key block, and from other users in the set.

This is a general scheme of a Zero Message broadcast encryption. For every set ШШ5.png, ШШ6.png, define a key ШШ7.png and give it to every user ШШ8.png. The common key to the privileged set T is simply the exclusive or of all keys ШШ6.png, ШШ9.png. Clearly, every coalition of ШШ10.png users will all be missing key ШШ11.png and will therefore be unable to compute the common key for any privileged set T such that ШШ12.png is empty.

Broadcast Encryption versus Public-Key Cryptography

Broadcast encryption and public-key cryptography differ in several ways. The main difference is in the allocation of keys. As mentioned before, in broadcast encryption, devices are given a set of keys and the master server contains a key management block. Future devices can easily be added and be allowed into the privileged group. None of the devices needs to know about each other; all they know is that each belongs to the privileged group. Public-key cryptography, on the other hand, is based on prior knowledge of participating devices. Senders use their own private key to encode messages, and recipients use a public key to decode messages. Since these keys must be known before messages can be exchanged, each device must know about every other device, meaning it must know and store the keys of other devices, it wants to communicate with. [D08] [S07]

A disadvantage of broadcast encryption is that it cannot provide a nonrefutable signature. In public-key cryptography, forgery of a valid signature is an intractable problem without the actual signer's private key. [AA09] Therefore, the true identity of an individual cannot be guaranteed with broadcast encryption. Broadcast encryption can only guarantee that one participant is in the same group as another; public-key cryptography can guarantee the participant's actual identity.

An advantage of public-key cryptography systems is that they do not require a central authority. With broadcast encryption, a central authority, the broadcast center, must produce and assign key management blocks and assign device keys. In public-key users create their own certificates and exchange them throughout the system. Some public-key systems do use a central authority for key distribution, but it is not a requirement. Public-key systems can use a “web of trust” in which users verify the authenticity of the keys of other users' keys instead of a central authority.


If user A trusts user , and if user B has verified the key of user C, user A can be confident that the person using user C’s key, with whom A is communicating, is actually user C.

This is a simplified example. A real web of trust would involve more people verifying the authenticity of a user's key before another user would safely believe the identity of a previously unknown user.

Advantages of broadcast encryption include increased speed over public-key cryptography and the ability to adapt to attacks on the system. Since broadcast encryption performs simple symmetric operations and public-key cryptography uses exponentiation operations, the processor load on a broadcast encryption system can be up to 1,000 times less than the load to perform a public-key signature calculation.

Broadcast encryption is not applicable in all applications; however, it is especially useful in content protection. [L02]

Practical issues

When broadcast encryption was first designed, the creators primarily saw it as a means to provide conditional access, allowing only privileged users or devices access to a message. An ideal use for this was granting access to premium cable TV channels to paying customers.

This original use for broadcast encryption has turned out to be less important than another application: media protection. Content protection is an important topic since home users now have access to all types of media in digital form. Since the millionth digital copy is just as good as the original, protecting digital content and the rights of its creators is of increasing concern. [H02]

Broadcast encryption is most appropriate for content protection in the home in devices such as prerecorded DVD media and CD media. The Content Scrambling System (CSS) which was widely used in DVDs has already been broken, and it is easy to find programs that can decrypt encoded DVDs. Since the key scheme for CSS is a shared-secret scheme, it cannot be changed dynamically like a broadcast encryption scheme, so the security breach cannot be fixed. This is an example of why broadcast encryption is an important area of research and should be used when appropriate.



Move to bibliography for «Broadcast encryption» article.

Move to article "Broadcast encryption" in Russian.


Saltanova M.V. 2015