Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query

Abstract

Secure k-Nearest Neighbor (k-NN) query aims to find k nearest data of a given query from an encrypted database in a cloud server without revealing privacy to the untrusted cloud and has wide applications in many areas, such as privacy-preserving machine learning and secure biometric identification. Several solutions have been put forward to solve this challenging problem. However, the existing schemes still suffer from various limitations in terms of efficiency and flexibility. In this paper, we propose a new encrypt-then-index strategy for the secure k-NN query, which can simultaneously achieve sub-linear search complexity (efficiency) and support dynamical update over the encrypted database (flexibility). Specifically, we propose a novel algorithm to transform the encrypted database and encrypted query points in the cloud. By indexing the transformed database using spatial data structures such as the R-tree index, our strategy enables sub-linear complexity for secure k-NN queries and allows users to dynamically update the encrypted database. To the best of our knowledge, the proposed strategy is the first to simultaneously provide these two properties. Through theoretical analysis and extensive experiments, we formally prove the security and demonstrate the efficiency of our scheme.

Graphical abstract

Keywords

cloud computing / secure k-NN query / sub-linear complexity / dynamic update

Xingxin Li received the PhD degree in Computer Science and Technology from Nanjing University of Aeronautics and Astronautics, China. He is currently a postdoc at Department of Mathematical Informatics, University of Tokyo, Japan. His research interests include secure outsourcing computation and privacy-preserving machine learning

Youwen Zhu received his BE degree and PhD degree in Computer Science from University of Science and Technology of China, China in 2007 and 2012, respectively. From 2012 to 2014, he is a JSPS postdoc in Kyushu University, Japan. He is currently a Professor at the College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, China. His research interests include identity authentication, information security anddata privacy

Rui Xu received his PhD degree in mathematics from Kyushu University, Japan in 2015. He is currently with the School of Computer Science, China University of Geosciences, China. His research areas include secret sharing schemes, multi-party computation and privacy-preserving techniques

Jian Wang received the PhD degree in Nanjing University, Nanjing, China in 1998. He is currently a Professor at the College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, China. His research interests include cryptographic protocol and malicious tracking

Yushu Zhang received the PhD degree in computer science and technology from the College of Computer Science, Chongqing University, China in 2014. He is currently a Professor with the College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, China. His current research interests include multimedia security, artificial intelligence, cloud computing security, Internet of Things security, and blockchain

References

[1] Shan Z, Ren K, Blanton M, Wang C. Practical secure computation outsourcing: a survey. ACM Computing Surveys, 2019, 51( 2): 31

[2] Zhang M, Zhang Y, Shen G. PPDDS: a privacy-preserving disease diagnosis scheme based on the secure Mahalanobis distance evaluation model. IEEE Systems Journal, 2022, 16( 3): 4552–4562

[3] Zissis D, Lekkas D. Addressing cloud computing security issues. Future Generation Computer Systems, 2012, 28( 3): 583–592

[4] Zhang M, Zhang Y, Jiang Y, Shen J. Obfuscating EVES algorithm and its application in fair electronic transactions in public clouds. IEEE Systems Journal, 2019, 13( 2): 1478–1486

[5] Barona R, Anita E A M. A survey on data breach challenges in cloud computing security: issues and threats. In: Proceedings of 2017 International Conference on Circuit, Power and Computing Technologies (ICCPCT). 2017, 1−8

[6] Zhang M, Chen Y, Lin J. A privacy-preserving optimization of neighborhood-based recommendation for medical-aided diagnosis and treatment. IEEE Internet of Things Journal, 2021, 8( 13): 10830–10842

[7] Domingo-Ferrer J, Farràs O, Ribes-González J, Sánchez D. Privacy-preserving cloud computing on sensitive data: a survey of methods, products and challenges. Computer Communications, 2019, 140−141: 38−60

[8] Li X, Zhu Y, Wang J, Zhang J. Efficient and secure multi-dimensional geometric range query over encrypted data in cloud. Journal of Parallel and Distributed Computing, 2019, 131: 44–54

