Paper 2011/010

Structured Encryption and Controlled Disclosure

Melissa Chase and Seny Kamara

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. The preliminary version appeared at Asiacrypt 2010. This is the full version.
Keywords
searchable encryptionstructured encryptioncontrolled disclosurecloud storage
Contact author(s)
senyk @ microsoft com
History
2011-01-06: received
Short URL
https://ia.cr/2011/010
License
Creative Commons Attribution
CC BY

BibTeX

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