Paper 2016/518

Attribute-based Key Exchange with General Policies

Vladimir Kolesnikov, Hugo Krawczyk, Yehuda Lindell, Alex J. Malozemoff, and Tal Rabin


Attribute-based methods provide authorization to parties based on whether their set of attributes (e.g., age, organization, etc.) fulfills a policy. In attribute-based encryption (ABE), authorized parties can decrypt, and in attribute-based credentials (ABCs), authorized parties can authenticate themselves. In this paper, we combine elements of ABE and ABCs together with garbled circuits to construct attribute-based key exchange (ABKE). Our focus is on an interactive solution involving a client that holds a certificate (issued by an authority) vouching for that client's attributes and a server that holds a policy computable on such a set of attributes. The goal is for the server to establish a shared key with the client but only if the client's certified attributes satisfy the policy. Our solution enjoys strong privacy guarantees for both the client and the server, including attribute privacy and unlinkability of client sessions. Our main contribution is a construction of ABKE for arbitrary circuits with high (concrete) efficiency. Specifically, we support general policies expressible as boolean circuits computed on a set of attributes. Even for policies containing hundreds of thousands of gates the performance cost is dominated by two pairing computations per policy input. Put another way, for a similar cost to prior ABE/ABC solutions, which can only support small formulas efficiently, we can support vastly richer policies. We implemented our solution and report on its performance. For policies with 100,000 gates and 200 inputs over a realistic network, the server and client spend 957 ms and 176 ms on computation, respectively. When using offline preprocessing and batch signature verification, this drops to only 243 ms and 97 ms.

Note: Added needed acknowledgement.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.23rd ACM Conference on Computer and Communications Security (CCS), 2016.
secure computationkey exchange
Contact author(s)
kolesnikov @ research bell-labs com
2016-12-09: last of 3 revisions
2016-05-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vladimir Kolesnikov and Hugo Krawczyk and Yehuda Lindell and Alex J.  Malozemoff and Tal Rabin},
      title = {Attribute-based Key Exchange with General Policies},
      howpublished = {Cryptology ePrint Archive, Paper 2016/518},
      year = {2016},
      doi = {10.1145/2976749.2978359},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.