Indexing dynamic encrypted database in cloud for efficient secure <i>k</i>-nearest neighbor query

doi:10.1007/s11704-022-2401-1

Front. Comput. Sci.

2024, Vol. 18

Issue (1) : 181803 https://doi.org/10.1007/s11704-022-2401-1

Information Security

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

Xingxin LI^1,², Youwen ZHU^1,³(

), Rui XU⁴, Jian WANG¹, Yushu ZHANG¹

¹. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
². Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8654, Japan
³. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China
⁴. School of Computer Science, China University of Geosciences, Wuhan 430074, China

Download: PDF(3844 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

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

Corresponding Author(s): Youwen ZHU

About author:

Changjian Wang and Zhiying Yang contributed equally to this work.

Just Accepted Date: 28 November 2022 Issue Date: 21 February 2023

Cite this article:

Xingxin LI,Youwen ZHU,Rui XU, et al. Indexing dynamic encrypted database in cloud for efficient secure k-nearest neighbor query[J]. Front. Comput. Sci., 2024, 18(1): 181803.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-2401-1
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I1/181803

	[18]	[28]	[21]	[17]	[25]	[24]	[27]	Our scheme
Sub-linear complexity	$√$	$√$	×	$√$	×	$√$	$√$	$√$
Dynamic update	×	×	$√$	×	$√$	×	×	$√$
Accurate result	$√$	×	$√$	$√$	$√$	×	×	$√$
Multi-dimension data	$√$	×	$√$	$√$	$√$	×	$√$	$√$
Single server	×	$√$	$√$	$√$	×	$√$	$√$	$√$
One-round interaction	$√$	$√$	$√$	×	$√$	$√$	×	$√$

Tab.1 Comparison between previous works and our scheme

Notation	Description
$D, D ′, D ∗$	Database, encrypted database, transformed databse
$p i, p i ′, p i ∗$	Each data item in $D, D ′, D ∗$
$q, q ′, q ∗$	Query, encrypted query, transformed query
$n$	Size of database
$d$	Dimension of data item and query
$k$	Number of nearest neighbors
$M$	Secret key
$r$	Random values
$Γ$	R-tree index
$d i s ()$	Squared Euclidean distance
$\| \| p \| \| 2$	Squared Euclidean norm of $p$
$α$	Maximum among ${\| \| p i \| \| 2} 1 ≤ i ≤ n$

Tab.2 List of notations.

Fig.1 System model of secure

k

-NN query

Fig.2 An example of an R-tree with four points

Fig.3 Sub-linear secure k-NN query scheme

Dataset size $n$	DBEnc()	TransED()	Index()
$105$	0.85	0.53	8.96
$2 × 105$	1.76	1.06	18.51
$3 × 105$	2.64	1.58	28.82
$4 × 105$	3.48	2.29	37.29
$5 × 105$	4.37	2.86	48.73
$6 × 105$	5.25	3.43	60.04
$7 × 105$	5.72	3.93	70.72
$8 × 105$	6.91	4.28	81.17
$9 × 105$	7.58	5.08	91.95
$106$	8.98	5.41	105.94

Tab.3 Computation cost of stages before

k

-NN query in SBL-ASPE (seconds)

Fig.4 Query time of SBL-ASPE and ASPE. (a) Query time with k = 1; (b) query time with n = 10⁵

Fig.5 Dynamic update time of SBL-ASPE. (a) Running time of inserting a new record; (b) running time on the CS when removing a record

Fig.6 Query time of SBL-ZHT and ZHT. (a) Query time with k = 1; (b) query time with n = 10⁵

Fig.7 Query time of SBL-MRSE and MRSE. (a) Query time with k = 50; (b) query time with n = 3500

1	Z, Shan K, Ren M, Blanton C Wang . Practical secure computation outsourcing: a survey. ACM Computing Surveys, 2019, 51( 2): 31
2	M, Zhang Y, Zhang G Shen . PPDDS: a privacy-preserving disease diagnosis scheme based on the secure Mahalanobis distance evaluation model. IEEE Systems Journal, 2022, 16( 3): 4552–4562
3	D, Zissis D Lekkas . Addressing cloud computing security issues. Future Generation Computer Systems, 2012, 28( 3): 583–592
4	M, Zhang Y, Zhang Y, Jiang J Shen . Obfuscating EVES algorithm and its application in fair electronic transactions in public clouds. IEEE Systems Journal, 2019, 13( 2): 1478–1486
5	R, Barona E A M Anita . 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	M, Zhang Y, Chen J Lin . 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	J, Domingo-Ferrer O, Farràs J, Ribes-González D Sánchez . Privacy-preserving cloud computing on sensitive data: a survey of methods, products and challenges. Computer Communications, 2019, 140−141: 38−60
8	X, Li Y, Zhu J, Wang J Zhang . Efficient and secure multi-dimensional geometric range query over encrypted data in cloud. Journal of Parallel and Distributed Computing, 2019, 131: 44–54
9	Z, Mei H, Zhu Z, Cui Z, Wu G, Peng B, Wu C Zhang . Executing multi-dimensional range query efficiently and flexibly over outsourced ciphertexts in the cloud. Information Sciences, 2018, 432: 79–96
10	N, Cao C, Wang M, Li K, Ren W Lou . Privacy-preserving multi-keyword ranked search over encrypted cloud data. IEEE Transactions on Parallel and Distributed Systems, 2014, 25( 1): 222–233
11	Z, Fu X, Wu Q, Wang K Ren . Enabling central keyword-based semantic extension search over encrypted outsourced data. IEEE Transactions on Information Forensics and Security, 2017, 12( 12): 2986–2997
12	Z, Guan X, Liu L, Wu J, Wu R, Xu J, Zhang Y Li . Cross-lingual multi-keyword rank search with semantic extension over encrypted data. Information Sciences, 2020, 514: 523–540
13	Y, Liu Y, Luo Y, Zhu Y, Liu X Li . Secure multi-label data classification in cloud by additionally homomorphic encryption. Information Sciences, 2018, 468: 89–102
14	D, Zhu H, Zhu X, Liu H, Li F, Wang H, Li D Feng . CREDO: efficient and privacy-preserving multi-level medical pre-diagnosis based on ML-kNN. Information Sciences, 2020, 514: 244–262
15	Y, Yang P, Xiong Q, Huang F Chen . Secure and efficient outsourcing computation on large-scale linear regressions. Information Sciences, 2020, 522: 134–147
16	S, Hu M, Li Q, Wang S S M, Chow M Du . Outsourced biometric identification with privacy. IEEE Transactions on Information Forensics and Security, 2018, 13( 10): 2448–2463
17	Y, Zhu X, Li J, Wang J Li . Cloud-assisted secure biometric identification with sub-linear search efficiency. Soft Computing, 2020, 24( 8): 5885–5896
18	X, Yang H, Zhu F, Wang S, Zhang R, Lu H Li . MASK: efficient and privacy-preserving m-tree based biometric identification over cloud. Peer-to-Peer Networking and Applications, 2021, 14( 4): 2171–2186
19	M, Zhang W, Song J Zhang . 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	Y, Zhu Z, Huang T Takagi . Secure and controllable k-NN query over encrypted cloud data with key confidentiality. Journal of Parallel and Distributed Computing, 2016, 89: 1−12
23	B, Wang Y, Hou M Li . 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	C, Guo S, Su K K R, Choo X Tang . A fast nearest neighbor search scheme over outsourced encrypted medical images. IEEE Transactions on Industrial Informatics, 2021, 17( 1): 514–523
26	A Guttman . 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	B, Wang Y, Hou M Li . 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	N, Cao C, Wang M, Li K, Ren W Lou . Privacy-preserving multi-keyword ranked search over encrypted cloud data. In: Proceedings of 2011 Proceedings IEEE INFOCOM. 2011, 829−837
30	Y, Zhu R, Xu T Takagi . 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	Y, Zhu R, Xu T Takagi . 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	L, Zhou Y, Zhu A Castiglione . Efficient k-NN query over encrypted data in cloud with limited key-disclosure and offline data owner. Computers & Security, 2017, 69: 84–96
33	J, Yuan S Yu . Efficient privacy-preserving biometric identification in cloud computing. In: Proceedings of 2013 Proceedings IEEE INFOCOM. 2013, 2652−2660
34	Q, Wang S, Hu K, Ren M, He M, Du Z Wang . 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	M, Berg O, Cheong M, Kreveld M Overmars . Computational Geometry: Algorithms and Applications. 3rd ed. Berlin: Springer, 2008
37	A, Boldyreva N, Chenette Y, Lee A O’Neill . Order-preserving symmetric encryption. In: Proceedings of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2009, 224−241
38	O Goldreich . Foundations of Cryptography Volume II Basic Applications. Cambridge: Cambridge University Press, 2004
39	B, Wang Y, Hou M, Li H, Wang H, Li F Li . 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	B, Wang Y, Hou M, Li H, Wang H Li . 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	J L Bentley . Multidimensional binary search trees used for associative searching. Communications of the ACM, 1975, 18( 9): 509–517
44	Y, Bachrach Y, Finkelstein R, Gilad-Bachrach L, Katzir N, Koenigstein N, Nice U Paquet . 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	R, Curtmola J, Garay S, Kamara R Ostrovsky . Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19( 5): 895–934
46	W, Sun B, Wang N, Cao M, Li W, Lou Y T, Hou H Li . 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	Z, Xia X, Wang X, Sun Q Wang . 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

[1]

FCS-22401-OF-XL_suppl_1

Download

[1]	Kun WANG, Song WU, Shengbang LI, Zhuo HUANG, Hao FAN, Chen YU, Hai JIN. Precise control of page cache for containers[J]. Front. Comput. Sci., 2024, 18(2): 182102-.
[2]	Ashish SINGH, Abhinav KUMAR, Suyel NAMASUDRA. DNACDS: Cloud IoE big data security and accessing scheme based on DNA cryptography[J]. Front. Comput. Sci., 2024, 18(1): 181801-.
[3]	Jianwei LI, Xiaoming WANG, Qingqing GAN. SEOT: Secure dynamic searchable encryption with outsourced ownership transfer[J]. Front. Comput. Sci., 2023, 17(5): 175812-.
[4]	Sedigheh KHOSHNEVIS. A search-based identification of variable microservices for enterprise SaaS[J]. Front. Comput. Sci., 2023, 17(3): 173208-.
[5]	Changbo KE, Fu XIAO, Zhiqiu HUANG, Fangxiong XIAO. A user requirements-oriented privacy policy self-adaption scheme in cloud computing[J]. Front. Comput. Sci., 2023, 17(2): 172203-.
[6]	Rong ZENG, Xiaofeng HOU, Lu ZHANG, Chao LI, Wenli ZHENG, Minyi GUO. Performance optimization for cloud computing systems in the microservice era: state-of-the-art and research opportunities[J]. Front. Comput. Sci., 2022, 16(6): 166106-.
[7]	Zhengxiong HOU, Hong SHEN, Xingshe ZHOU, Jianhua GU, Yunlan WANG, Tianhai ZHAO. Prediction of job characteristics for intelligent resource allocation in HPC systems: a survey and future directions[J]. Front. Comput. Sci., 2022, 16(5): 165107-.
[8]	Zhangjie FU, Yan WANG, Xingming SUN, Xiaosong ZHANG. Semantic and secure search over encrypted outsourcing cloud based on BERT[J]. Front. Comput. Sci., 2022, 16(2): 162802-.
[9]	Arpita BISWAS, Abhishek MAJUMDAR, Soumyabrata DAS, Krishna Lal BAISHNAB. OCSO-CA: opposition based competitive swarm optimizer in energy efficient IoT clustering[J]. Front. Comput. Sci., 2022, 16(1): 161501-.
[10]	Yao QIN, Hua WANG, Shanwen YI, Xiaole LI, Linbo ZHAI. A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds[J]. Front. Comput. Sci., 2021, 15(5): 155105-.
[11]	Wei ZHENG, Ying WU, Xiaoxue WU, Chen FENG, Yulei SUI, Xiapu LUO, Yajin ZHOU. A survey of Intel SGX and its applications[J]. Front. Comput. Sci., 2021, 15(3): 153808-.
[12]	Najme MANSOURI, Mohammad Masoud JAVIDI, Behnam Mohammad Hasani ZADE. Hierarchical data replication strategy to improve performance in cloud computing[J]. Front. Comput. Sci., 2021, 15(2): 152501-.
[13]	Jiayang LIU, Jingguo BI, Mu LI. Secure outsourcing of large matrix determinant computation[J]. Front. Comput. Sci., 2020, 14(6): 146807-.
[14]	Xingyue CHEN, Tao SHANG, Feng ZHANG, Jianwei LIU, Zhenyu GUAN. Dynamic data auditing scheme for big data storage[J]. Front. Comput. Sci., 2020, 14(1): 219-229.
[15]	Meysam VAKILI, Neda JAHANGIRI, Mohsen SHARIFI. Cloud service selection using cloud service brokers: approaches and challenges[J]. Front. Comput. Sci., 2019, 13(3): 599-617.

Viewed

Full text

Abstract

Cited

Shared

Discussed