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.


  • 1
    $\begingroup$ It depends on the schemes. What scheme do you consider? Or, do you want a pointer to concrete schemes? $\endgroup$
    – xagawa
    Jun 29, 2013 at 9:18
  • $\begingroup$ i want a simple scheme, and a practical explanation for its implementation. I would really apreciate your help $\endgroup$ Jun 29, 2013 at 10:25

1 Answer 1


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:


Your Answer

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

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