[KSW08] Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products

Authors: Jonathan Katz, Amit Sahai, Brent Waters | Venue: Eurocrypt 2008 | Source

Abstract

Predicate encryption is a new paradigm for public-key encryption that generalizes identity-based and attribute-based encryption. In a predicate encryption scheme, secret keys correspond to predicates and ciphertexts are associated with attributes; a secret key $S{K}_f$ corresponding to predicate $f$ can decrypt a ciphertext associated with attribute $x$ if and only if $f(x)=1$. We present the first predicate encryption scheme supporting inner-product predicates: a key for a vector $\mathbf{v}$ decrypts a ciphertext for a vector $\mathbf{x}$ if and only if $⟨\mathbf{v},\mathbf{x}⟩=0$. Our scheme achieves full attribute-hiding security — ciphertexts reveal neither the payload nor the attribute vector. We also demonstrate that inner-product predicates are surprisingly expressive: they suffice for supporting disjunctions, polynomial equations, CNF/DNF formulas, and general polynomial evaluation. The scheme is proved secure in the standard model under the decisional linear assumption over bilinear groups.

BibTeX

Copy

@Inproceedings{EC:KatSahWat08,
  author = {Jonathan Katz and Amit Sahai and Brent Waters},
  title = {Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products},
  pages = {146--162},
  editor = {Nigel P. Smart},
  booktitle = {Advances in Cryptology -- {EUROCRYPT}~2008},
  volume = {4965},
  series = {Lecture Notes in Computer Science},
  address = {Istanbul, Turkey},
  month = {apr~13--17},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2008},
  doi = {10.1007/978-3-540-78967-3_9},
}