Privacy-preserving k-nearest neighbour query on outsourced database

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

doi:10.1007/978-3-319-40253-6_11

Privacy-preserving k-nearest neighbour query on outsourced database

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

Laboratory of Mathematical Design for Advanced Cryptography

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

Abstract

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 Õ (klog⁴n) 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 language	English
Title of host publication	Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings
Editors	Joseph K. Liu, Ron Steinfeld
Publisher	Springer Verlag
Pages	181-197
Number of pages	17
ISBN (Print)	9783319402529
DOIs	https://doi.org/10.1007/978-3-319-40253-6_11
Publication status	Published - 2016
Event	21st Australasian Conference on Information Security and Privacy, ACISP 2016 - Melbourne, Australia Duration: Jul 4 2016 → Jul 6 2016

Publication series

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

Other

Other	21st Australasian Conference on Information Security and Privacy, ACISP 2016
Country/Territory	Australia
City	Melbourne
Period	7/4/16 → 7/6/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-40253-6_11

Cite this

Xu, R., Morozov, K., Yang, Y., Zhou, J., & Takagi, T. (2016). Privacy-preserving k-nearest neighbour query on outsourced database. In J. K. Liu, & R. Steinfeld (Eds.), Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings (pp. 181-197). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9722). Springer Verlag. https://doi.org/10.1007/978-3-319-40253-6_11

Privacy-preserving k-nearest neighbour query on outsourced database. / Xu, Rui; Morozov, Kirill; Yang, Yanjiang et al.
Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. ed. / Joseph K. Liu; Ron Steinfeld. Springer Verlag, 2016. p. 181-197 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9722).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Xu, R, Morozov, K, Yang, Y, Zhou, J & Takagi, T 2016, Privacy-preserving k-nearest neighbour query on outsourced database. in JK Liu & R Steinfeld (eds), Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9722, Springer Verlag, pp. 181-197, 21st Australasian Conference on Information Security and Privacy, ACISP 2016, Melbourne, Australia, 7/4/16. https://doi.org/10.1007/978-3-319-40253-6_11

Xu R, Morozov K, Yang Y, Zhou J, Takagi T. Privacy-preserving k-nearest neighbour query on outsourced database. In Liu JK, Steinfeld R, editors, Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. Springer Verlag. 2016. p. 181-197. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-40253-6_11

Xu, Rui ; Morozov, Kirill ; Yang, Yanjiang et al. / Privacy-preserving k-nearest neighbour query on outsourced database. Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings. editor / Joseph K. Liu ; Ron Steinfeld. Springer Verlag, 2016. pp. 181-197 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{56fcf8d4dd61422091a7c87b4d64e57d,

title = "Privacy-preserving k-nearest neighbour query on outsourced database",

abstract = "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 {\~O} (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.",

author = "Rui Xu and Kirill Morozov and Yanjiang Yang and Jianying Zhou and Tsuyoshi Takagi",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 21st Australasian Conference on Information Security and Privacy, ACISP 2016 ; Conference date: 04-07-2016 Through 06-07-2016",

year = "2016",

doi = "10.1007/978-3-319-40253-6_11",

language = "English",

isbn = "9783319402529",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "181--197",

editor = "Liu, {Joseph K.} and Ron Steinfeld",

booktitle = "Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Privacy-preserving k-nearest neighbour query on outsourced database

AU - Xu, Rui

AU - Morozov, Kirill

AU - Yang, Yanjiang

AU - Zhou, Jianying

AU - Takagi, Tsuyoshi

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84978200144&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84978200144&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-40253-6_11

DO - 10.1007/978-3-319-40253-6_11

M3 - Conference contribution

AN - SCOPUS:84978200144

SN - 9783319402529

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 181

EP - 197

BT - Information Security and Privacy - 21st Australasian Conference, ACISP 2016, Proceedings

A2 - Liu, Joseph K.

A2 - Steinfeld, Ron

PB - Springer Verlag

T2 - 21st Australasian Conference on Information Security and Privacy, ACISP 2016

Y2 - 4 July 2016 through 6 July 2016

ER -

Privacy-preserving k-nearest neighbour query on outsourced database

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this