计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (11): 400-417.doi: 10.11896/jsjkx.230900158

• 信息安全 • 上一篇    

保护两方隐私的多类型的路网K近邻查询方案

曾聪爱1,2,3, 刘亚丽1,2,3, 陈书仪1,2,3, 朱秀萍1,2,3, 宁建廷4   

  1. 1 江苏师范大学计算机科学与技术学院 江苏 徐州 221116
    2 广西密码学与信息安全重点实验室(桂林电子科技大学) 广西 桂林 541004
    3 河南省网络密码技术重点实验室 郑州 450001
    4 福建省网络安全与密码技术重点实验室(福建师范大学) 福州 350007
  • 收稿日期:2023-09-27 修回日期:2023-11-11 出版日期:2024-11-15 发布日期:2024-11-06
  • 通讯作者: 刘亚丽(liuyali@jsnu.edu.cn)
  • 作者简介:(zengcongai@jsnu.edu.cn)
  • 基金资助:
    国家自然科学基金(61702237,61972094,62032005);徐州市科技计划项目(KC22052);广西密码学与信息安全重点实验室(桂林电子科技大学)研究课题(GCIS202114);河南省网络密码技术重点实验室研究课题(LNCT2021-A07);福建省网络安全与密码技术重点实验室(福建师范大学)开放课题(NSCL-KF2021-04);江苏师范大学研究生科研与实践创新计划项目(2022XKT1545,2021XKT1387,2021XKT1396);教育部产学合作协同育人项目(202101374001);江苏省自然科学基金(BK20150241);徐州市推动科技创新专项资金项目(KC18005);江苏省高校自然科学基金(14KJB520010);江苏政府留学奖学金

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)

274

摘要： 在车联网场景中,现有基于位置服务的隐私保护方案存在不支持多种类型K近邻兴趣点的并行查询、难以同时保护车辆用户和位置服务提供商(Location-Based Service Provider,LBSP)两方隐私、无法抵抗恶意攻击等问题。为了解决上述问题,提出了一种保护两方隐私的多类型的路网K近邻查询方案MTKNN-MPP。将改进的k-out-of-n不经意传输协议应用于K近邻查询方案中,实现了在保护车辆用户的查询内容隐私和LBSP的兴趣点信息隐私的同时,一次查询多种类型K近邻兴趣点。通过增设车载单元缓存机制,降低了计算代价和通信开销。安全性分析表明,MTKNN-MPP方案能够有效地保护车辆用户的位置隐私、查询内容隐私以及LBSP的兴趣点信息隐私,可以保证车辆的匿名性,能够抵抗合谋攻击、重放攻击、推断攻击、中间人攻击等恶意攻击。性能评估表明,与现有典型的K近邻查询方案相比,MTKNN-MPP方案具有更高的安全性,且在单一类型K近邻查询和多种类型K近邻查询中,查询延迟分别降低了43.23%~93.70%,81.07%~93.93%。

关键词: 基于位置的服务, 两方隐私保护, K近邻查询, 不经意传输协议, 车联网, 多类型

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发