A Probabilistic Approach for Secure and Verifiable Computation of kNN Queries in Cloud

The tremendous benefits of outsourcing have influenced many organizations to migrate their data and DBMS functionalities to the cloud infrastructure. Since cloud service providers offer advanced security services, data migration typically boosts the security of business data and operations. Nonetheless, since a cloud is an untrusted third party, it is important for organizations to ensure confidentiality of the outsourced data and integrity of results generated by the cloud. In this paper, we focus on the Secure and Verifiable Computation for k-Nearest Neighbor (SVC-kNN) problem. Existing SVC-kNN solutions delegate the verification task solely to a single semi-trusted party and are unreliable in terms of security as the verification server could be either dishonest or compromised. To address these issues, we propose a novel and probabilistic SVC-kNN protocol that utilizes a randomization technique and additive homomorphic properties under the two-cloud model. Our proposed solution facilitates the clouds to jointly compute verification proofs and allows the end-user to verify the computation results efficiently. Additionally, our solution is highly efficient from the data owner and query issuers' perspective as most of the critical computations are performed by the clouds. Furthermore, our experimental results using a real dataset clearly demonstrate the effectiveness of our protocol.