Efficient outsourcing of secure k-nearest neighbour query over encrypted database. Issue 69 (August 2017)

• Record Type: Journal Article
• Authors: Xu, Rui; Morozov, Kirill; Yang, Yanjiang; Zhou, Jianying; Takagi, Tsuyoshi
• Is Part Of: Computers & security. Issue 69(2017)
• 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
• DOI: 10.1016/j.cose.2016.11.012
• Languages: English
• ISSNs: 0167-4048

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.