Practical and secure nearest neighbor search on encrypted large-scale data

Boyang Wang, Yantian Hou, Ming Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations


Nearest neighbor search (or k-nearest neighbor search in general) is one of the most fundamental queries on massive datasets, and it has extensive applications such as pattern recognition, statistical classification, graph algorithms, Location-Based Services and online recommendations. With the raising trend of outsourcing massive sensitive datasets to public clouds, it is urgent for companies and organizations to demand fast and secure nearest neighbor search solutions over their outsourced data, but without revealing privacy to untrusted clouds. However, existing solutions for secure nearest neighbor search still face significant limitations, which make them far from practice. In this paper, we propose a new searchable encryption scheme, which can efficiently and securely enable nearest neighbor search over encrypted data on untrusted clouds. Specifically, we modify the search algorithm of nearest neighbors with tree structures (e.g., R-trees), where the modified algorithm adapts to lightweight cryptographic primitives (e.g., Order-Preserving Encryption) without affecting the original faster-than-linear search complexity. As a result, we address all the limitations in the previous works while still maintaining correctness and security. Moreover, our design is general, which can be used for secure k-nearest neighbor search, and it is compatible with other similar tree structures. Our experimental results on Amazon EC2 show that our scheme is extremely practical over massive datasets.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2016 - 35th Annual IEEE International Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781467399531
StatePublished - Jul 27 2016
Event35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016 - San Francisco, United States
Duration: Apr 10 2016Apr 14 2016

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Practical and secure nearest neighbor search on encrypted large-scale data'. Together they form a unique fingerprint.

Cite this