Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / searchable encryption, structured encryption, controlled disclosure, cloud storage

Publication Info: The preliminary version appeared at Asiacrypt 2010. This is the full version.

Date: received 5 Jan 2011, last revised 5 Jan 2011

Contact author: senyk at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20110106:030048 (All versions of this report)

Short URL: ia.cr/2011/010

Discussion forum: Show discussion | Start new discussion