Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (11): 400-417.doi: 10.11896/jsjkx.230900158

• Information Security • Previous Articles    

Multi-type K-nearest Neighbor Query Scheme with Mutual Privacy-preserving in Road Networks

ZENG Congai1,2,3, LIU Yali1,2,3, CHEN Shuyi1,2,3, ZHU Xiuping1,2,3, NING Jianting4   

  1. 1 College of Computer Science and Technology,Jiangsu Normal University,Xuzhou,Jiangsu 221116,China
    2 Guangxi Key Laboratory of Cryptography and Information Security,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China
    3 Henan Key Laboratory of Network Cryptography Technology,Zhengzhou 450001,China
    4 Fujian Provincial Key Laboratory of Network Security and Cryptology,Fujian Normal University,Fuzhou 350007,China
  • Received:2023-09-27 Revised:2023-11-11 Online:2024-11-15 Published:2024-11-06
  • About author:ZENG Congai,born in 1999,postgra-duate.Her main research interests include Internet of Vehicles security and location-based service privacy-preserving.
    LIU Yali,born in 1981,Ph.D,professor,master’s supervisor, is a senior member of CCF(No.95313S).Her main research interests include information security,Internet of Things security and privacy-preserving technology,blockchain security and privacy,vehicular ad hoc networks,cryptographic algorithms and protocols as well as their applications in Internet of Things and mobile communication.
  • Supported by:
    National Natural Science Foundation of China(61702237,61972094,62032005),Science and Technology Planning Foundation of Xuzhou City(KC22052),Opening Foundation of Guangxi Key Laboratory of Cryptography and Information Security(Guilin University of Electronic Technology)(GCIS202114),Opening Foundation of Henan Key Laboratory of Network Cryptography Technology(LNCT2021-A07),Opening Foundation of Fujian Provincial Key Laboratory of Network Security and Cryptology Research Fund(Fujian Normal University)(NSCL-KF2021-04),Postgraduate Research & Practice Innovation Program of Jiangsu Normal University(2022XKT1545,2021XKT1387,2021XKT1396),Cooperative Education Project of the Ministry of Education(202101374001),Natural Science Foundation of Jiangsu Province(BK20150241),Special Foundation of Promoting Science and Technology Innovation of Xuzhou City(KC18005),Natural Science Foundation of the Higher Education Institutions of Jiangsu Province(14KJB520010) and Jiangsu Provincial Government Scholarship for Overseas Studies.

PDF (PC)

242

Abstract: In the Internet of vehicles scenario,existing location-based service privacy-preserving schemes have issues such as not supporting parallel query of multi-type K-nearest neighbor points of interest,difficulty to protect the privacy of both the in-vehicle users and the location-based service provider(LBSP),and unable to resist malicious attacks.In order to solve the above issues,a multi-type K-nearest neighbor query scheme with mutual privacy-preserving in road networks,named as MTKNN-MPP is proposed.By applying the improved k-out-of-n oblivious transfer protocol to the K-nearest neighbor query scheme,it is realized that multi-type K-nearest neighbor points of interest can be queried at a time while protecting the privacy of the query content of in-vehicle user and the privacy of the points of interest information of LBSP.The addition of the onboard unit caching mechanism reduces computational cost and communication overhead.The security analysis shows that the MTKNN-MPP scheme can effectively protect the location privacy of in-vehicle users,query content privacy of in-vehicle users,and the privacy of points of interest information of LBSP,which ensures the anonymity of the vehicle’s identity and can resist malicious attacks such as collusion attacks,replay attacks,inference attacks,and man-in-the-middle attacks.Performance evaluation shows that compared with the existing typical K-nearest neighbor query schemes,the MTKNN-MPP scheme has higher security and the query latency in single-type K-nearest neighbor query and multi-type K-nearest neighbor query is reduced by 43.23%~93.70% and 81.07%~93.93%,respectively.

Key words: Location-based service, Mutual privacy-preserving, K-nearest neighbor query, Oblivious transfer protocol, Internet of vehicles, Multi-type

