QuickN: Practical and Secure Nearest Neighbor Search on Encrypted Large-Scale Data

Boyang Wang, Yantian Hou, Ming Li

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

In this article, we propose a scheme, named QuickN, which can efficiently and securely enable nearest neighbor search over encrypted data on untrusted clouds. Specifically, we modify the search algorithm of nearest neighbors in tree structures (e.g., R-trees), such that the modified algorithm adapts to lightweight cryptographic primitives (e.g., Order-Preserving Encryption) without affecting the original faster-than-linear search complexity. Moreover, we propose an optimized algorithm on top of our modified search algorithm, where it can significantly save communication overheads of a client without introducing any additional information leakage. We devise an approximate algorithm to k k-nearest neighbor search to improve search efficiency by taking a tradeoff in the completeness of search results. In addition, we also demonstrate our design only leaks minimal privacy against advanced inference attacks. Our experimental results on Amazon EC2 show that our algorithms are extremely practical over massive datasets.

Original languageEnglish (US)
Pages (from-to)2066-2078
Number of pages13
JournalIEEE Transactions on Cloud Computing
Volume10
Issue number3
DOIs
StatePublished - 2022

Keywords

  • Nearest neighbor search
  • encrypted data
  • large-scale data
  • privacy-preserving

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'QuickN: Practical and Secure Nearest Neighbor Search on Encrypted Large-Scale Data'. Together they form a unique fingerprint.

Cite this