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

Gowri Pandian Sundarapandi, Salma Bokhary, Bharath K. Samanthula, Boxiang Dong

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.

Original languageEnglish
Title of host publicationProceedings - 2023 IEEE Cloud Summit, Cloud Summit 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9798350322170
StatePublished - 2023
Event2023 IEEE Cloud Summit, Cloud Summit 2023 - Columbia, United States
Duration: 6 Jul 20237 Jul 2023

Publication series

NameProceedings - 2023 IEEE Cloud Summit, Cloud Summit 2023


Conference2023 IEEE Cloud Summit, Cloud Summit 2023
Country/TerritoryUnited States


  • Cloud computing
  • homomorphic encryption
  • k-nearest neighbor
  • privacy
  • verifiable computation


Dive into the research topics of 'A Probabilistic Approach for Secure and Verifiable Computation of kNN Queries in Cloud'. Together they form a unique fingerprint.

Cite this