基于马尔可夫模型的同态加密位置隐私保护方案

周凯，彭长根，朱义杰，何建琼

（1. 贵州大学计算机科学与技术学院，贵州 贵阳 550025；2. 贵州大学贵州省公共大数据重点实验室，贵州 贵阳 550025；3. 贵州大学密码学与数据安全研究所，贵州 贵阳 550025；4. 贵州省网络数据保密工程技术研究中心，贵州 贵阳 550025）

基于马尔可夫模型的同态加密位置隐私保护方案

周凯1,2,3，彭长根2,3，朱义杰3,4，何建琼1,2,3

（1. 贵州大学计算机科学与技术学院，贵州 贵阳 550025；2. 贵州大学贵州省公共大数据重点实验室，贵州 贵阳 550025；3. 贵州大学密码学与数据安全研究所，贵州 贵阳 550025；4. 贵州省网络数据保密工程技术研究中心，贵州 贵阳 550025）

针对基于位置服务的位置隐私与查询隐私保护问题，提出一种基于马尔可夫模型的同态加密位置隐私保护方案。首先，随机置换匿名用户真实身份，结合用户的历史查询内容，构建马尔可夫状态转移矩阵；其次，预查询用户的历史高频率内容及马尔可夫链下的预测内容，并且存储相应结果集；最后，对该方案双预测系统的安全性进行了分析。该方案使服务器满足k+1个查询内容，并使恶意服务器或攻击者无法判定查询用户的真实身份与查询内容之间的对应关系，实现了用户位置隐私与查询隐私的保护。同时，利用同态加密密文的可计算性和保密性，实现了面向密文数据的统计分析和隐私数据的安全存储。

基于位置的服务；查询隐私；马尔可夫链；同态加密；匿名性

1 引言

移动互联网可移动化、可定位化以及个性化服务的发展，促进了基于位置服务（LBS, location-based service）的快速发展。基于位置服务将设备定位技术、无线通信技术以及地理信息管理等多种技术相互集成应用，从而为用户提供与其当前空间位置相关的个性化服务[1]。当前，LBS已经在社会、经济、生活等领域产生了深远的影响，基于位置服务在给人民生活带来各种便利的同时，也面临个人隐私被泄露的风险。文献[2,3]报道了某人利用 GPS跟踪前女友事件，文献[4]研究了用户轨迹开始和结束的地点，可以推测出用户的家庭住址等信息。

近几年, 关于基于位置服务隐私保护的研究从未中断过，也取得了丰厚的成果，大部分的位置隐私保护研究工作是基于中心服务器结构和P2P网络结构[5]。文献[6]介绍了位置大数据的相关概念以及位置大数据的隐私威胁定义。目前，位置隐私保护技术主要有：位置 k-匿名技术[7]、假名技术[8]、假位置泛化技术[9]、位置区域的模糊法技术[10]、混合区域技术[11]、加密技术[12,13]等。基于隐马尔可夫模型进行概率推测的位置隐私保护的研究也有很多，文献[14]提出一种MaskIt方法，主要思想为用隐马尔可夫模型形式化攻击者获取用户连续提交位置信息的过程。文献[15]使用 Markov模型来进行位置的预测，但由于模型仅考虑当前时刻位置的影响，使预测精度较低。文献[16]提出了一种用户能判断待提交位置信息的模糊性对候选集精确性影响的位置服务框架，从而权衡预先查询的隐私强度和实用性。

针对大部分方案，用户在使用LBS时，必须要在服务质量和隐私保护之间做出一个折中的权衡。安全的位置隐私保护和高质量的基于位置服务就像鱼和熊掌，两者不可兼得。一方面，位置隐私保护技术最大程度地将用户精确的位置信息隐藏起来；另一方面，享用位置服务的用户希望能得到更精确的位置信息，从而享受更高质量的服务。

针对以上问题，本文提出一种基于中心服务器结构的位置隐私保护方法。首先，通过一个置换表将用户的身份信息匿名。其次，引入马尔可夫模型、混淆查询信息以及预查询概念，实现基于位置查询隐私保护。同时，混淆用户的查询信息，保护用户的身份信息和查询内容的对应关系。最后，通过分析用户的历史查询内容，预查询用户的历史高频率内容及马尔可夫链下的预测内容，并且存储相应结果集。期间，利用同态加密密文的可计算性和保密性，实现面向密文数据的统计分析和隐私数据的安全存储。