[9] Mei Z, Zhu H, Cui Z, Wu Z, Peng G, Wu B, Zhang C. Executing multi-dimensional range query efficiently and flexibly over outsourced ciphertexts in the cloud. Information Sciences, 2018, 432: 79–96

[10] Cao N, Wang C, Li M, Ren K, Lou W. Privacy-preserving multi-keyword ranked search over encrypted cloud data. IEEE Transactions on Parallel and Distributed Systems, 2014, 25( 1): 222–233

[11] Fu Z, Wu X, Wang Q, Ren K. Enabling central keyword-based semantic extension search over encrypted outsourced data. IEEE Transactions on Information Forensics and Security, 2017, 12( 12): 2986–2997

[12] Guan Z, Liu X, Wu L, Wu J, Xu R, Zhang J, Li Y. Cross-lingual multi-keyword rank search with semantic extension over encrypted data. Information Sciences, 2020, 514: 523–540

[13] Liu Y, Luo Y, Zhu Y, Liu Y, Li X. Secure multi-label data classification in cloud by additionally homomorphic encryption. Information Sciences, 2018, 468: 89–102

[14] Zhu D, Zhu H, Liu X, Li H, Wang F, Li H, Feng D. CREDO: efficient and privacy-preserving multi-level medical pre-diagnosis based on ML-kNN. Information Sciences, 2020, 514: 244–262

[15] Yang Y, Xiong P, Huang Q, Chen F. Secure and efficient outsourcing computation on large-scale linear regressions. Information Sciences, 2020, 522: 134–147

[16] Hu S, Li M, Wang Q, Chow S S M, Du M. Outsourced biometric identification with privacy. IEEE Transactions on Information Forensics and Security, 2018, 13( 10): 2448–2463

[17] Zhu Y, Li X, Wang J, Li J. Cloud-assisted secure biometric identification with sub-linear search efficiency. Soft Computing, 2020, 24( 8): 5885–5896

[18] Yang X, Zhu H, Wang F, Zhang S, Lu R, Li H. MASK: efficient and privacy-preserving m-tree based biometric identification over cloud. Peer-to-Peer Networking and Applications, 2021, 14( 4): 2171–2186

[19] Zhang M, Song W, Zhang J. A secure clinical diagnosis with privacy-preserving multiclass support vector machine in clouds. IEEE Systems Journal, 2022, 16( 1): 67–78

[20] Elmehdwi Y, Samanthula B K, Jiang W. Secure k-nearest neighbor query over encrypted data in outsourced environments. In: Proceedings of 2014 IEEE 30th International Conference on Data Engineering. 2014, 664−675

[21] Wong W K, Cheung D W L, Kao B, Mamoulis N. Secure KNN computation on encrypted databases. In: Proceedings of 2009 ACM SIGMOD International Conference on Management of data. 2009, 139−152

[22] Zhu Y, Huang Z, Takagi T. Secure and controllable k-NN query over encrypted cloud data with key confidentiality. Journal of Parallel and Distributed Computing, 2016, 89: 1−12

[23] Wang B, Hou Y, Li M. Practical and secure nearest neighbor search on encrypted large-scale data. In: Proceedings of the 35th Annual IEEE International Conference on Computer Communications. 2016, 1−9

[24] Lei X, Liu A X, Li R, Tu G H. SecEQP: a secure and efficient scheme for SkNN query problem over encrypted geodata on cloud. In: Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE). 2019, 662−673

[25] Guo C, Su S, Choo K K R, Tang X. A fast nearest neighbor search scheme over outsourced encrypted medical images. IEEE Transactions on Industrial Informatics, 2021, 17( 1): 514–523

[26] Guttman A. R-trees: a dynamic index structure for spatial searching. In: Proceedings of 1984 ACM SIGMOD International Conference on Management of Data. 1984, 47−57

[27] Wang B, Hou Y, Li M. QuickN: practical and secure nearest neighbor search on encrypted large-scale data. IEEE Transactions on Cloud Computing, 2022, 10( 3): 2066–2078

[28] Yao B, Li F, Xiao X. Secure nearest neighbor revisited. In: Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE). 2013, 733−744

