Paper 2011/010

Structured Encryption and Controlled Disclosure

Melissa Chase and Seny Kamara


We consider the problem of encrypting structured data (e.g., a web graph or a social network) in such a way that it can be efficiently and privately queried. For this purpose, we introduce the notion of structured encryption which generalizes previous work on symmetric searchable encryption (SSE) to the setting of arbitrarily-structured data. In the context of cloud storage, structured encryption allows a client to encrypt data without losing the ability to query and retrieve it efficiently. Another application, which we introduce in this work, is to the problem of controlled disclosure, where a data owner wishes to grant access to only part of a massive dataset. We propose a model for structured encryption, a formal security definition and several efficient constructions. We present schemes for performing queries on two simple types of structured data, specifically lookup queries on matrix-structured data, and search queries on labeled data. We then show how these can be used to construct efficient schemes for encrypting graph data while allowing for efficient neighbor and adjacency queries. Finally, we consider data that exhibits a more complex structure such as labeled graph data (e.g., web graphs). We show how to encrypt this type of data in order to perform focused subgraph queries, which are used in several web search algorithms. Our construction is based on our labeled data and basic graph encryption schemes and provides insight into how several simpler algorithms can be combined to generate an efficient scheme for more complex queries.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. The preliminary version appeared at Asiacrypt 2010. This is the full version.
searchable encryptionstructured encryptioncontrolled disclosurecloud storage
Contact author(s)
senyk @ microsoft com
2011-01-06: received
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Seny Kamara},
      title = {Structured Encryption and Controlled Disclosure},
      howpublished = {Cryptology ePrint Archive, Paper 2011/010},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.