第42卷第5期
2021年5月
哈㊀尔㊀滨㊀工㊀程㊀大㊀学㊀学㊀报Journal of Harbin Engineering University
Vol.42ɴ.5
May 2021
杜刚1，张磊1,2
，马春光3
，张国印1
(1.哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001;2.佳木斯大学信息电子技术学院，黑龙江佳木斯
154007;3.山东科技大学计算机科学与工程学院，山东青岛266590)
摘㊀要：针对基于位置服务隐私保护中以索引为主的隐私信息检索策略在处理时间和用户属性保护方面的不足，提出了一种属性基隐私信息检索的位置隐私保护方法㊂该方法基于属性基加密算法结合位置服务的本质特征，通过用户与位置服务器之间的两方秘密计算，完成了零信息泄露的位置服务查询与反馈㊂最后，给出了形式化的安全性分析和性能评估，从理论上证明了所提出方法的有效性与可用性㊂同时，通过与同类算法在隐私保护能力和算法效率方面比较实验，进一步验证了所提出的方法的优越性㊂ 关键词：基于位置服务；隐私保护；索引；隐私信息检索；属性基加密算法；秘密计算；零信息泄露；属性隐藏；形式化证明
DOI :10.11990/jheu.201912032
网络出版地址:http ://wwwki /kcms /detail /23.1390.U.20210220.1512.004.html 中图分类号:TP309.2㊀文献标志码:A㊀文章编号:1006-7043(2021)05-0680-07
Location privacy protection method based on attribute-based
privacy information retrieval
DU Gang 1
,ZHANG Lei 1,2
,MA Chunguang 3
,ZHANG Guoyin 1
(1.College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China;2.College of Information and Electronic Technology,Jiamusi University,Jiamusi 154007,China;3.College of Computer Science and Engineering,Shandong University of Science and Technology,Qingdao 266590,China)
Abstract :Aiming at the shortcomings of index-based privacy information retrieval strategies in location-based service privacy protection in terms of processing time and user attribute protection,this work proposes a location privacy pro-tection method rooted in attribute-based privacy information retrieval.Based on the attribute-based encryption algo-rithm and the essential characteristics of location service,the proposed method can complete the query and feedback of location service with zero information disclosure through the two-party secret calculation between users and location servers.Formal security analysis and performance evaluation are conducted,and the effectiveness and availability of the proposed method are proved theoretically.Meanwhile,the sup
eriority of the proposed method is further verified by comparative experiments on its privacy protection ability and algorithm efficiency and those of similar algorithms.Keywords :location-based service;privacy protection;index;privacy information retrieval;attribute-based encryp-tion algorithm;secret calculation;zero information disclosure;property hiding;formal proof
收稿日期:2019-12-17.网络出版日期:2021-02-20.基金项目：国家自然科学基金项目(61932005,U1936112)；中国博士后
基金项目(2019M661260)；黑龙江省自然科学基金项目(YQ2019F018,LH2019F011).
作者简介：杜刚，男，讲师，博士研究生;
张磊，男，副教授，博士.
通信作者：张磊,E-mail:8213662@163.
㊀㊀随着基于位置服务(location based service,LBS)的广泛应用，越来越多的人们开始关注该服务中的隐私泄露问题[1-2]㊂当前较为普遍的隐私保护方法有泛化[3-4]㊁模糊[5-6]㊁加密[7-8]以及空间变换[9]等，但上述方法都面临同样的问题，即在LBS
服务器提供服务的过程中不可避免地要获知用户的真实意图，进而可根据诸如兴趣点类型㊁查询种类等信息分析获得用户隐私㊂隐私信息检索(private in-formation retrieval,PIR)是应对这种潜在隐私泄露的有效办法[10-11]㊂该方法对LBS 服务器中的数据加密，通过二进制的可计算PIR 和硬件PIR 实现零信息泄露的结果检索㊂Wightman 等[12]根据这一观点，基于经纬度的地理差异，提出了基于地图查询的PIR㊂杨松涛等[13]基于该技术建立了基于位置服务的盲查询方法㊂
但是，由于基于位置服务本身的特性，使得这种
第5期杜刚，等：基于属性基隐私信息检索的位置隐私保护方法
以索引为基础的隐私信息检索在执行过程中需搜寻较大规模的数据条目，这增加了反馈结果的处理时间，影响了服务质量[14]㊂Hu 等[15]提出用分层索引提升索引效率㊂Yi 等[16]则提出了模糊索引的概念㊂通常情况下，基于位置服务是一种针对用户提交信息进行反馈的服务，其反馈结果主要针对用户属性信息获得的查询结果[17-18]㊂因此，使用属性作为索引进行隐私信息检索将会减少处理数据量，提高检索效率，减少对服务质量的影响㊂基于上述观点，本文基于属性基加密提出了一种可应用于位置隐私保护的属性基PIR 方法，该方法在有效的保护用户隐私信息的同时，能给提供比索引为基础的隐私信息检索方法更好的服务质量㊂最后，通过安全性分析和比较实验，进一步证明本文所提出的方法在隐私保护能力方面和算法执行效率方面的优越性㊂
1㊀隐私保护相关定义
1.1㊀系统架构及攻击假设硅链
与传统隐私保护方法不同，基于隐私信息检索的位置隐私保护方法并不需要可信或非可信第三方，因此该方法采用如图1所示的二层系统架构
㊂
图1㊀二层系统架构示意
Fig.1㊀The system structure of two entities
从图1中可以看出，该架构中存在2个实体，即用户和LBS 服务器㊂用户是指在固定位置或移动过程中，通过自身设备向LBS 服务器请求服务的使用者；而LBS 服务器是在获得用户请求信息后向用户提供服务结果的服务提供者㊂通常,LBS 服务器由政府或大型企业提供因此是真实可信的，但所有信息均
由该实体处理，使得该实体易成为攻击焦点，且在巨大商业利益诱惑下存在泄露用户隐私的可能㊂因此，本文假设该实体为半可信实体，既能够提供位置服务，又可对用户隐私信息进行收集并分析，因此需将用户信息隐藏防止LBS 服务器获得用户隐私㊂
1.2㊀隐私保护需求
针对1.1中给出的以LBS 服务器为潜在攻击者的攻击假设，若需保护用户的隐私信息，在整个基
于位置服务的过程中需降低对LBS 服务器的信息公布量，同时还需要获得所需要的查询服务结果㊂因此，基于用户属性特点，有如下隐私保护和服务需求:
1)LBS 服务器无法准确识别由用户查询信息转化的属性信息;
塑料染
2)LBS 服务器能够根据用户提交的加密查询信息反馈查询结果;
3)隐私处理以及服务获取过程应在用户可接受时间范围内完成㊂
基于上述需求，本文设计并提出了隐私保护方法㊂
2㊀属性基PIR 方法及算法
2.1㊀属性基PIR 方法
通常，用户请求基于位置服务反馈时需向LBS 服务器提交查询，该查询一般为：距离我最近的饭店㊁当前道路上的加油站或者到某酒店的最短路程等㊂这些信息可形式化为Q ={(x ,y ),t ,c }，其中(x ,y )为用户所在位置,t 为提出查询的时间,c 为查询的内容㊂因此，上述信息可以用用户属性加以代替，即存在用户属性A ={A 1,A 2, ,A n }中的每一个属性对应查询中的一个形式化表述内容㊂因此，上述查询的隐私保护可转换为用户属性隐私信息检索，并解密反馈信息的处理过程㊂这一过程可表示为如图2所示的LBS 服务器和用户之间的信息传递协议
㊂
图2㊀属性基PIR 传递协议
Fig.2㊀The protocol of attribute based PIR
2.2㊀属性基PIR 方法执行过程
按照属性基PIR 的处理协议，隐私检索方法存在2个处理阶段，分别为LBS 服务器信息处理和用户信息处理㊂为便于对属性PIR 的理解，本文借鉴文献[12]所提供的隐私信息检索方法，将这2个阶段按照时间顺序加以表述㊂为便于理解，表1给出了属性PIR 处理中所使用的参数及所表示的含义㊂㊀㊀在准备
阶段,LBS 服务器首先计算F (1λ)ң(,p ,g ),αѳ$
p ,g 1ѳg α，获得公开参数params =(g ,g 1,)㊂
㊃
186㊃
哈㊀尔㊀滨㊀工㊀程㊀大㊀学㊀学㊀报第42卷
式中:g是的生成器，是p阶大素数循环,F(㊃)是多项式时间概率算法㊂
表1㊀属性PIR所涉及的参数Table1㊀Parameters used in attribute based PIR 符号表示的意义
A用户的全部属性集合
λLBS服务器选择的系统安全参数params LBS服务器的公开参数
G用户选定的属性集合
Z n p含有n个元素的从p选择的集合
p0~p-1个数组成的集合
sk用户私钥
β用户保存的私钥
ѳ$从右面集合中一致选择一个元素并赋值给左面集合T(G)用户发送的加密后的查询信息
sdo100
M用户所需要的反馈结果
LBS服务器所保存的属性信息集合
k LBS服务器保存的属性集合中的属性数量
Mᶄ用户获得的加密反馈信息
n用户选定的属性数量
CT用户获得的由LBS服务器反馈的查询信息㊀㊀设存在用户的全部属性集合A,LBS服务器需选择系统安全参数λ，素数阶p以及安全参数λ保证下的公开参数params㊂同时，每个用户需利用其私钥生成标记和选择的属性集合，并将生成标记作为查询信息发送给LBS服务器㊂为生成标记，用户需使用系统
公开参数params，并同时选择由G表示的用户选定属性集合，本文假设G={A1,A2, ,A n}ɪZ n p，其中n为用户选定的属性数量㊂对于给定的属性G={A1,A2, ,A n}⊂A，随机数βѳp，计算:
hѳgβ
tң=(t1,t2, ,t n)ѳ$n p
sң=(s1,s2, ,s n)ѳ$n p
rң=(r1,r2, ,r n)ѳ$n p,g1ʂg-βr i,i=1,2, ,n ㊀㊀对于每个i分别计算:
u iѳg1h r i,v iѳg r i,X iѳg s i,Y iѳg t i
f i(x)=ᵑn j=1,jʂi x-A j A i-A j=ðn-1j=0a i,j x j mod p
U iѳh s iᵑn j=1u a j,i-1j92gan
V iѳh t iᵑn j=1v a j,i-1j
㊀㊀经计算，用户获得向LBS服务器发送的加密属性信息T(G)={U i,V i,X i,Y i},i=1,2, ,n，同时保存私钥β㊂其中,aѳ
$b表示从集合a中一致的选择一个元素并赋值给b㊂上述计算处理过程可表示为如算法1所示的计算过程㊂
算法1㊀用户加密查询处理
输入：用户查询信息转换后的属性信息G和私钥βѳp
输出：加密后的用户查询信息T(G)
1随机选择初始参数tң㊁sң㊁rң;
2计算hѳgβ;
3for(i=1,i<=n,i++)
4u iѳg1h r i,v iѳg r i;
5㊀㊀X iѳg s i,Y iѳg t i;
6㊀㊀f i(x)=ᵑn j=1,jʂi x-A j A i-A j=ðn-1j=0a i,j x j mod p; 7㊀㊀U iѳh s iᵑn j=1u a j,i-1j;
8㊀㊀V iѳh t iᵑn j=1v a j,i-1j;
9end
10return T(G)={U i,V i,X i,Y i};
算法1中，第3~9行通过for循环实现对每个属性对应的查询进行加密，并获得加密查询信息T(G)，该过程若不考虑累乘其时间复杂度为O(n)，但在算法的6~8行对属性信息进行了累乘计算，因而实际的时间复杂度将达到O(n2)㊂
当LBS服务器收到用户发送的T(G)时，对于保存的兴趣点数据M，以及数据属性,||=k, LBS服务器完成如下计算:
P iѳV1㊃V A i2㊃V A2i3 V A n-1i n=v i㊃h t1+t2A i+ +t n A n-1i=g r i㊃hηi Q iѳU1㊃U A i2㊃U A2i3 U A n-1i n=
u i㊃h s1+s2A i+ +s n A n-1i=g1gβr i㊃hθi W iѳQ i㊃g-11=gβr i hθi ㊀㊀同时计算:
l1,l2, ,l kѳ$p
PѳᵑiɪP l i i=gðiɪr i l i㊃hðiɪηi l i
WѳᵑiɪW l i i=gðiɪβr i l i㊃hðiɪθi l i
tѳ$p
C0=ᵑiɪ(ᵑn j=1X A j-1i j)tl i=g t㊃ðiɪθi l i,θi=s1+s2A i+
+s n A n-1i
C1=ᵑiɪ(ᵑn j=1Y A j-1i j)tl i=g t㊃ðiɪηi l i,
ηi=t1+t2A i+ +t n A n-1i C2=P t
C3=W t㊃M
㊀㊀LBS服务器获得加密信息CT=(C0,C1,C2, C3)，并将其发送给用户㊂上述处理可表示为如算法2所示的计算处理过程㊂
㊃286㊃
第5期杜刚，等：基于属性基隐私信息检索的位置隐私保护方法
麦克力电气算法2㊀LBS服务器进行隐私信息检索
输入：用户提交的加密查询信息T(G)
输出:LBS服务器基于属性PIR处理后的加密查询结果CT㊂
1for(i=1,i<=k,i++)
2㊀㊀计算P i,Q i,W i;
3end
4随机选择l1~l k,t;
5累乘计算P和W;
6计算C0,C1,C2,C3;
7return㊀CT=(C0,C1,C2,C3);
算法2通过for循环对LBS服务器内保存的所有属性处理后获得反馈的查询结果，并向用户发送含有n个属性的查询结果集合㊂此时,for循环的规模远大于算法1中的for循环，即k≫n㊂此时算法2的时间复杂度为O(k)+O(n)=O(k)㊂
用户在收到由LBS服务器发送过来的信息CT 后，计算:
Mᶄ=(C-sk1㊃C2)-sk㊃C-sk0㊃C3= ((g t㊃ðiɪηi l i)-β㊃(g t㊃ðiɪr i l i㊃h t㊃ðiɪηi l i))-β㊃(g t㊃ðiɪθi l i)-β㊃g t㊃ðiɪβr i l i㊃h t㊃ðiɪθi l i㊃M=M ㊀㊀由此可在M中过滤出所需要的查询信息㊂最后对CT的处理过程可简化为算法3所示的处理过程㊂
算法3㊀加密反馈信息解密
输入:LBS服务器反馈的加密查询结果CT;
输出：明文Mᶄ㊂
1Mᶄ=(C-sk1㊃C2)-sk㊃C-sk0㊃C3;
2return Mᶄ;
算法3对每个属性信息进行了累加计算，处理后获得针对用户提交属性的查询结果信息㊂该算法的时间复杂度为O(n)㊂
综上，经过3个算法的处理实现了属性基PIR 的处理过程，用户可通过秘密的信息检索过程获得所需的查询反馈㊂
3㊀性能评估
3.1㊀隐私保护和可用性分析
属性基PIR的安全性取决于LBS服务器无法准确识别由用户查询信息转化的属性信息㊂其可用性取决于对查询结果的准确反馈以及在有效的时间内的计算处理㊂
在安全性方面，首先，用户属性信息在处理中进行了模p运算，且p为大素数，则根据模运算的性质，攻击者很难在未知β的情况下逆向推测出用户属性；其次，设攻击者获得T(G)和属性数量n，但由于t
ң㊁sң㊁rң是一致性选择获取的数据，即使不经过模运算攻击者也无法逆向准确识别用户属性；最后，攻击者掌握的属性数量k≫n，即在k个属性中准确地猜测识别其子集中完整的n个属性的概率为1/k n，此时攻击者更难准确地识别用户提交的属性信息㊂为进一步说明本文所提出算法的隐私保护能力，设存在一个在挑战者A和用户U之间的博弈来证明隐私保护强度㊂假设挑战者A准备了2组属性(a1,a2)，并将这2个查询发送给用户U㊂U随机选择cɪ(1,2)并表示为a c，同时将2组属性加密，然后将任意一组属性M发送给挑战者A㊂如果挑战者A能够计算得出cᶄ满足p(a cᶄ)ʂp(a c)，则A 获胜㊂若A获胜，则需对于任意一组属性，存在p (a iɪa c|a cɪM)ʂp(a jɪa c|a cɪM)∀(0<iʂjɤk)，而在本文算法中，按照上述分析，有:
p(a iɪa c|a cɪM)=p(a iɪa c|a cɪM)
p(a cɪM)㊀=
p i
p(a cɪM),
对于另一组属性，有:
p(a jɪa c|a cɪM)=p j
p(a cɪM)㊂
㊀㊀在本文算法的处理下，攻击者可获得的是加密后的属性信息，在不能获得解密密钥的前提下，攻击者只能进行猜测，此时2次猜测成功的概率彼此相等，有p i=p j,∀(0<iʂjɤk)㊂这与挑战者A获胜的条件相悖㊂因此，可认为本文算法具有较高的隐私保护能力㊂
在可用性方面，属性基PIR的检索准确性可表示为:paramsѳ
$F(1λ),(T(G),n,sk)ѳ$(params, G),1ѳ$(params,T(G),n),CTѳ$(params,, T(G),M)，则对(params,CT,sk)检索后的取值将是
M,if⊆G
ʅ,if⊆G
{，所以选择的属性是LBS服务器
公开属性基础上获得的检索结果㊂其次，在执行时间即算法执行效率方面，按照第2节给出的的时间复杂度分析，在顺序执行时，属性基PIR的时间复杂度可表示为O(n2)+O(k)+O(n)=O(n2)，即算法在用户和LBS服务器之间仅进行2次数据传递，且每个实体所进行的计算均限定在二项式时间范围内，因而概算可在二项式时间内完成㊂而从理论上分析现有的PIR处理过程，虽然在实体之间的信息传递过程中也都是2次，但是在隐私信息检索过程中，由于索引检索需要重复多次索引与数据之间的比较操作，其时间复杂度可达到O(n4)[13]，因而本文算在检索效率方面更具优势，具体的执行时间将
㊃386㊃
哈㊀尔㊀滨㊀工㊀程㊀大㊀学㊀学㊀报第42卷
通过实验与另外几种PIR 方法加以测试比较；最后，关于属性基PIR 的其他特性可参考文献[14]给出的密码学证明，本文不再详述㊂3.2㊀实验设定
通过上一节给出的属性基PIR 在隐私保护和可用性方面的理论分析可知，该算法能够保障用户的隐私且具有良好的执行效率㊂本节将通过与其他几种基于位置服务的隐私保护算法之间的对比，进一步证明所提出方法的优越性㊂参与比较的算法有：基于索引的可计算PIR [10]，基于分层索引的层次PIR [15]，基于模糊索引的近似PIR [16]，基于属性泛化的属性基加密算法[17]以及基于属性模糊的关联概率不可区分算法[5]㊂实验将使用北京出租车行驶数据，并在Intel Core i51.70GHz CPU㊁4gb RAM 笔
记本电脑上利用Matlab R2017a 在Windows 7ˑ64操作系统上完成测试，所有结果均是取计算500次后的平均值作为比较结果并绘制完成结果图㊂3.3㊀测试结果及分析
mesh设备表2给出了几种算法在不同安全环境下㊁查询准确性以及算法运行时间上的效果比较㊂
表2㊀不同算法效果比较
Table 2㊀The comparison effects of different algorithms
算法名称属性隐藏零知识泄露不可
关联性
准确性执行时间可计算PIR [9]ɿɿˑ中高层次PIR [13]ɿɿˑ中中近似PIR [14]
ɿ
ɿ
ˑ中中属性基加密算法[15]
ɿˑɿ高低关联概率不可区分算法
[5]
ɿˑɿ低低本文方法ɿ
ɿ
ɿ
中
低
㊀㊀图3给出了几种不同算法在属性数量变化下的
攻击者猜测成功概率㊂从该图中可以看出，本文方法因使用属性基PIR，所以随属性增加，攻击者攻击成功的概率变化不大㊂同样使用PIR 技术的可计算PIR㊁层次PIR 以及近似PIR 等3种方法的攻击成功概率也变化不大，这是因采用PIR 索引差异导致的攻击效果差异㊂而属性基加密算法，尽管采用属性加密来防止属性被攻击者识别，但该算法一方面需提交用户真实位置，导致被识别的概率高于PIR；另一方面随着属性数量的增加，其保护性逐渐降低，因此其攻击成功率要高于上述几种基于PIR 的算法㊂最后，关联概率不可区分算法采用的是位置模糊，并未对用户的属性信息加以保护，其被攻击者有效识别的概率高于其他算法，攻击成功率最高㊂
图4给出了几种不同算法在查询次数变化下的攻击成功概率㊂从该图中可以看出，随着查询次数的增加，所有算法都不可避免地存在更高的被攻击者识别的概率㊂这是因为随着查询次数的增加，用
户将暴露更多的潜在信息给LBS 服务器，这些信息可作为背景知识被攻击者所利用，进而提升攻击成
功率㊂在这些方法中，本文方法因采用属性基PIR，其被暴露属性的可能性较低，攻击者利用属性关联获取用户隐私信息的成功率要低于其他PIR 算法㊂而其他PIR 算法，诸如计算PIR㊁层次PIR 以及近似PIR 等3种方法，由于采用加密技术，使得可暴露的信息量要少于泛化或模糊的算法，因此其攻击成功率要低于属性基加密算法和和关联概率不可区分算法㊂最后，属性基加密算法可针对的属性要高于关联概率不可区分算法，其攻击成功率要低于关联概率不可区分算法，而关联概率不可区分算法则是几种算法中最易被攻击者攻破并获取用户隐私信息的算法
㊂
图3㊀不同算法的攻击成功概率vs.属性数量Fig.3㊀The success ratio of guessing the privacy vs.the
number of
attributes
图4㊀不同算法的攻击成功概率vs.查询次数
Fig.4㊀The success ratio of guessing the privacy vs.the num-ber of requests
图5给出了几种不同算法在属性数量变化下的算法执行时间差异㊂从该图中可以看出，所有算法的执行
时间均随用户属性数量的增加而增长，这是因为属性加密算法以及其他算法，都需对增加的属性进行加密㊁泛化或模糊处理，上述过程增加了处理时间㊂在这些算法中，本文算法由于采用了属性基检索，其执行时间要低于采用索引检索的PIR 算法，且由于对多个属性同时加密，其执行时间要低于用户协作的属性基加密算法，仅高于采用偏移的关联概率不可区分算法㊂其他几种PIR 则按照可计算PIR，层次PIR 以及近似PIR 的顺序，其算法执行
㊃
486㊃
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议