2 准备知识

本节介绍需用的准备知识，包括同态加密、马尔可夫链等基本概念和性质。

定义1 同态加密。

同态加密算法由一个四元组(K eyGen, Enc, Dec, Eval)和3个集合(M , Π, C)构成，其中，M= (m1,… ,mn)是明文集合，是相应的密文集合，C是可行的电路集合。四元组中算法描述如下。

KeyGen (1k,ρ)密钥生成算法：输入安全参数k和随机数ρ，输出公钥、私钥( pk, s k)。

Enc( pk, m) 加密算法：输入公钥pk、明文M，加密生成密文。

同态加密的形式化定义如下。

定义2 设0m和1m是明文集合M中的元素，f是M上的运算，E是M上的加密算法，如果存在一个有效的操作函数F使

则称加密算法E对运算f是同态的。

1) 加法同态

设0m和1m是明文集合M中的元素，E是M上的加密算法，D是M上的解密算法，若存在一个有效的操作函数⊕使

则称加密算法E满足加法同态。

2) 乘法同态

设0m和1m是明文集合M中的元素，E是M上的加密算法，D是M上的解密算法，若存在一个有效的操作函数⊗使

则称加密算法E满足乘法同态。

定义3 马尔可夫链。

随机过程{ Xn,n ∈ T}，若对于任意的整数n ∈ T和离散状态空间 I, i0, i1,… ,in+1∈I ，满足条件概率则称{Xn,n ∈ T }为马尔可夫链，简称马氏链。

定义4 状态转移概率矩阵。

马尔可夫链{ Xn,n ∈ T}在时刻n的转移概率为

其中，i, j∈ I。若 pij(n)与时刻n无关，则称马尔可夫链是齐次的，并记 pij(n)为 pij。对于由n个状态组成的状态空间，转移概率可表示为矩阵形式，记为

3 查询隐私保护方案

3.1 用户身份匿名方案

当用户发生一个查询行为，位置匿名系统会随机地生成一个“假名”，即用户的第二重身份。用户发送查询信息时，会发送加密生成的“假名”以及注册时发放的唯一公钥。该系统主要保护用户的身份信息，每次查询时，用户的“假名”都可能不同，以达到混淆用户身份信息的效果。

3.1.1 系统初始化

当用户初次使用匿名系统时，需向可信中心提供个人的身份信息（姓名、电话号码等），用 Uidi表示用户 ui的身份信息。

具体构造方案如下。

1) KeyGen (1k,ρ)密钥生成算法：输入安全参数k和随机数ρ，生成公钥集 PK =( pk1,…, pkn)、私钥集 SK = (sk1,…, s kn)，中心服务器公钥为pkT，私钥 skT。每个用户 ui(1 ≤i≤ n)唯一的公钥为 pki、私钥为 ski。

2) 用户 ui在时刻 t随机生成一个随机数 ri,t作为临时密钥。其中， ri,t可以向中心服务器随时更改，每个用户的 ri,t都不一致。

3.1.2 假名生成

图1 用户身份匿名表

用户iu每次发送查询消息，假名ID都会不同。在这种映射关系下，即使攻击方（敌手）获得位置信息或者身份ID，也很难确定是哪个用户提出的位置服务请求。因此可以很好地起到

混淆用户身份，保护用户的身份隐私不泄露。

3.1.3 服务请求提交

在用户与LBS服务器的通信中，本文采用一次一密的加密方式。具体方案如下。

1) 用户 ui在时刻t随机生成一个随机数 ri,t作为临时密钥，并生成查询信息 Qi=＜ loc, qi, ri,t, Uid′＞，其中，loc是位置信息， qi是查询内容，Uid'是用户生成的假名。

2) 用户 ui用可信中心的公钥 pkT将 Qi加密并发送给可信中心。

3) 可信中心用私钥 skT解密，获得用户 ui的loc、 qi、 ri,t、 Uid'。根据用户的 ri,t对用户进行身份核对。

4) 可信中心发送loc、qi、Uid'给LBS服务器。3.2 查询隐私保护方案

本文方案根据用户的历史查询信息建模，用频率替代概率，将历史查询信息进行聚类分析。在分析中引入同态加密，在密文状态下进行统计计算，然后利用马尔可夫预测模型，预查询可能的查询信息，使查询隐私满足k-匿名，且提高查询效率。第三方服务器中的用户集合 U={u1,…, un}，ui,1≤i≤ n表示集合中的第i个用户， ui用户的历史查询信息集合。查询隐私保护方案分为2个模型：k-匿名混淆模型和马尔可夫预测模型。

