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 formats: PDF | BibTeX Citation Version: 20110106:030048 (All versions of this report) Discussion forum: Show discussion | Start new discussion