CLC Number: 

  • TP309
[1] SONG T,LI X H,LI H,et al.Overview of Research on Security Encryption Authentication Technology of IoV in Big Data Era[J].Computer Science,2022,49(4):340-353.
[2] DUAN W,GU J,WEN M,et al.Emerging technologies for 5G-IoV networks:applications,trends and opportunities[J].IEEE Network,2020,34(5):283-289.
[3] TU S P,ZHANG L,LIU X P.Double Dummy Location Selection Algorithm Based on Behavior Correlation[J].Computer Science,2023,50(5):348-354.
[4] NI W W,FENG Z G,YAN D.Location Privacy Preserving Nea-rest Neighbor Query Method Based on Circle Distribution on Road Networks[J].Chinese Journal of Computers,2020,43(8):1385-1396.
[5] CUI J,CHEN X F,ZHANG J,et al.Bus Cache-Based Location Privacy Protection Scheme in the Internet of Vehicles[J].Journal on Communications,2021,42(7):150-161.
[6] LIU B,ZHOU W,ZHU T,et al.Silence is golden:enhancingprivacy of location-based services by content broadcasting and active caching in wireless vehicular networks[J].IEEE Transactions on Vehicular Technology,2016,65(12):9942-9953.
[7] CHEN S Y,LIU Y L,LIN C L,et al.Lightweight Verifiable Group Authentication Scheme for the Internet of Things[J].Acta Electronica Sinica,2022,50(4):990-1001.
[8] HU L,QIAN Y,CHEN M,et al.Proactive cache-based location privacy preserving for vehicle networks[J].IEEE Wireless Communications,2018,25(6):77-83.
[9] ZHOU C L,CHEN Y H,TIAN H,et al.Location Privacy and Query Privacy Preserving Method for K-nearest Neighbor Query in Road Networks[J].Journal of Software,2020,31(2):471-492.
[10] YADAV V K,VERMA S,VENKATESAN S.Linkable privacy-preserving scheme for location-based services[J].IEEE Tran-sactions on Intelligent Transportation Systems,2021,23(7):7998-8012.
[11] LIU S S,LIU A,YAN Z,et al.Efficient LBS queries with mu-tual privacy preservation in IoV[J].Vehicular Communications,2019,16(2019):62-71.
[12] NI W W,LI N Q,LIU J Q.Voronoi-R*-Based Privacy-Preserving k Nearest Neighbor Query over Road Networks[J].Journal of Software,2019,30(12):3782-3797.
[13] YI X,PAULET R,BERTINO E,et al.Practical approximate k nearest neighbor queries with location and query privacy[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(6):1546-1559.
[14] PAILLIER P.Public-Key Cryptosystems Based on CompositeDegree Residuosity Classes[C]//International Conference on the Theory and Applications of Cryptographic Techniques(EUROCRYPT).Berlin:Springer Press,1999:223-238.
[15] ZHOU C L,MA C G,YANG S T.Research of LBS Privacy Preserving Based on Sensitive Location Diversity[J].Journal on Communications,2015,36(4):129-140.
[16] CHEN J,HE K,YUAN Q,et al.Blind filtering at third parties:An efficient privacy-preserving framework for location-based services[J].IEEE Transactions on Mobile Computing,2018,17(11):2524-2535.
[17] PAULET R,KAOSAR M G,YI X,et al.Privacy-preserving and content-protecting location based queries[J].IEEE Transactions on Knowledge and Data Engineering,2013,26(5):1200-1210.
[18] YADAV V K,ANDOLA N,VERMA S,et al.A survey of obli-vious transfer protocol[J].ACM Computing Surveys(CSUR),2022,54(10):1-37.
[19] NI W,GU M,CHEN X.Location privacy-preserving k nearestneighbor query under user’s preference[J].Knowledge-Based Systems,2016,103:19-27.
[20] JANNATI H,BAHRAK B.An oblivious transfer protocol based on elgamal encryption for preserving location privacy[J].Wireless Personal Communications,2017,97(2):3113-3123.
[21] YADAV V K,VERMA S,VENKATESAN S.Efficient and secure location-based services scheme in VANET[J].IEEE Tran-sactions on Vehicular Technology,2020,69(11):13567-13578.
[22] LIU J K,WEI V K,WONG D S.Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups[C]//Australasian Conference on Information Security and Privacy(ACISP).Berlin:Springer Press,2004:325-335.
[23] BETHENCOURT J,SAHAI A,WATERS B.Ciphertext-Policy Attribute-Based Encryption[C]//2007 IEEE Symposium on Security and Privacy(S&P).Piscataway:IEEE Press,2007:321-334.
[24] CUI N N,YANG X,WANG B,et al.SVkNN:Efficient Secureand Verifiable k-Nearest Neighbor Query on the Cloud Platform[C]//2020 IEEE 36th International Conference on Data Engineering(ICDE).Piscataway:IEEE Press,2020:253-264.
[25] CUI N N,QIAN K,CAI T T,et al.Towards multi-user,secure,and verifiable kNN query in cloud database[J].IEEE Transactions on Knowledge and Data Engineering,2023,35(9):9333-9349.
[26] MENEZES A J,VANSTONE S A.Elliptic curve cryptosystems and their implementation[J].Journal of Cryptology,1993,6(4):209-224.
[27] SONG W,SHI C L,SHEN Y,et al.Select the Best for Me:Privacy-Preserving Polynomial Evaluation Algorithm over Road Network[C]//International Conference on Database Systems for Advanced Applications(DASFAA).Cham:Springer Press,2019:281-297.
[28] WANG J,WU L B,LUO M,et al.Secure and Efficient Two-Party ECDSA Signature Scheme[J].Journal on Communications,2021,42(2):12-25.
[29] FAN Q,HE D B,LUO M,et al.Ring Signature Schemes Based on SM2 Digital Signature Algorithm[J].Journal of Cryptologic Research,2021,8(4):710-723.
[30] MU Y,ZHANG J,VARADHARAJAN V.M out of n ObliviousTransfer[C]//Australasian Conference on Information Security and Privacy(ACISP).Berlin:Springer Press,2002:395-405.
[31] TZENG W G.Efficient 1-out-n Oblivious Transfer Schemes[C]//International Workshop on Public Key Cryptography(PKC).Berlin:Springer Press,2002:159-171.
[32] HAZAY C,LINDELLl Y.Efficient Secure Two-Party Proto-cols:Techniques and Constructions[M].Springer Science & Business Media,2010.
[33] ZHANG Z Y,LIU X Y,LI W H,et al.Efficient and Cooperative Secure Two-Party Computation Based on Authenticated Garbled Circuit[J].Chinese Journal of Computers,2022,45(11):2433-2455.
[34] LI F F.Real Datasets for Spatial Databases[DB/OL].[2022-11-16].https://www.cs.utah.edu/lifeifei/SpatialDataset.htm.
[35] LI F F,CHENG D H,HADJIELEFTHERIOU M,et al.OnTrip Planning Queries in Spatial Databases[C]//International Symposium on Spatial and Temporal Databases(SSTD).Berlin:Springer Press,2005:273-290.
[36] CUI Y Q,CAO L,ZHANG X Y,et al.Ring Signature Based on Lattice and VANET Privacy Preservation[J].Chinese Journal of Computers,2019,42(5):980-992.
[37] CHEN S Y,LIU Y L,NING J T,et al.BASRAC:An efficient batch authentication scheme with rule-based access control for VANETs[J].Vehicular Communications,2023,40:100575.
[38] LAN X W.Optimization of ECC computation algorithms andtheir application in SM2 implementation[D].Chengdu:University of Electronic Science and Technology of China,2019.
[39] FENG Q.Research on data privacy preservation technologies using secure multi-party computation[D].Hubei:Wuhan University of China,2021.
[40] BELLARE M,MICALI S.Non-Interactive Oblivious Transferand Applications[C]//Conference on the Theory and Application of Cryptology(CRYPTO).Berlin:Springer Press,1989:547-557.
[41] XIE X R.Computer networks[M].Beijing:Publishing House of Electronics Industry,2021.
[1] ZHAO Hui, PENG Jianyou, QIN Yulin, HAN Lili. Construction of Internet of Vehicles Covert Channel Based on Websocket Protocol [J]. Computer Science, 2024, 51(8): 364-370.
[2] LI Fengyun, CHEN Mingming, WANG Lin, LI Peng , JU Xianyin. Study on Trust Management Mechanism of Internet of Vehicles Based on Blockchain [J]. Computer Science, 2024, 51(4): 381-387.
[3] XUE Jianbin, YU Bowen, XU Xiaofeng, DOU Jun. Queueing Theory-based Joint Optimization of Communication and Computing Resources in Edge Computing Networks [J]. Computer Science, 2024, 51(11A): 240100103-9.
[4] LIN Xinyu, YAO Zewei, HU Shengxi, CHEN Zheyi, CHEN Xing. Task Offloading Algorithm Based on Federated Deep Reinforcement Learning for Internet of Vehicles [J]. Computer Science, 2023, 50(9): 347-356.
[5] GUO Nan, SONG Xiaobo, ZHUANG Luyuan, ZHAO Cong. Anonymous Batch Authentication Scheme in Internet of Vehicles for WAVE Security Services [J]. Computer Science, 2023, 50(4): 308-316.
[6] ZHANG Xuejun, YANG Yixing, LI Jiale, TIAN Feng, HUANG Haiyan, HUANG Shan. Dummy Location Generation Algorithm Against Side Information Inference Attack [J]. Computer Science, 2023, 50(11A): 221000036-9.
[7] SHAO Zi-hao, YANG Shi-yu, MA Guo-jie. Foundation of Indoor Information Services:A Survey of Low-cost Localization Techniques [J]. Computer Science, 2022, 49(9): 228-235.
[8] CHEN Jing, WU Ling-ling. Mixed Attribute Feature Detection Method of Internet of Vehicles Big Datain Multi-source Heterogeneous Environment [J]. Computer Science, 2022, 49(8): 108-112.
[9] SONG Tao, LI Xiu-hua, LI Hui, WEN Jun-hao, XIONG Qing-yu, CHEN Jie. Overview of Research on Security Encryption Authentication Technology of IoV in Big Data Era [J]. Computer Science, 2022, 49(4): 340-353.
[10] ZHANG Xue-jun, YANG Hao-ying, LI Zhen, HE Fu-cun, GAI Ji-yang, BAO Jun-da. Differentially Private Location Privacy-preserving Scheme withSemantic Location [J]. Computer Science, 2021, 48(8): 300-308.
[11] TANG Liang, LI Fei. Research on Forecasting Model of Internet of Vehicles Security Situation Based on Decision Tree [J]. Computer Science, 2021, 48(6A): 514-517.
[12] YU Jian-ye, QI Yong, WANG Bao-zhuo. Distributed Combination Deep Learning Intrusion Detection Method for Internet of Vehicles Based on Spark [J]. Computer Science, 2021, 48(6A): 518-523.
[13] YU Tian-qi, HU Jian-ling, JIN Jiong, YANG Jian-feng. Mobile Edge Computing Based In-vehicle CAN Network Intrusion Detection Method [J]. Computer Science, 2021, 48(1): 34-39.
[14] WANG Chun-dong, LUO Wan-wei, MO Xiu-liang, YANG Wen-jun. Survey on Mutual Trust Authentication and Secure Communication of Internet of Vehicles [J]. Computer Science, 2020, 47(11): 1-9.
[15] LIU Dan. Fog Computing and Self-assessment Based Clustering and Cooperative Perception for VANET [J]. Computer Science, 2020, 47(10): 55-62.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.