Paper 2017/233

Simplifying Design and Analysis of Complex Predicate Encryption Schemes

Shashank Agrawal and Melissa Chase


Wee (TCC'14) and Attrapadung (Eurocrypt'14) introduced predicate and pair encodings, respectively, as a simple way to construct and analyze attribute-based encryption schemes, or more generally predicate encryption. However, many schemes do not satisfy the simple information theoretic property proposed in those works, and thus require much more complicated analysis. In this paper, we propose a new simple property for pair encodings called symbolic security. Proofs that pair encodings satisfy this property are concise and easy to verify. We show that this property is inherently tied to the security of predicate encryption schemes by arguing that any scheme which is not trivially broken must satisfy it. Then we use this property to discuss several ways to convert between pair encodings to obtain encryption schemes with different properties like small ciphertexts or keys. Finally, we show that any pair encoding satisfying our new property can be used to construct a fully secure predicate encryption scheme. The resulting schemes are secure under a new q-type assumption which we show follows from several of the assumptions used to construct such schemes in previous work.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
predicate encryptionattribute-based encryptionbilinear maps
Contact author(s)
shashank agraval @ gmail com
2017-03-08: received
Short URL
Creative Commons Attribution


      author = {Shashank Agrawal and Melissa Chase},
      title = {Simplifying Design and Analysis of Complex Predicate Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2017/233},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.