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

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

通信学报 ›› 2017, Vol. 38 ›› Issue (6): 19-29.doi: 10.11959/j.issn.1000-436x.2017120

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

周长利¹,田晖¹,马春光²,杨松涛²

¹ 华侨大学计算机科学与技术学院，福建厦门 361021
² 哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨 150001

修回日期:2017-03-27 出版日期:2017-06-25 发布日期:2017-06-30
作者简介:周长利（1985-），男，黑龙江哈尔滨人，博士，华侨大学讲师，主要研究方向为位置隐私保护、网络与信息安全等。|田晖（1982-），男，湖北赤壁人，华侨大学副教授，主要研究方向为网络信息安全、大数据安全与隐私保护、多媒体内容安全等。|马春光（1974-），男，黑龙江双鸭山人，哈尔滨工程大学教授、博士生导师，主要研究方向为密码学、网络与信息安全等。|杨松涛（1972-），男，黑龙江佳木斯人，哈尔滨工程大学副教授，主要研究方向为网络与信息安全、位置隐私保护等。
基金资助:
国家自然科学基金资助项目(61370007);国家自然科学基金资助项目(61472097);国家自然科学基金资助项目(U1405254);国家自然科学基金资助项目(U1536115);福建省高校新世纪优秀人才计划基金资助项目(2014FJ-NCET-ZR06);福建省高校新世纪优秀人才计划基金资助项目(MJK2016-23);福建省自然科学青年基金资助项目(2016J05158);福建省高校杰出青年科研人才培育计划基金资助项目(MJK2015-54);华侨大学科研基金资助项目(15BS412)

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

Chang-li ZHOU¹,Hui TIAN¹,Chun-guang MA²,Song-tao YANG²

¹ School of Computer Science and Technology,Huaqiao University,Xiamen 361021,China
² School of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China

Revised:2017-03-27 Online:2017-06-25 Published:2017-06-30
Supported by:
The National Natural Science Foundation of China(61370007);The National Natural Science Foundation of China(61472097);The National Natural Science Foundation of China(U1405254);The National Natural Science Foundation of China(U1536115);Program for New Century Excellent Talents in Fujian Province University(2014FJ-NCET-ZR06);Program for New Century Excellent Talents in Fujian Province University(MJK2016-23);The Natural Science Foundation for Youths of Fujian Province(2016J05158);Program for Outstanding Youth Scientific and Technological Talents in Fujian Province University(MJK2015-54);Scientific Research Funds of Huaqiao University(15BS412)

摘要/Abstract

摘要：

针对路网连续查询用户的位置隐私和查询内容隐私保护问题，提出一种基于伪随机置换的隐私保护方法。首先，基于路网顶点（锚点）组织兴趣点（PoI）分布信息，以单个路网顶点为基本处理对象，构造基于伪随机置换的LBS服务端兴趣点记录置换方案，该方案以32 bit随机种子生成置换表，并对兴趣点记录进行加密和置换处理后存入数据库；然后，可信中心服务器代理用户以目标类型兴趣点记录号发起查询，LBS服务器无法确定用户真实位置及查询内容，实现了保护隐私的秘密检索；最后，对查询准确性、数据分组量和处理时间进行了对比分析实验，性能分析证明了所提方法具有位置不可追踪性和查询内容不可关联性。

关键词: 基于位置的服务, 隐私保护, K近邻查询, 不可追踪性, 不可关联性

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

中图分类号:

TP311

周长利,田晖,马春光,杨松涛. 路网环境下基于伪随机置换的LBS隐私保护方法研究[J]. 通信学报, 2017, 38(6): 19-29.

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.

图/表 16

图1

图2

表1

LBS数据库中兴趣点存储信息"

顶点记录号	路网顶点（锚点）	兴趣点记录号	兴趣点类型	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}}}$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$

表1

表2

区域内K近邻兴趣点分布索引"

路网顶点( 锚点)	兴趣点标号	兴趣点类型	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}}}$
$⋮$	$⋮$	$⋮$	$⋮$

表2

图3

表3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

参考文献 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.

参数名	取值范围	默认值
用户数量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

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 16

参考文献 17

相关文章 15

Metrics

推荐阅读 0

[1]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[2]	冯涛, 陈李秋, 方君丽, 石建明. 基于本地化差分隐私和属性基可搜索加密的区块链数据共享方案[J]. 通信学报, 2023, 44(5): 224-233.
[3]	夏莹杰, 朱思雨, 刘雪娇. 区块链架构下具有条件隐私的车辆编队跨信任域高效群组认证研究[J]. 通信学报, 2023, 44(4): 111-123.
[4]	胡柏吉, 张晓娟, 李元诚, 赖荣鑫. 支持多功能的V2G网络隐私保护数据聚合方案[J]. 通信学报, 2023, 44(4): 187-200.
[5]	徐明, 张保俊, 伍益明, 应晨铎, 郑宁. 面向网络攻击和隐私保护的多智能体系统分布式共识算法[J]. 通信学报, 2023, 44(3): 117-127.
[6]	余晟兴, 陈钟. 基于同态加密的高效安全联邦学习聚合框架[J]. 通信学报, 2023, 44(1): 14-28.
[7]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[8]	王继锋, 王国峰. 边缘计算模式下密文搜索与共享技术研究[J]. 通信学报, 2022, 43(4): 227-238.
[9]	封化民, 史瑞, 袁峰, 李艳俊, 杨旸. 高效的强隐私保护和可转让的属性票据方案[J]. 通信学报, 2022, 43(3): 63-75.
[10]	于海宁, 张宏莉, 余翔湛, 曲家兴, 葛蒙蒙. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022, 43(11): 1-13.
[11]	彭滔, 钟文韬, 王国军, 罗恩韬, 熊金波, 刘忆宁, Hao Wang. 移动社交网络中面向隐私保护的精确好友匹配[J]. 通信学报, 2022, 43(11): 90-103.
[12]	史瑞, 封化民, 谢惠琴, 史国振, 刘飚, 杨旸. 基于带智能卡的移动终端实现的隐私保护的属性票据方案[J]. 通信学报, 2022, 43(10): 26-41.
[13]	熊金波, 周永洁, 毕仁万, 万良, 田有亮. 边缘协同的轻量级隐私保护分类框架[J]. 通信学报, 2022, 43(1): 127-137.
[14]	晏燕, 丛一鸣, Adnan Mahmood, 盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法[J]. 通信学报, 2022, 43(1): 203-216.
[15]	马立川, 彭佳怡, 裴庆祺, 朱浩瑾. 高效的决策树隐私分类服务协议[J]. 通信学报, 2021, 42(8): 80-89.