Simplifying Design and Analysis of Complex Predicate Encryption Schemes
Shashank Agrawal
Abstract:
Predicate encryption is a natural cryptographic tool for building various types of conditional access systems. It provides a way to encrypt data so that only those key holders who satisfy a certain predicate can decrypt. With time, the class of predicates we can handle with the help of pairing-friendly elliptic curves has grown substantially, from the simple condition of equality (identity-based encryption) to arbitrary Boolean formulae (attribute-based encryption). Along with this, the task of designing and analyzing a predicate encryption scheme has become more and more challenging.
Recently, some powerful abstractions have been introduced to overcome this problem. They save the designer from dealing with elliptic curves, hardness assumptions, sophisticated proof techniques, etc. Instead, she just encodes a predicate into polynomials of a simple form and shows that a certain information-theoretic property about them is true. Unfortunately, for a number of complex predicates, it is not known how to design encodings that satisfy such properties.
In this work, we propose a new *symbolic* property for encodings which completely eliminates the need to deal with any kind of distribution, and leads to fully secure encryption schemes in a generic way. We show that this property is inherently tied to the security of predicate encryption schemes by arguing that any encoding which is not trivially broken must satisfy it. We use this property to discuss several ways to convert between pair encodings to obtain encryption schemes with useful properties like small ciphertexts or keys.
Joint work with Melissa Chase (Microsoft Research). To appear in Eurocrypt 2017.
Bio:
Shashank Agrawal is a Research Scientist at Visa Research. He is interested in cryptography, information security and distributed computing. He has a PhD in computer science from the University of Illinois at Urbana-Champaign. More information can be found at https://shashank-agrawal.com/.