路网环境下基于伪随机置换的LBS隐私保护方法研究

doi:10.11959/j.issn.1000-436x.2017120

Abstract

Abstract:

A method of privacy preservation based on pseudorandom permutation was put forward for the issues of location privacy and query content privacy.Firstly,the distribution information of points of interest (PoI) based on the vertexes in the road network was organized,each single road vertex was taken as the foundational processing object.Based on the pseudorandom permutation,a permutation scheme of the point-of-interest records at the LBS server's end was put forward,a 32-bit random seed was adopted to generate a permuted table in the scheme,and the point-of-interest records were encrypted and permuted according to the table.These processed records were stored in the LBS database.Then a trusted intermediate server,replacing of the user,issued a query request with a record number instead of the query content to the LBS server.The LBS server could not determine which kind of PoI the user was interested in or which road section the user was locating on,and therefore the scheme achieved private information retrieval.Finally,the efficiency in the metrics of query accuracy,communication overhead and processing time was also analyzed.By the performance analysis and extensive experiments,the proposed scheme is proved to be location untraceable and query content uncorrelation.

Key words: location-based service, privacy preservation, K nearest neighbor query, untraceable, uncorrelation

CLC Number:

TP311

Chang-li ZHOU,Hui TIAN,Chun-guang MA,Song-tao YANG. Research on LBS privacy preservation based on pseudorandom permutation in road network[J]. Journal on Communications, 2017, 38(6): 19-29.

Figures/Tables 16

顶点记录号	路网顶点（锚点）	兴趣点记录号	兴趣点类型	K_max近邻兴趣点集	兴趣点对应描述信息
		1	医院	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$	${i n f_{1}, i n f_{2}, \dots, i n f_{K_{\max}}}$
$R E C_{v_{1}}$	v₁(锚点1)	2	银行	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$	${i n f_{1}, i n f_{2}, \dots, i n f_{K_{\max}}}$
		3	宾馆	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$	${i n f_{1}, i n f_{2}, \dots, i n f_{K_{\max}}}$
		4	加油站	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$	${i n f_{1}, i n f_{2}, \dots, i n f_{K_{\max}}}$
		1	医院	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$	${i n f_{1}, i n f_{2}, \dots, i n f_{K_{\max}}}$
$R E C_{v_{2}}$	v₂(锚点2)	2	银行	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$	${i n f_{1}, i n f_{2}, \dots, i n f_{K_{\max}}}$
		3	宾馆	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$	${i n f_{1}, i n f_{2}, \dots, i n f_{K_{\max}}}$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$

路网顶点( 锚点)	兴趣点标号	兴趣点类型	K_max近邻兴趣点集
	1	医院	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$
v₁ (锚点1)	2	银行	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$
	3	宾馆	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$
	4	加油站	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$
	1	医院	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$
v₂ (锚点2)	2	银行	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$
	3	宾馆	${l o c_{1}, l o c_{2}, \dots, l o c_{K_{\max}}}$
$⋮$	$⋮$	$⋮$	$⋮$

References 17

[1]	GHINITA G . Privacy for location-based services[J]. Synthesis Lectures on Information Security,Privacy,＆Trust, 2013,4(1): 1-85.
[2]	张学军, 桂小林, 伍忠东 . 位置服务隐私保护研究综述[J]. 软件学报, 2015,9: 2373-2395.
	ZHANG X J , GUI X L , WU Z D . Privacy preservation for location-based services:a survey[J]. Journal of Software, 2015,9: 2373-2395.
[3]	王宇航, 张宏莉, 余翔湛 . 移动互联网中的位置隐私保护研究[J]. 通信学报, 2015,36(9): 230-243.
	WANG Y H , ZHANG H L , YU X Z . Research on location privacy in mobile internet[J]. Journal on Communications, 2015,36(9): 230-243.
[4]	潘晓, 郝兴, 孟小峰 . 基于位置服务中的连续查询隐私保护研究[J]. 计算机研究与发展, 2010,47(1): 121-129.
	PAN X , HAO X , MENG X F . Privacy preserving towards continuous query in location-based services[J]. Journal of Computer Research and Development, 2010,47(1): 121-129.
[5]	高胜, 马建峰, 姚青松 ,等. LBS 中面向协同位置隐私保护的群组最近邻查询[J]. 通信学报, 2015,36(3): 146-154.
	GAO S , MA J F , YAO Q S ,et al. Towards cooperation location privacy-preserving group nearest neighbor queries in LBS[J]. Journal on Communications, 2015,36(3): 146-154.
[6]	NI W , GU M , CHEN X . Location privacy-preserving k nearest neighbor query under user’s preference[J]. Knowledge-Based Systems, 2016,103: 19-27.
[7]	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.
[8]	PAN X , XU J , MENG X . Protecting location privacy against location-dependent attacks in mobile services[J]. IEEE Transactions on Knowledge and Data Engineering, 2012,24(8): 1506-1519.
[9]	NIU B , ZHANG Z , LI X ,et al. Privacy-area aware dummy generation algorithms for location-based services[C]// 2014 IEEE International Conference on Communications (ICC). 2014: 957-962.
[10]	MAN L Y , JENSEN C.S , HUANG X G ,et al. SpaceTwist:managing the trade-offs among location privacy,query performance,and query accuracy in mobile services[C]// IEEE 24th International Conference on Data Engineering. 2008: 366-375.
[11]	GONG Z , SUN G Z , XIE X . Protecting privacy in location-based services using k-anonymity without cloaked region[C]// Mobile Data Management (MDM),2010 Eleventh International Conference. 2010: 366-371.
[12]	黄毅, 霍峥, 孟小峰 . CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法[J]. 计算机学报, 2011,34(10): 1976-1985.
	HANG Y , HUO Z , MENG X F . CoPrivacy:a collaborative location privacy-preserving method without cloaking region[J]. Chinese Journal of Computers, 2011,34(10): 1976-1985.
