Securely and Efficiently Nearest Neighbor Query Scheme Based on Additive Secret Sharing

AbstractWith the wide application of machine learning algorithms in medical diagnosis, we gradually confronted the problem of computing and storing large-scale data. Outsourcing cloud computing has become the most cost-effective option to address these challenges. However, privacy and security issues have always existed in outsourced computing. Therefore, in this article, we propose an efficient index nearest neighbor query scheme based on Secret Sharing (SS) and Secure Multi-Party Computation (MPC) with the dual-cloud model architecture. For secure and efficient queries, we have designed a comprehensive set of secure index generation algorithms and secure index query algorithms. The cloud server creates indexes for the outsourced data and saves them through index generation algorithms in the offline phase, and uses index query algorithms to complete secure and efficient nearest neighbor query tasks in the online phase where users participate. Security analysis proves that our scheme protects the security of outsourced data and the privacy of query data. Simulation results on real datasets also demonstrate that the proposed scheme has higher efficiency and lower communication overhead compared with existing schemes.KeywordsPrivacy-preservationOutsourcing computationSecret sharingNearest neighbor(NN) queryk-d tree