How are Predicate Encryption algorithms implemented?

Question

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.

Thanks!

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:

• PBC and jPBC
• Charm