Building Confidential and Efficient Query Services in the ...

1 1 Building Confidential and Efficient QueryServices in the Cloud with RASP DataPerturbationHuiqi Xu, Shumin Guo, Keke ChenData Intensive Analysis and Computing LabOhio Center of Excellence in Knowledge Enabled ComputingDepartment of Computer Science and EngineeringWright State University, Dayton, OH 45435 Abstract With the wide deployment of public cloud computing infrastructures, using clouds to host data Query Services hasbecome an appealing solution for the advantages on scalability and cost-saving. However, some data might be sensitive that thedata owner does not want to move to the cloud unless the data confidentiality and Query privacy are guaranteed.

2 On the otherhand, a secured Query service should still provide efficientquery processing and significantly reduce the in-house workload tofully realize the benefits of cloud computing. We propose theRASP data perturbation method to provide secure and efficientrange Query and kNN Query Services for protected data in the cloud. The RASP data perturbation method combines orderpreserving encryption, dimensionality expansion, randomnoise injection, and random projection, to provide strong resilience toattacks on the perturbed data and queries. It also preservesmultidimensional ranges, which allows existing indexing techniquesto be applied to speedup range Query processing.

3 The kNN-R algorithm is designed to work with the RASP range Query algorithmto process the kNN queries. We have carefully analyzed the attacks on data and queries under a precisely defined threat modeland realistic security assumptions. Extensive experiments have been conducted to show the advantages of this approachonefficiency and Terms Query Services in the cloud, privacy, range Query , kNN Query 1 INTRODUCTIONH osting data-intensive Query Services in the cloud isincreasingly popular because of the unique advan-tages in scalability and cost-saving. With the cloudinfrastructures, the service owners can convenientlyscale up or down the service and only pay for thehours of using the servers.

4 This is an attractive featurebecause the workloads of Query Services are highlydynamic, and it will be expensive and inefficient toserve such dynamic workloads with in-house infras-tructures [2]. However, because the service providerslose the control over the data in the cloud, dataconfidentiality and Query privacy have become themajor concerns. Adversaries, such as curious serviceproviders, can possibly make a copy of the databaseor eavesdrop users queries, which will be difficult todetect and prevent in the cloud new approachesare needed to preserve dataconfidentiality and Query privacy, the efficiency ofquery Services and the benefits of using the cloudsshould also be preserved.

5 It will not be meaningfulto provide slow Query Services as a result of securityand privacy assurance. It is also not practical forthe data owner to use a significant amount of in-house resources, because the purpose of using cloudresources is to reduce the need of maintaining scalablein-house infrastructures. Therefore, there is an intri-cate relationship among the data confidentiality, queryprivacy, the quality of service, and the economics ofusing the summarize these requirements for constructinga practical Query service in the cloud as the CPEL criteria: data Confidentiality, Query Privacy, Efficientquery processing, and Low in-house processing these requirements will dramatically in-crease the complexity of constructing Query servicesin the cloud.

6 Some related approaches have beendeveloped to address some aspects of the , they do not satisfactorily address all ofthese aspects. For example, the crypto-index [12] andOrder Preserving Encryption (OPE) [1] are vulnerableto the attacks. The enhanced crypto-index approach[14] puts heavy burden on the in-house infrastructureto improve the security and privacy. The New Casperapproach [24] uses cloaking boxes to protect data ob-jects and queries, which affects the efficiency of queryprocessing and the in-house workload. We have sum-marized the weaknesses of the existing approaches inSection propose the RAndom Space Perturbation(RASP) approach to constructing practical rangequery and k-nearest-neighbor (kNN) Query Services inthe cloud.

7 The proposed approach will address all theIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING VOL:26 NO:2 YEAR 20142four aspects of the CPEL criteria and aim to achieve agood balance on them. The basic idea is to randomlytransform the multidimensional datasets with a com-bination of order preserving encryption, dimension-ality expansion, random noise injection, and randomproject, so that the utility for processing range queriesis preserved. The RASP perturbation is designed insuch a way that the queried ranges are securelytransformed into polyhedra in the RASP-perturbeddata space, which can be efficiently processed with thesupport of indexing structures in the perturbed RASP kNN Query service (kNN-R) uses the RASP range Query service to process kNN queries.

8 The keycomponents in the RASP framework include (1) thedefinition and properties of RASP perturbation; (2) theconstruction of the privacy-preserving range queryservices; (3) the construction of privacy-preservingkNN Query Services ; and (4) an analysis of the attackson the RASP-protected data and summary, the proposed approach has a numberof unique contributions. The RASP perturbation is a unique combinationof OPE, dimensionality expansion, random noiseinjection, and random projection, which providesstrong confidentiality guarantee. The RASP approach preserves the topology ofmultidimensional range in secure transformation,which allows indexing and efficiently Query pro-cessing.

9 The proposed service constructions are able tominimize the in-house processing workload be-cause of the low perturbation cost and high pre-cision Query results. This is an important featureenabling practical cloud-based have carefully evaluated our approach with syn-thetic and real datasets. The results show its uniqueadvantages on all aspects of the CPEL entire paper is organized as follows. In Sec-tion 3, we define the RASP perturbation method,describe its major properties, and analyze the attacksto the RASP perturbed data. We also introduce theframework for constructing the Query Services withthe RASP perturbation.

10 In Section 4 we describe thealgorithm for transforming queries and processingrange queries. In Section 5, the range Query serviceis extended to handle kNN queries. When describingthese two Services , we also analyze the attacks onthe Query privacy. Finally, we present some relatedapproaches in Section 7 and analyze their weaknessesin terms of the CPEL QUERYSERVICES IN THECLOUDThis section presents the notations, the system archi-tecture, and the threat model for the RASP approach,and prepares for the security analysis [3] in latersections. The design of the system architecture keepsthe cloud economics in mind so that most data storageand computing tasks will be done in the cloud.