Paper 2011/546

Hidden Vector Encryption Fully Secure Against Unrestricted Queries

Angelo De Caro, Vincenzo Iovino, and Giuseppe Persiano

Abstract

Predicate encryption is an important cryptographic primitive (see \cite{BDOP04,BoWa07,Goyal06,KaSaWa08}) that enables fine-grained control on the decryption keys. Roughly speaking, in a predicate encryption scheme the owner of the master secret key $\text{MSK}$ can derive secret key ${\text{SK}}_P$, for any predicate $P$ from a specified class of predicates $\mathbb{P}$. In encrypting a message $M$, the sender can specify an {\em attribute} vector $\text{x}$ and the resulting ciphertext $\tilde{X}$ can be decrypted only by using keys ${\text{SK}}_P$ such that $P(\text{x})=1$. Our main contribution is the {\em first} construction of a predicate encryption scheme that can be proved {\em fully} secure against {\em unrestricted} queries by probabilistic polynomial-time adversaries under non-interactive constant sized (that is, independent of the length $$ of the attribute vectors) hardness assumptions on bilinear groups of composite order. Specifically, we consider {\em hidden vector encryption} (HVE in short), a notable case of predicate encryption introduced by Boneh and Waters \cite{BoWa07} and further developed in \cite{ShWa08, IoPe08, SLNHJ10}. In a HVE scheme, the ciphertext attributes are vectors $$ of length $$ over alphabet $$, keys are associated with vectors $$ of length $$ over alphabet $$ and we consider the $$ predicate which is true if and only if, for all $$, $$ implies $$. Previous constructions restricted the proof of security to adversaries that could ask only {\em non-matching} queries; that is, for challenge attribute vectors $$ and $$, the adversary could ask only for keys of vectors $$ for which$$ false. Our proof employs the dual system methodology of Waters \cite{Waters09}, that gave one of the first fully secure construction in this area, blended with a careful design of intermediate security games that keep into account the relationship between challenge ciphertexts and key queries.