3.2.1 k-匿名模型

KeyGen( 1k,ρ)密钥生成算法：输入安全参数k和随机数ρ，生成公钥集 PK =(p k1,…,p kn)、私钥集 SK = (sk1,…, skn)，分配给每个用户ui(1 ≤i≤ n)唯一的公钥 pki、私钥 ski。

Enc( p k, m )：输入公钥 pki、 ui用户的历史查询信息集合，加密生成密文

利用同态加密的密文可计算性，将用户 ui历史查询事件集合用二元组表示，a表示不同的查询事件，b表示每种查询事件的总数，A是密文状态。

将 pi1,… ,pik从大到小进行排序，得到排序后的以及对应概率的查询事件集合，集合 A'i是密文。当检测到用户上传位置信息时，经匿名技术处理，选择概率排名前n个查询内容，其中n( n ＜k)的大小由用户设置。用户 ui历史查询事件也可能来自多个用户上传的数据。

Dec( sk, Π )解密算法：输入私钥 ski和密文集，解密输出明文状态的查询内容。提前发送给服务提供商(SP)并存放加密的候选结果集 {R( D()), R( D)),… ,R( D)) }。将用户发送的查询内容q与预查询内容 {D(), D), … , D()}进行匹对。实现查询的伪代码，见Query算法。

Query算法如下。

3.2.2 马尔可夫预测模型

该模型是以 ui用户(i = 1,…, n)的查询信息密文集合作为源数据。在此模块中，主要工作是使用马尔可夫链预测模型，求出状态转移矩阵。具体方案如下。

1) 根据k-匿名混淆模型分析得到二元组用户 ui共有k种查询事件。

3) 加密iC矩阵。

将矩阵iC按列分组，其中12A[]( , ,, i p p=iip 。将源矩阵按随机生成的映射表Map进行转换，矩阵iC的列混淆，输出混淆矩阵 =B {[1], ,[]}kki…) B B… ，矩阵B存放在数据库中。如图2所示。

图2 加密iC矩阵

4) 根据用户iu的最近一次查询内容，利用求得的概率转移矩阵iC，预测出下一个查询事件。

但是，也可能出现预测内容与用户查询内容不同的情况。那么，系统先匿名用户的身份，然后将查询Q发送给服务提供商，相应的结果直接返回给用户。

在基于位置服务中，k-匿名模型和马尔可夫预测模型同时工作。利用 k-匿名模型提前查询出高频率查询信息的候选答案集。使用马尔可夫预测模型预查询预测信息。每当系统检测到用户打开位置服务，就自动触发预测，发送 k-匿名模型和马尔可夫预测模型的查询信息。此时，位置服务器至少要接收到 1k+个互不相同的查询内容，使服务器无法辨别真实的查询内容。另外，通过预查询和存储结果，提高用户的查询效率。

4 方案分析

LBS系统中的攻击者分为内部攻击者和外部攻击者。本方案的安全性分析如下。

4.1 内部攻击下的安全性

内部攻击者是指 LBS 服务器拥有所有用户的一切查询请求消息，可以利用所掌握的查询信息和查询用户身份信息进行推断攻击，其攻击目的是获得用户身份信息与位置数据的对应关系。

攻击者假设：攻击者是一个全局攻击者，攻击者可以获取LBS服务器数据，拥有一定的边信息[17]辅助的推测攻击。攻击者以获取查询用户的身份信息、查询内容为目标，攻破位置数据与身份信息的对应关系。

4.1.1 身份匿名

身份匿名是指LBS服务器既不能区分用户的真实身份，也不能判断不同的查询信息是否来自同一用户。在本文方案中，用户iu每次查询的假名均来自于身份匿名表的随机选择。任何一个假名其实都是一个现实中真实存在的。由于身份匿名表中的假名与用户iu的 ID无直接关系，即使敌手得到了所有假名集合iidU ，LBS服务器也无法从用户的任意一个假名识别真实身份。不仅如此，即使用户iu发送连续查询信息，敌手获得一串假名也无法判定出用户的真实身份。

4.1.2 位置隐私

