Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

After a lot of reading on the internet, i can't seem to figure out how Predicate Encryption works.

As i read, it consists of 4 algorithms:

Setup() - (outputs MSK - Master Secret Key and PK - Public Key)

Encrypt(PK, text) - (outputs CT - ciphertext)

GenKey(MSK, predicate) - (outputs a Token)

Query(Token, CT) - 0 if false, 1 if true

I don't understand how the GenKey algorithm works, how u generate a token based on MSK and predicate, and of course, how you query the ciphertext using the generated token.

Can someone point me in the right direction ? Maybe some pseudo-code or very detailed explanation.


share|improve this question
It depends on the schemes. What scheme do you consider? Or, do you want a pointer to concrete schemes? – xagawa Jun 29 '13 at 9:18
i want a simple scheme, and a practical explanation for its implementation. I would really apreciate your help – Cristi Pufu Jun 29 '13 at 10:25
i guess you forgot.. anyone help? – Cristi Pufu Jul 3 '13 at 11:21
up vote 1 down vote accepted

At first, your syntax (Setup,GenKey,Encrypt,Query) seems to be the syntax of public-key encryption with keyword-search (PKES). In the case of predicate-based encryption, we use Decrypt rather than Query.

The Sahai-Waters Fuzzy IBE

I recommend Sahai and Waters: Fuzzy identity-based encryption (EUROCRYPT 2005) as a first step. I assume you know the basic of pairing-based cryptography and secret sharing.

In Fuzzy IBE, a ciphertext and secret key is associated with attributes sets, $X$ and $Y$, respectively. If $X$ and $Y$ shares at least $t$ elements, one can decrypt the ciphertext $c_X$ using $sk_Y$. The syntax is as follows:

  • $\mathsf{Setup}(1^{\kappa},n,t)$ outputs $msk$ and $pk$, where $\kappa$ is the security parameter, $n$ is the size of universe, and $t$ is a threshold parameter.
  • $\mathsf{GenKey}(msk,Y)$ outputs $sk_Y$, where $Y \subseteq \{1,\dots,n\}$.
  • $\mathsf{Encrypt}(pk,X,m)$ outputs a ciphertxt $c_X$, where $X \subseteq \{1,\dots,n\}$.
  • $\mathsf{Dec}(sk_Y,c_X)$ outputs $m$ if $X$ and $Y$ share at least $t$ elements.

They design the scheme as follows (I omit enc and dec):

  • Setup: the master secret key is $\alpha,t_1,\dots,t_n \in \mathbb{Z}_q$ and the master public key is $e(g,g)^{\alpha}$ and $T_i = g^{t_i}$.
  • GenKey: The master generates shares $s_1,\dots,s_n$ of $\alpha$ by using $(n,t)$ secret sharing scheme, computes $D_i = g^{s_i/t_i}$ for each $i$, and returns $D_i$ for $i \in Y$.

Other schemes

Predicate-based encryption schemes based on the paring groups often employ this structure. Intuitively speaking, they hide/share the master secret into user secret keys as Sahai and Waters did.

If you need examples of implementations, we can find (proof-of-concept) implementations of more complex predicate-based encryption schemes in cryptographic libraries:

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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