Efficient outsourcing of secure k-nearest neighbour query over encrypted database. Issue 69 (August 2017)
- Record Type:
- Journal Article
- Title:
- Efficient outsourcing of secure k-nearest neighbour query over encrypted database. Issue 69 (August 2017)
- Main Title:
- Efficient outsourcing of secure k-nearest neighbour query over encrypted database
- Authors:
- Xu, Rui
Morozov, Kirill
Yang, Yanjiang
Zhou, Jianying
Takagi, Tsuyoshi - Abstract:
- Abstract: Cloud computing allows a cloud user to outsource her data and the related computation to a cloud service provider to save storage and computational cost. This convenient service has brought a shift from the traditional client–server model to DataBase as a Service (DBaaS). Although DBaaS relieves the clients from the data management burdens, a significant concern about the data privacy remains. In this work, we focus on outsourcing secure k -nearest neighbour ( k -NN) query, and provide the first sublinear solution (with preprocessing) with computational complexity O ( k lg n ( lg 2 n + lg 3 k ) ) . Our construction uses the data structure called k d-tree to achieve the sublinear query complexity. In order to protect data access patterns, garbled circuits are used to simulate Oblivious RAM (ORAM) for accessing data in the k d-tree. Compared with the existing solutions, our scheme imposes only constant overhead on both the data owner and the querying client.
- Is Part Of:
- Computers & security. Issue 69(2017)
- Journal:
- Computers & security
- Issue:
- Issue 69(2017)
- Issue Display:
- Volume 69, Issue 69 (2017)
- Year:
- 2017
- Volume:
- 69
- Issue:
- 69
- Issue Sort Value:
- 2017-0069-0069-0000
- Page Start:
- 65
- Page End:
- 83
- Publication Date:
- 2017-08
- Subjects:
- Privacy-preserving computation -- k nearest neighbour search -- Outsourcing of computation -- Encrypted database -- Oblivious RAM
Computer security -- Periodicals
Electronic data processing departments -- Security measures -- Periodicals
005.805 - Journal URLs:
- http://www.sciencedirect.com/science/journal/01674048 ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.cose.2016.11.012 ↗
- Languages:
- English
- ISSNs:
- 0167-4048
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.781000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 2817.xml