[13]	马春光, 周长利, 杨松涛 ,等. 基于 Voronoi 图预划分的 LBS 位置隐私保护方法[J]. 通信学报, 2015,36(5): 5-16.
	MA C G , ZHOU C L , YANG S T ,et al. Location privacy-preserving method in LBS based on Voronoi division[J]. Journal on Communications, 2015,36(5): 5-16.
[14]	周长利, 马春光, 杨松涛 . 基于敏感位置多样性的LBS位置隐私保护方法研究[J]. 通信学报, 2015,36(4): 129-140.
	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.
[15]	YI X , PAULET R , BERTINO E ,et al. Practical k nearest neighbor queries with location privacy[C]// 2014 IEEE 30th International Conference on Data Engineering. IEEE, 2014: 640-651.
[16]	MOURATIDIS K , YIU M L . Shortest path computation with no information leakage[J]. The VLDB Endowment, 2012,5(8): 692-703.
[17]	杨松涛, 马春光, 周长利 . 面向LBS的隐私保护模型及方案[J]. 通信学报, 2014,35(8): 116-124.
	YANG S T , MA C G , ZHOU C L . LBS-oriented location privacy protection model and scheme[J]. Journal on Communications, 2014,35(8): 116-124.

Metrics

Recommended 0

No Suggested Reading articles found!

参数名	取值范围	默认值
用户数量U	50 000,300 000]	100 000
用户查询兴趣点数K	10,60]	20
用户位置更新频率f/s	5,30]	15
兴趣点缓存时长T_k /h	—	6
固定锚点使用率r c	20%,100%]	90%
平均路段长度S/m	200,2 000]	1 000

Research on LBS privacy preservation based on pseudorandom permutation in road network

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 17

Related Articles 15

Metrics

Recommended 0

[1]	Hongtao LI, Xiaoyu REN, Jie WANG, Jianfeng MA. Continuous location privacy protection mechanism based on differential privacy [J]. Journal on Communications, 2021, 42(8): 164-175.
[2]	Jie CUI, Xuefeng CHEN, Jing ZHANG, Lu WEI, Hong ZHONG. Bus cache-based location privacy protection scheme in the Internet of vehicles [J]. Journal on Communications, 2021, 42(7): 150-161.
[3]	Chen FANG, Yuanbo GUO, Yifeng WANG, Yongjin HU, Jiali MA, Han ZHANG, Yangyang HU. Edge computing privacy protection method based on blockchain and federated learning [J]. Journal on Communications, 2021, 42(11): 28-40.
[4]	Zhu WANG,Kun HE,Xinyu WANG,Ben NIU,Fenghua LI. Traffic characteristic based privacy leakage assessment scheme for Android device [J]. Journal on Communications, 2020, 41(2): 155-164.
[5]	Weihao LI,Jin CAO,Hui LI. Privacy self-correlation privacy-preserving scheme in LBS [J]. Journal on Communications, 2019, 40(5): 57-66.
[6]	Yuanzhi YAO,Feng WANG,Wenbo YAN,Nenghai YU. Image privacy preservation scheme based on QR code and reversible visible watermarking [J]. Journal on Communications, 2019, 40(11): 65-75.
[7]	Yatao YANG,Xinguang HAN,Jierun HUANG,Yang ZHAO. Bidirectional authentication key agreement protocol supporting identity’s privacy preservation based on RLWE [J]. Journal on Communications, 2019, 40(11): 180-186.
[8]	Weihao LI,Sheng DING,Jiajie MENG,Hui LI. Spatio-temporal aware privacy-preserving scheme in LBS [J]. Journal on Communications, 2018, 39(5): 134-142.
[9]	Xiaoying ZHANG,Hui PENG,Hong CHEN. State-of-the-art survey of privacy-preserving data aggregation in wireless sensor networks [J]. Journal on Communications, 2018, 39(10): 130-142.
[10]	Zhen-peng LIU,Xuan ZHAO,Ya-wei DONG,Bin ZHANG. Improved SpaceTwist privacy protection method based on anchor optimization algorithm [J]. Journal on Communications, 2017, 38(Z1): 32-38.
[11]	Lei ZHANG,Chun-guang MA,Song-tao YANG,Zeng-peng LI. CP-ABE based users collaborative privacy protection scheme for continuous query [J]. Journal on Communications, 2017, 38(9): 76-85.
[12]	Zhuo-xiong PEI,Xing-hua LI,Hai LIU,Kai-yue LEI,Jian-feng MA,Hui LI. Anonymizing region construction scheme based on query range in location-based service privacy protection [J]. Journal on Communications, 2017, 38(9): 125-132.
[13]	Lu-lu LI,Jia-feng HUA,Sheng WAN,Hui ZHU,Feng-hua LI. Achieving efficient location privacy protection based on cache [J]. Journal on Communications, 2017, 38(6): 148-157.
[14]	Jia-hui WANG,Chuan-yi LIU,Bin-xing FANG. Survey on data preserving for the search of internet of things [J]. Journal on Communications, 2016, 37(9): 142-153.
[15]	Hai LIU,Xing-hua LI,Er-meng WANG,Jian-feng MA. Privacy enhancing method for dummy-based privacy protection with continuous location-based service queries [J]. Journal on Communications, 2016, 37(7): 140-150.