Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products

• Published in: Journal of cryptology 2013-04, Vol.26 (2), p.191-224
• Main Authors: Katz, Jonathan, Sahai, Amit, Waters, Brent
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Coding and Information Theory; Combinatorics; Communications Engineering; Computational Mathematics and Numerical Analysis; Computer Science; Cryptography; Encryption; Exact sciences and technology; Information, signal and communications theory; Networks; Polynomials; Probability Theory and Stochastic Processes; Signal and communications theory; Telecommunications and information theory
• ISSN: 0933-2790; 1432-1378
• DOI: 10.1007/s00145-012-9119-4

Predicate encryption is a new paradigm for public-key encryption that generalizes identity-based encryption and more. In predicate encryption, secret keys correspond to predicates and ciphertexts are associated with attributes ; the secret key SK f corresponding to a predicate f can be used to decrypt a ciphertext associated with attribute I if and only if f ( I )=1. Constructions of such schemes are currently known only for certain classes of predicates. We construct a scheme for predicates corresponding to the evaluation of inner products over ℤ N (for some large integer  N ). This, in turn, enables constructions in which predicates correspond to the evaluation of disjunctions, polynomials, CNF/DNF formulas, thresholds, and more. Besides serving as a significant step forward in the theory of predicate encryption, our results lead to a number of applications that are interesting in their own right.