Fast and Scalable Range Query Processing with Strong Privacy Protection for Cloud Computing
Abstract
This paper is concerned with the problem of privacy-preserving range query processing on clouds.
Prior schemes are weak in privacy protection as they cannot achieve index indistinguishability, and therefore allow the cloud to statistically estimate the values of data and queries using domain knowledge and history query results.
We propose two algorithms, namely PBtree traversal width minimization and PBtree traversal depth minimization, to improve query processing efficiency.
We implemented and evaluated our scheme on a real-world dataset with 5 million items. For example, for a query whose results contain 10 data items, it takes only 0.17 ms.
Conclusion
Privacy has been the key road block to cloud computing as clouds may not be fully trusted.
This paper is concerned with the problem of privacy-preserving range query processing on clouds.
Prior schemes are weak in privacy protection as they cannot achieve index indistinguishability, and therefore allow the cloud to statistically estimate the values of data and queries using domain knowledge and history query results.
In this paper, we propose the first range query processing scheme that achieves index indistinguishability under the indistinguishability against chosen keyword attack (IND-CKA).
Our key idea is to organize indexing elements in a complete binary tree called PBtree, which satisfies structure indistinguishability
We prove that our scheme is secure under the widely adopted IND-CKA security model.
