Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products
Predicate encryption is a new paradigm generalizing, among other things, identity-based encryption. In a predicate encryption scheme, secret keys correspond to predicates and ciphertexts are associated with attributes; the secret key SK f corresponding to
- PDF / 287,944 Bytes
- 17 Pages / 430 x 660 pts Page_size
- 54 Downloads / 279 Views
University of Maryland [email protected] 2 UCLA [email protected] 3 SRI International [email protected]
Abstract. Predicate encryption is a new paradigm generalizing, among other things, identity-based encryption. In a predicate encryption scheme, secret keys correspond to predicates and ciphertexts are associated with attributes; the secret key SKf 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 for relatively few classes of predicates. We construct such a scheme for predicates corresponding to the evaluation of inner products over ZN (for some large integer N ). This, in turn, enables constructions in which predicates correspond to the evaluation of disjunctions, polynomials, CNF/DNF formulae, or threshold predicates (among others). 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.
1
Introduction
Traditional public-key encryption is rather coarse-grained: a sender encrypts a message M with respect to a given public key P K, and only the owner of the (unique) secret key associated with P K can decrypt the resulting ciphertext and recover the message. These straightforward semantics suffice for point-to-point communication, where encrypted data is intended for one particular user who is known to the sender in advance. In other settings, however, the sender may
Research supported in part by NSF CAREER award #0447075 and the U.S. Army Research Laboratory. Supported in part by the NSF ITR and CyberTrust programs (including grants 0627781, 0456717, 0716389, and 0205594), a subgrant from SRI as part of the Army Cyber-TA program, an equipment grant from Intel, an Okawa Research Award, and an Alfred P. Sloan Foundation Research Fellowship. Supported by NSF CNS-0524252, CNS-0716199; the US Army Research Office under the CyberTA Grant No. W911NF-06-1-0316; and the U.S. Department of Homeland Security under Grant Award Number 2006-CS-001-000001.
N. Smart (Ed.): EUROCRYPT 2008, LNCS 4965, pp. 146–162, 2008. c International Association for Cryptologic Research 2008
Predicate Encryption Supporting Disjunctions
147
instead want to define some complex policy determining who is allowed to recover the encrypted data. For example, classified data might be associated with certain keywords; this data should be accessible to users who are allowed to read all classified information, as well as to users allowed to read information associated with the particular keywords in question. Or, in a health care application, a patient’s records should perhaps be accessible only to a physician who has treated the patient in the past. Applications such as those sketched above require new cryptographic mechanisms that provide more fine-grained control over access to encrypted data. Predicate encryption offers one such tool. At a high level (formal definitions are given in Section 2), secret keys i
Data Loading...
