Privacy Protection Scheme Supporting Interval Query for LBS Outsourced Data

doi:10.3969/j.issn.1671-1122.2021.03.004

Abstract

Abstract:

With the rapid development of cloud computing technology, more and more LBS services are being outsourced to the cloud to reduce local computing and storage costs. However, cloud servers are generally considered to be a semi-trusted entity in outsourced environment, the data security of LBS providers and the personal privacy of users will face new security challenges. In view of the fact that the absence of interval query and sufficient privacy protection in the existing LBS data outsourcing using cloud computing, a LBS interval query scheme with privacy protection features is proposed. Asymmetric scalar-product-preserving encryption and public key searchable encryption are used to encrypt LBS coordinates and point interest keywords to realize the confidentiality of LBS data and the user query mode. Lightweight matrix computing enables users to accurately obtain LBS data without revealing query intervals. In terms of new user registration, the bilinear pairing operation structure is adopted to realize user identity authentication. The performance analysis demonstrates that the proposed scheme has some advantages over existing similar schemes.

Key words: privacy protection, location-based service, interval query, outsourcing computing

CLC Number:

TP309

ZHOU Yousheng, WANG Ming, LIU Yuanni. Privacy Protection Scheme Supporting Interval Query for LBS Outsourced Data[J]. Netinfo Security, 2021, 21(3): 26-36.

Figures/Tables 8

符号	符号说明
$<>$	内积运算符
${{M}_{1}},{{M}_{2}}$	可逆矩阵
${{O}_{o}}$	$l-2$ 维向量
$b$	长度为 $l$ 的比特串
$\{({{x}_{i}},{{y}_{i}}),{{W}_{i}},{{\alpha }_{i}}\}$	第 $i$ 条POI数据
$\{({{x}_{u}},{{y}_{u}}),R\}$	用户坐标为 $({{x}_{u}},{{y}_{u}})$ 且查询半径为R的圆形区域
$[{{\partial }_{1}},{{\partial }_{2}}]$	用户所查询的POI区间属性范围
$lo{{c}_{\partial }},lo{{c}_{-1}}$	POI中区间属性值I和数字-1在l维向量中的位置
$r,{{r}_{u}},\text{ }r\prime ,\alpha$	随机数
$\left\{ S{{K}_{L}},P{{K}_{L}} \right\}$	LSP公私钥对
$\left\{ S{{K}_{\text{S}}},P{{K}_{S}} \right\}$	云服务器公私钥对
$\left\{ S{{K}_{u}},P{{K}_{u}} \right\}$	用户公私钥对

符号	定义
$N$	LBS数据数量
${{T}_{e}}$	群上一次模幂运算时间开销
${{T}_{m}}$	群上一次模幂乘法运算时间开销
${{T}_{p}}$	双线性映射操作时间开销

阶段	LBS加密数据	陷门生成	数据检索
文献[20]方案	$2N{{T}_{e}}$	$2{{T}_{e}}$	$2N{{T}_{p}}$
文献[21]方案	$N\left( 6{{T}_{e}}+2{{T}_{m}} \right)$	$4{{T}_{e}}$	$lo{{g}_{N}}\left( 5{{T}_{m}}+2{{T}_{p}} \right)$
文献[26]方案	$N\left( {{T}_{p}}+{{T}_{e}} \right)$	$2{{T}_{e}}$	$2N({{T}_{p}}+{{T}_{m}})$
本文方案	$N\left( 2{{T}_{m}}+{{T}_{p}} \right)$	$3{{T}_{m}}$	$N\left( {{T}_{m}}+2{{T}_{p}} \right)$

References 26

