My question is about Key-Policy ABE (KP-ABE). What does it mean when a "Ciphertext is Labeled with set of attribute"? How is it labeled?

  • 2
    $\begingroup$ Maybe you could mention where you are reading this? $\endgroup$
    – K.G.
    Dec 12, 2015 at 20:52

1 Answer 1


The first Attribute-based Encryption scheme was introduced by Sahai and Waters in 2005: Fuzzy Identity-Based Encryption. It worked by associating a set of attributes with both the ciphertext and the private key of the user.

Take for example the ciphertext which is encrypted with the attribute set $\{A, B, C\}$ and the private key of some user with the attribute set $\{B, C, D\}$. If the system threshold $d$ is chosen as 2 then the user would be able to decrypt the ciphertext with because the cut set of the ciphertext attribute set and the private key attribute set is of size 2 which is greater or equal to the global threshold $d$.

This is of course not very useful, because this only achieves cryptographic access control based on set overlap. One generally wants to use more complicated policies which are more expressive than simple sets. Such expressive policies where later achieved by Goyal et al. in 2006: Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data (KP-ABE).

Instead of using two sets, the private key of the user is generated (associated) from a boolean formula (policy) of attributes and the ciphertext is encrypted with an attribute set. For example, the ciphertext may have been encrypted with the set $\{A, B\}$. Now we have two users with private keys from two different policies. $$SK_1=\text{Keygen}(MSK, ``A\ \text{and}\ (B\ \text{or}\ C)")$$ and $$SK_2=\text{Keygen}(MSK, ``A\ \text{and}\ (C\ \text{or}\ D)").$$

You should see that the user who possesses $SK_1$ can easily decrypt the ciphertext, because ciphertext was encrypted with $B$, the clauses $B\ \text{or}\ C$ is fulfilled as well as the $A$. Since both clauses are fulfilled, the $\texttt{and}$-gate is also fulfilled. This means that the attribute set satisfies the policy in the private key and $SK_1$ can decrypt the ciphertext.

The user who possesses $SK_2$ cannot decrypt the same ciphertext, because the necessary clause $C\ \text{or}\ D$ is not fulfilled by the attributes present in the ciphertext. Therefore the $\texttt{and}$-gate cannot be fulfilled and $SK_2$ cannot decrypt the ciphertext.

There is also CP-ABE by Bethencourt where the roles are reversed, because a policy is used to encrypt the ciphertext and private keys are generated from attribute sets.

  • $\begingroup$ I understand how with the threshold policy a Secret Sharing Scheme can be used to generate a secret key to decrypt the ciphertext, but how does this work in the KP-ABE example? If you use {A,B} to create the ciphertext, how can a SK1 "A and (B or C)" and SK3 "A and (B or E)" both decrypt the cipher text, since the secret key must be different right? $\endgroup$ May 29, 2017 at 10:04
  • 1
    $\begingroup$ @user1226868 Sorry, I've never looked at KP-ABE schemes in detail (because I still don't understand the use case perfectly), but they use a tree in the same way: inputting the attributes at the leaves and working their way up the tree to get the secret. $\endgroup$
    – Artjom B.
    May 29, 2017 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.