**Predicate Encryption with Partial Public Keys**

*Carlo Blundo and Vincenzo Iovino and Giuseppe Persiano*

**Abstract: **Predicate encryption is a new powerful cryptographic primitive which allows for fine-grained access control for encrypted data: the owner of the secret key can release partial keys, called tokens, that can decrypt only a specific subset of ciphertexts. More specifically, in a predicate encryption scheme, ciphertexts and tokens have attributes and a token can decrypt a ciphertext if and only if a certain predicate of the two associated attributes holds.
In this paper, ciphertext attributes are vectors $\x$ of fixed length
$\ell$ over an alphabet $\Sigma$ and
token attributes, called patterns, are vectors $\y$
of the same length over the alphabet $\Sigma_\star = \Sigma\cup\{\star\}$.
We consider the predicate $\Match(\x,\y)$ introduced by Boneh and Waters (TCC '07),
which is true if and only if $\x=\langle x_1,\ldots,x_\ell\rangle$ and
$\y=\langle y_1,\ldots,y_\ell\rangle$ agree in all
positions $i$ for which $y_i\ne\star$.
Various security notions are relevant for predicate encryption schemes.
First of all, one wants the ciphertexts to hide its attributes
(this property is called semantic security).
In addition, it makes sense also to consider the property of token security, a security notion in which the token
is required not to reveal any information on the associated pattern.
It is easy to see that predicate privacy is impossible to achieve in a
public-key setting.
In Shi, Shen and Waters, TCC '09, the authors considered the notion of a predicate encryption scheme in the symmetric-key setting and gave the first construction with token security.
In this paper, we consider the notion of a partial public key encryption (as suggested in Shi, Shen and Waters, TCC '09) in which a partial public key allows a user to generate only a subset of the ciphertexts.
We give a construction which is semantically secure and in which a token does not reveal any information on the associated pattern except for the locations of the $\star$'s.
The proofs of security of our construction are based on
hardness assumptions in bilinear groups of prime order;
this greatly improves the efficiency of the construction
when compared to previous constructions Shi, Shen and Waters
which used groups of composite orders.
Our security proofs do not use random oracles.

**Category / Keywords: **pairing-based cryptography, functional encryption

**Publication Info: **CANS 2010

**Date: **received 7 Sep 2010, last revised 14 Apr 2011

**Contact author: **iovino at dia unisa it

**Available format(s): **PDF | BibTeX Citation

**Version: **20110414:085942 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]