假设用户iu在一段时间 TΔ 内发生了 n次服务请求查询。显然，攻击者访问LBS数据库，在时刻jt，LBS服务器获悉用户真实查询内容的概率为，从用户iu假名识别其真实身份的概率为，从用户提交的 loc个位置中j识别真实的位置概率为。这样获悉一次用户真实身份、真实位置信息、查询内容的对应关系的概率为获悉真实身份和位置关系的概率为

对于用户 ui在一个时间段 ΔT 内的整个位置轨迹，本文定义在n次查询中查询内容与真实身份泄露的平均概率为

定义用户 ui在n次查询中泄露位置和身份信息的平均概率为

接下来，对基于 k-匿名的方案[7]和本文方案的隐私程度做简要的分析。

按照文献[7]的k-匿名构造方案，用户 ui在时间段 ΔT 内使用相同的假名，假设敌手获悉其假名所对应真实身份的概率为，k的值设为

假设其中的 m次查询收到了边信息辅助的推测攻击。当LBS服务器在时刻tp拥有边信息时，其掌握了用户的真实身份和位置，既1,ploc=1，而当在所有查询时刻没有掌握边信息时，。将这些值代入，可以得到

m次查询收到了边信息辅助的推测攻击。当LBS服务器在时刻tp拥有边信息时，其掌握了用户的真实身份和位置。此时的，而当在所有查询时刻没有掌握边信息时，。将这些值代入，可以得到

显然，当存在边信息时，文献[7]方案中用户泄露的平均概率远大于本文方案，即

当中心服务器中存放的历史查询信息达到一定程度时，用户的k值越大，用户的查询隐私保护程度越高，攻击者攻破位置信息与身份数据的对应关系越难。

4.2 外部攻击下的安全性

外部攻击分为2种：被动攻击和主动攻击。本文方案中，用户 ui与可信中心T之间的通信均是密文状态，没有相应的密钥是无法解密得到相应明文的。

在发放用户 ui的公、私钥对阶段。用户 ui向可信中心发送一个临时随机数密钥，然后可信中心为其发放加密的公钥 pki、私钥 ski。由于攻击者无法得到可信中心的密钥 skT，他无法伪造可信机构的消息来欺骗用户iu，也无法得到用户iu的临时随机数密钥,itr，不能解密消息得到用户的公钥ipk、私钥isk。在服务请求提交阶段，攻击者无法伪装成用户iu与 LBS 服务器通信，这样用户iu的临时随机数密钥,itr以及中心服务器的私钥Tsk就无法被可信中心服务器验证，也无法伪装成LBS服务器。

5 结束语

本文研究了基于位置服务中的位置隐私、查询隐私保护问题，提出了一种基于马尔可夫预测模型下的隐私保护模型。该模型基于保护用户身份信息与位置数据对应关系的思想，通过一个置换表匿名用户的身份信息，利用k-匿名混淆模型、马尔可夫预测模型，用k个高频率的查询信息混淆用户的真实查询信息，并通过系统的预查询、存储，提高中心服务器结构下的查询效率，最后证明了该方案的安全性。

[1] JENSEN C S. 5-Database aspects of location-based services[J]. Journal of Location Based Services, 2004: 115-147.

[2] Man accused of stalking ex-girlfriend with GPS[EB/OL]. http://www.foxnews.com/story/0,2933,131487,00.Html.

[3] Authorities: GPS system used to stalk woman[EB/OL]. http://www. usatoday.com/tech/news/2002-12--gps- stalker_x.html.

[4] WICKER S B. The loss of location privacy in the cellular age[J]. Communications of the ACM, 2012, 55(8): 60-68.

[5] 王宇航, 张宏莉, 余翔湛. 移动互联网中的位置隐私保护研究[J].通信学报, 2015, 36(9): 230-243. WANG Y H, ZHANG H L, YU X Z. Research on location privacy in mobile internet [J]. Journal of Communication, 2015, 36(9): 230-243.

[6] 王璐, 孟小峰. 位置大数据隐私保护研究综述[J]. 软件学报, 2014, 25(4): 693-712. WANG L, MENG X F. Location privacy preservation in big data era: a survey[J]. Journal of Software, 2014, 25(4): 693-712.

[7] SWEENEY L. k-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, 2002, 10(05): 557-570.

[8] PIRAMUTHU, On existence proofs for multiple RFID tags[C]// The International Conference on Pervasive Services, IEEE. 2006: 317-320.

