Adaptively Secure and Fast Processing of Conjunctive Queries over Encrypted Data
This paper concerns the fundamental problem of processing conjunctive queries that contain both keyword and range conditions on public clouds in a privacy preserving manner. No prior Searchable Symmetric Encryption (SSE) based privacy preserving conjunctive query processing scheme satisfies the three requirements of adaptive security, efficient query processing, and scalable index size. In this paper, we propose the first privacy preserving conjunctive query processing scheme that satisfies all the above three requirements. To achieve adaptive security, we propose an Indistinguishable Bloom Filter (IBF) data structure for indexing.To achieve efficient query processing and structural indistinguishability, we propose a highly balanced binary tree data structure called Indistinguishable Binary Tree (IBtree). To achieve scalable and compact index size, we propose an IBtree space compression algorithm to remove redundant information in IBFs. To optimize search efficiency, we propose a traversal minimization algorithm. To make our scheme dynamic, we propose update algorithms.We prove that our scheme is adaptive secure under the IND-CKA secure model. We implemented our scheme in C++ and evaluated its performance on two real-world data sets. Experimental results show that our scheme is both fast and scalable. For example, processing a query only takes a few milliseconds for millions of records.
Branch: CSE Domain: Data Mining