[1]	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.
[2]	PENG Tao, LIU Qin, MENG Dacheng, et al. Collaborative Trajectory Privacy Preserving Scheme in Location-based Services[J]. Information Sciences, 2017,387(5):165-179.
[3]	SHAO Jun, LU Rongxing, LIN Xiaodong. FINE: A Fine-grained Privacy-preserving Location-based Service Framework for Mobile Devices [C]//IEEE. IEEE INFOCOM 2014-IEEE Conference on Computer Communications. April 27-May 2, 2014, Toronto, Canada. New York: IEEE, 2014: 244-252.
[4]	JIANG Hongbo, ZHAO Ping, WANG Chen. RobLoP: Towards Robust Privacy Preserving Against Location Dependent Attacks in Continuous LBS Queries[J]. IEEE/ACM Transactions on Networking, 2018,26(2):1018-1032.
[5]	BERESFORD A R, STAJANO F. Location Privacy in Pervasive Computing[J]. IEEE Pervasive Computing, 2003,2(1):46-55.
[6]	HWANG R H, HSUEH Y L, CHUNG H W. A Novel Time-obfuscated Algorithm for Trajectory Privacy Protection[J]. IEEE Transactions on Services Computing, 2013,7(2):126-139.
[7]	LI Lichun, LU Rongxing, HUANG Cheng. EPLQ: Efficient Privacy-preserving Location-based Query over Outsourced Encrypted Data[J]. IEEE Internet of Things Journal, 2015,3(2):206-218.
[8]	BERESFORD A R, STAJANO F. Location Privacy in Pervasive Computing[J]. IEEE Pervasive Computing, 2003 ( 1):46-55.
[9]	PALANISAMY B, LIU Ling. Attack-resilient Mix-zones over Road Networks: Architecture and Algorithms[J]. IEEE Transactions on Mobile Computing, 2014,14(3):495-508.
[10]	SUN Yipin, ZHANG Bofeng, ZHAO Baokang, et al. Mix-zones Optimal Deployment for Protecting Location Privacy in VANET[J]. Peer-to-Peer Networking and Applications, 2015,8(6):1108-1121.
[11]	KIDO H, YANAGISAWA Y, SATOH T. An Anonymous Communication Technique Using Dummies for Location-based Services [C]//ICPS ‘05. Proceedings. International Conference on Pervasive Services, July 11-14, 2005, Santorini, Greece. Piscataway: IEEE, 2005: 88-97.
[12]	YIU M L, JENSEN C S, HUANG Xuegang, et al. SpaceTwist: Managing the Trade-offs among Location Privacy, Query Performance, and Query Accuracy in Mobile Services [C]//IEEE. 2008 IEEE 24th International Conference on Data Engineering. April 7-12, 2008, Cancun, Mexico. Los Alamitos: IEEE, 2008: 366-375.
[13]	ZHAO Dapeng, JIN Yuanyuan, ZHANG Kai, et al. EPLA: Efficient Personal Location Anonymity[J]. GeoInformatica, 2018,22(1):29-47.
[14]	Vu, Khuong, ZHENG Rong, GAO Jie. Efficient Algorithms for K-anonymous Location Privacy in Participatory Sensing [C]//IEEE. 2012 Proceedings IEEE INFOCOM, March 25-30, 2012, Orlando, FL, USA. New York: IEEE, 2012: 2399-2407.
[15]	GEDIK B, LIU Ling. Protecting Location Privacy with Personalized K-anonymity: Architecture and Algorithms[J]. IEEE Transactions on Mobile Computing, 2007,7(1):1-18.
[16]	NIU Ben, LI Qinghua, ZHU Xiaoyan, et al. Achieving K-anonymity in Privacy-aware Location-based Services [C]//IEEE INFOCOM 2014-IEEE Conference on Computer Communications. April 27-May 2, 2014, Toronto, Canada. New York: IEEE, 2014: 754-762.
[17]	CHEN Jing, HE Kun, YUAN Quan, 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.
[18]	ZHU Hui, LIU Fen, LI Hui. Efficient and Privacy-preserving Polygons Spatial Query Framework for Location-based Services[J]. IEEE Internet of Things Journal, 2016,4(2):536-545. doi: 10.1109/JIOT.2016.2553083 URL
[19]	ZHANG Shaobo, WANG Guojun, BHUIYAN M Z A, et al. A Dual Privacy Preserving Scheme in Continuous Location-based Services[J]. IEEE Internet of Things Journal, 2018,5(5):4191-4200. doi: 10.1109/JIoT.6488907 URL
[20]	YANG Xue, YIN Fan, TANG Xiaohu. A Fine-grained and Privacy-preserving Query Scheme for Fog Computing-enhanced Location-based Service[EB/OL]. https://www.mdpi.com/1424-8220/17/7/1611, 2017-05-31.
[21]	ZHU Hui, LU Rongxing, HUANG Cheng, et al. An Efficient Privacy-preserving Location-based Services Query Scheme in Outsourced Cloud[J]. IEEE Transactions on Vehicular Technology, 2015,65(9):7729-7739. doi: 10.1109/TVT.2015.2499791 URL
[22]	ZENG Ming, ZHANG Kai, CHEN Jie, et al. P3GQ: A Practical Privacy-preserving Generic Location-based Services Query Scheme[J]. Pervasive and Mobile Computing, 2018,51:56-72.
[23]	KARRAS P, NIKITIN A, SAAD M, et al. Adaptive Indexing over Encrypted Numeric Data [C]//ACM. Proceedings of the 2016 International Conference on Management of Data, June 26-July 1, 2016, San Francisco California, USA. New York: ACM, 2016: 171-183.
[24]	XU Zhou, LIN Yaping, SANDOR V K A, et al. A Lightweight Privacy and Integrity Preserving Range Query Scheme for Mobile Cloud Computing[J]. Computers & Security, 2019,84(7):318-333.
[25]	WONG W K, CHEUNG D W, KAO B, et al. Secure KNN Computation on Encrypted Databases [C]//ACM. Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. June 29-July 2, 2009, Providence Rhode Island USA. New York: ACM, 2009: 139-152.
[26]	OU LU, YIN Hui, QIN Zheng, et al. An Efficient and Privacy-preserving Multiuser Cloud-Based LBS Query Scheme[J]. Security & Communication Networks, 2018,2018(3):1-11.

	查询隐私	位置隐私	地理范围查询	关键词查询	区间属性查询	用户访问控制
文献[20]方案	√	√	√	√	×	×
文献[21]方案	√	√	√	×	×	×
文献[26]方案	√	√	√	√	×	√
本文方案	√	√	√	√	√	√