[29] Cao N, Wang C, Li M, Ren K, Lou W. Privacy-preserving multi-keyword ranked search over encrypted cloud data. In: Proceedings of 2011 Proceedings IEEE INFOCOM. 2011, 829−837

[30] Zhu Y, Xu R, Takagi T. Secure k-NN computation on encrypted cloud data without sharing key with query users. In: Proceedings of 2013 International Workshop on Security in Cloud Computing. 2013, 55−60

[31] Zhu Y, Xu R, Takagi T. Secure k-NN query on encrypted cloud database without key-sharing. International Journal of Electronic Security and Digital Forensics, 2013, 5(3−4): 201−217

[32] Zhou L, Zhu Y, Castiglione A. Efficient k-NN query over encrypted data in cloud with limited key-disclosure and offline data owner. Computers & Security, 2017, 69: 84–96

[33] Yuan J, Yu S. Efficient privacy-preserving biometric identification in cloud computing. In: Proceedings of 2013 Proceedings IEEE INFOCOM. 2013, 2652−2660

[34] Wang Q, Hu S, Ren K, He M, Du M, Wang Z. CloudBI: practical privacy-preserving outsourcing of biometric identification in the cloud. In: Proceedings of the 20th European Symposium on Research in Computer Security. 2015, 186−205

[35] Hu H, Xu J, Ren C, Choi B. Processing private queries over untrusted data cloud through privacy homomorphism. In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 601−612

[36] Berg M, Cheong O, Kreveld M, Overmars M. Computational Geometry: Algorithms and Applications. 3rd ed. Berlin: Springer, 2008

[37] Boldyreva A, Chenette N, Lee Y, O’Neill A. Order-preserving symmetric encryption. In: Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2009, 224−241

[38] Goldreich O. Foundations of Cryptography Volume II Basic Applications. Cambridge: Cambridge University Press, 2004

[39] Wang B, Hou Y, Li M, Wang H, Li H, Li F. Tree-based multi-dimensional range search on encrypted data with enhanced privacy. In: Proceedings of the 10th International ICST Conference on Security and Privacy in Communication Networks. 2015, 374−394

[40] Wang B, Hou Y, Li M, Wang H, Li H. Maple: scalable multi-dimensional range search over encrypted cloud data with tree-based index. In: Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security. 2014, 111−122

[41] Wang P, Ravishankar C V. Secure and efficient range queries on outsourced databases using Rp-trees. In: Proceedings of the 29th IEEE International Conference on Data Engineering. 2013, 314−325

[42] Manolopoulos Y, Nanopoulos A, Papadopoulos A N, Theodoridis Y. R-Trees: Theory and Applications. London: Springer, 2006

[43] Bentley J L. Multidimensional binary search trees used for associative searching. Communications of the ACM, 1975, 18( 9): 509–517

[44] Bachrach Y, Finkelstein Y, Gilad-Bachrach R, Katzir L, Koenigstein N, Nice N, Paquet U. Speeding up the Xbox recommender system using a Euclidean transformation for inner-product spaces. In: Proceedings of the 8th ACM Conference on Recommender systems. 2014, 257−264

[45] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19( 5): 895–934

[46] Sun W, Wang B, Cao N, Li M, Lou W, Hou Y T, Li H. Privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking. In: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013, 71−82

[47] Xia Z, Wang X, Sun X, Wang Q. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE Transactions on Parallel and Distributed Systems, 2016, 27( 2): 340–352

Acknowledgements

This work was support by the National Key R&D Program of China (No. 2020YFB1005900), the National Natural Science Foundation of China (Grant Nos. 62172216, 62032025, 62071222, U20A201092), the Key R&D Program of Guangdong Province (No. 2020B0101090002), the Natural Science Foundation of Jiangsu Province (No. BK20211180, BK20200418), the Research Fund of Guangxi Key Laboratory of Trusted Software (No. KX202034), and JSPS Postdoctoral Fellowships for Research in Japan (No. P21073).

RIGHTS & PERMISSIONS

2024 Higher Education Press