[9] KIDO H, YANAGISAWA Y, SATOH T. An anonymous communication technique using dummies for location-based services[C]// The International Conference on Pervasive Services(ICPS '05). 2005:88-97.

[10] ARDAGNA CA, CREMONINI M, DAMIANI E, et al. Location privacy protection through obfuscation-based techniques[M]//Data and Applications Security XXI. Berlin Heidelberg :Springer. 2007: 47-60.

[11] PALANISAMY B, LIU L. MobiMix: protecting location privacy with mix-zones over road networks[C]//The 2011 IEEE 27th International Conference on Data Engineering. 2011: 494-505.

[12] MASCETTI S, FRENI D, BETTINI C, et al. Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies [J]. VLDB Journal, 2010, 20(4): 541-566

[13] LI X Y, JUNG T. Search me if you can: privacy-preserving location query service[C]//Infocom, IEEE. 2012: 2760-2768.

[14] TZ M, NATH S, GEHRKE J. MaskIt: privately releasing user context streams for personalized mobile applications[C]//The ACM Sigmod International Conference on Management of Data. 2012: 289-300.

[15] CHEN M, LIU Y, YU X. NLPMM: a next location predictor with Markov modeling[C]//Advances in Knowledge Discovery and Data Mining. 2014:186-197.

[16] DEWRI R, THURIMELLA R. Exploiting service similarity for privacy in location-based search queries[J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(2): 374-383.

[17] YOU T H, PENG W C, LEE W C. Protecting moving trajectories with dummies[C]//The International Conference on Mobile Data Management. 2007: 278-282.

何建琼（1991-），贵州遵义人，贵州大学硕士生，主要研究方向为密码学与安全协议。

Homomorphic encryption location privacy-preserving scheme based on Markov model

ZHOU Kai1,2,3, PENG Chang-gen1,2,3, ZHU Yi-jie3,4, HE Jian-qiong1,2,3

(1. College of Computer Science and Technology, Guizhou University, Guiyang 550025, China;
2. Guizhou Provincial Key Laboratory of Public Big Data, GuiZhou University, Guiyang 550025, China;
3. Institute of Cryptography & Data Security, Guizhou University, Guiyang 550025, China;
4. Guizhou Provincial Engineering and Technology Research Center of Cyber Data Security, Guiyang 550025, China)

Homomorphic encryption location privacy-preserving scheme based on Markov mode was proposed to solve the problem of location privacy and query privacy protection in location-based service systems. Firstly, the anonymous user’s identity were permuted randomly and the Markov state transition matrix combining with the user’s historical query content was constructed. Secondly, system previously queries the user’s high frequency content and the prediction content under Markov chain, then store the corresponding result sets. Finally, the security of the scheme’s double prediction system was analyzed. The scheme makes the LBS receives k+1 query contents which let malicious server or attacker can’t determine the corresponding relation between queried user’s real identity and queried content. So the user’s location privacy and query privacy can be protected. Meanwhile, the computability and confidentiality of homomorphic encryption ciphertext were used to realize the statistical analysis of ciphertext-oriented data and the secure storage of private data.

location-based services, inquiry privacy, Markov chain, homomorphic encryption, anonymity

TP302

A

10.11959/j.issn.2096-109x.2017.00137

周凯（1991-），男，浙江衢州人，贵州大学硕士生，主要研究方向为密码学与可信计算。

彭长根（1963-），男，贵州锦屏人，博士，贵州大学教授、博士生导师，主要研究方向为密码学、信息安全。

朱义杰（1989-），男，山东临沂人，贵州大学硕士生，主要研究方向为密码学与可信计算。

2016-11-22；

2016-12-27。通信作者：彭长根，peng_stud@163.com

国家自然科学基金资助项目（No. 61262073, No. 61662009）；贵州省哲学社会科学规划青年课题基金资助项目（No.16GZQN06）；贵州省科技基金计划基金资助项目（No.黔科合基础[2016]1023）；贵州大学研究生创新基金资助项目（No.2016050）

Foundation Items: The National Natural Science Foundation of China (No.61262073, No.61662009), The Philosophy and Social Sciences Planning Project of Guizhou Province (No.16GZQN06), The Science and Technology Foundation of Guizhou Province (No.Gzuihou-Science-Contact [2016]1023), The Graduate Innovation Foundation of Guizhou University (No.2016050)