Privacy-preserving k-nearest neighbour query on outsourced database

Rui Xu, Kirill Morozov, Yanjiang Yang, Jianying Zhou, Tsuyoshi Takagi

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

5 Citations (Scopus)


Cloud computing brought a shift from the traditional clientserver model to DataBase as a Service (DBaaS), where the data owner outsources her database as well as the data management function to the cloud service provider. Although cloud services relieve the clients from the data management burdens, a significant concern about the data privacy remains. In this work, we focus on privacy-preserving k-nearest neighbour (k-NN) query, and provide the first sublinear solution (with preprocessing) with computational complexity Õ (klog4n) in the honestbut- curious adversarial setting. Our constructions use the data structure called kd-tree to achieve sublinear query complexity. In order to protect data access patterns, garbled circuits are used to simulate Oblivious RAM (ORAM) for accessing data in the kd-tree. Compared to the existing solutions, our scheme imposes little overhead on both the data owner and the querying client.

Original languageEnglish
Title of host publicationInformation Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings
EditorsJoseph K. Liu, Ron Steinfeld
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783319402529
Publication statusPublished - 2016
Event21st Australasian Conference on Information Security and Privacy, ACISP 2016 - Melbourne, Australia
Duration: Jul 4 2016Jul 6 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other21st Australasian Conference on Information Security and Privacy, ACISP 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Privacy-preserving k-nearest neighbour query on outsourced database'. Together they form a unique fingerprint.

Cite this