Efficient outsourcing of secure k-nearest neighbour query over encrypted database. Issue 69 (August 2017) - Xu, Rui; Morozov, Kirill; Yang, Yanjiang; Zhou, Jianying; Takagi, Tsuyoshi
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.