文摘

随着移动通信技术的发展,基于位置的服务(LBS)蓬勃发展的路旁。与此同时隐私保护已成为进一步发展的主要障碍磅。的最近的邻居(nn)搜索是最常见的一种类型的磅。在本文中,我们提出一个高效的私人循环查询协议(EPCQP)和高准确率和低计算和通信成本。我们采用摩尔曲线将二维空间数据转换为一维序列和加密的兴趣点(POIs)信息与保护隐私的Brakerski-Gentry-Vaikuntanathan同态加密方案。该方案执行加密POIs的秘密圆形转变信息隐藏的位置用户没有可信第三方。为了减少计算和通信成本,我们动态地划分表POIs的信息的价值 。实验表明,该方案提供了查询结果精度高,同时保持低计算和通信成本。

1。介绍

如今,基于位置服务发展迅速,移动互联网和智能移动设备的广泛使用。基于位置的服务使用移动设备内置的帮助下学习当前位置定位设备和位置信息通过移动网络。

在基于位置的服务中,用户得到的查询结果为服务提供者提供准确的位置。用户隐私是可能获得的对手通过结合相关背景知识和捕获的位置信息。如何利用服务同时保护用户的位置隐私已成为一个研究课题近年来在基于位置的服务。

基于位置服务的隐私数据包括三个方面:身份信息、位置信息和查询内容。位置的隐私是指用户隐藏的准确位置。查询内容的隐私是指隐藏用户提交的请求的具体描述。查询内容时,用户的特征和行为可以推导出。

在伦敦商学院,保护隐私的核心是切断身份信息的相关性,位置信息和查询内容。从用户查询内容彼此相关的连续查询。因此,它不仅提高了隐私保护的难度,也增加了计算成本。

在保护隐私的查询有两种通信模式在磅:一个是基于可信第三方(TTP),另一个是不受信任的第三方(TTP-free)。虽然TTP-based的解决方案(1- - - - - -7)能够收集足够的信息来最大限度地满足隐私保护的需求,存在两个问题:很难获得TTP,出类拔萃。集中攻击TTP使它成为瓶颈的查询计划。TTP-free-based解决方案利用有限的信息来帮助最大化隐私保护。然而,有一个缺乏优秀的方法在所有三个方面的查询的准确性,效率,保护隐私。

留置权et al。8)提出了一个私人循环查询协议没有TTP (PCQP),它使用摩尔曲线和Paillier密码系统实现位置的保护和查询内容。该计划包含大量的同态增加和乘法,因此它需要较高的计算和沟通成本。宇都宫等。9]PCQP的基础上做了一些改进,提出了一个轻量级私人循环查询协议(LPCQP)划分POI-table有效减少同态的数量增加和乘法。的分裂POI-table只执行一次初始化过程和子类型的数量显著地影响查询的准确性。在一些极端的情况下,该方案不能返回POIs给用户。此外,当POIs的子表的数量远远大于 ,同态增加和乘法带来大量的不必要的计算成本。LPCQP使用同态加密方案提出的智能和·维,以确保安全。这个计划需要大尺寸的公钥和大量的计算。

考虑到上述两个方案的优缺点,本文提出了一个高效的私人循环查询协议(EPCQP)减轻LPCQP没有破坏安全的缺点。该方案利用完全同态加密方案来解决这一问题的安全查询在磅加密数据。省略多余的同态增加和乘法,该方案动态地把加密POI-table根据用户的查询要求。数据安全取决于Brakerski-Gentry-Vaikuntanathan (BGV)同态加密方案10]。此外,用户利用循环移位和模操作来代替真正的位置,保证了位置保护隐私。

该方案具有以下优点。

(1)位置隐私和数据隐私。该方案可以保护相关的攻击,背景知识攻击,离线关键字猜测攻击,推理攻击、中间人攻击和攻击的链接。

(2)计算效率。计算成本时下降了99%或更多从5到50 PCQP相比。当小于25岁的计算成本EPCQP显著低于LPCQP。

(3)高准确率。该方案的准确率是即使高于90%为统一的数据集很大,高于84%时大的现实世界的数据集。

本文的其余部分组织如下。部分2介绍了相关的背景知识。部分3描述了该协议的细节和部分4讨论了该方案的性能根据不同的实验。综述了相关工作5结论是在部分6。

2。背景

在本节中,我们审查的主要技术是利用提出的协议。

2.1。摩尔曲线

Space-filing曲线(11)代表一个类曲线的遍历所有点在二维区域或更普遍的一个维超立方体,没有交叉。希尔伯特(12]证明了通用的几何生成程序构建整个类空间的曲线在1891年。希尔伯特曲线有集群和优越的能力部分保留邻近邻接的原始数据13,14]。图1说明了希尔伯特曲线不同的订单。一个th秩序希尔伯特曲线可以通过所有细胞 正方形网格。每个单元格的数量在街角表示一个索引,调用- - - - - -价值,从一组( 当曲线遍历细胞。

摩尔曲线(15)是一种变异的希尔伯特曲线与end-point-connected财产。图2说明了摩尔曲线不同的订单。POIs的二维区域可以使连接成一个圆形结构。我们计划采用摩尔曲线由于圆连接属性。

2.2。同态加密

没有可信第三方,我们计划采用同态加密保护数据隐私。由于房地产的同态加密显示(1),服务器可以执行加法或乘法没有解密的明文。在(1), , , ,和表示两个明文,公钥和私钥,分别。加密和解密是表示和 。在这里,和在暗文表示同态加法和乘法。

同态加密(16里维斯特等人1978年提出的)。贵族(17)在2009年提出的第一个完全同态加密方案,引导构建一个使用完全同态加密方案从一种同态加密方案。该计划可以概括如下:FHE =她+引导,其安全性取决于某些坏的问题在理想的晶格。为了减少计算复杂度的解密电路,他设计了一个lattice-based解密电路,及其安全取决于两个问题的假设的硬度:稀疏的子集和问题(SSSP)和某些坏的问题在理想的晶格。绅士的计划使用矩阵运算,向量模运算,在计算和快速增长导致不连续计算成本。此外,生成的密文的大小相应的比特明文是成倍增加;因此,大小变得太长被编程实现。尽管有这些缺点,贵族仍然作出了伟大贡献的研究完全同态加密。改善穷人的实用性绅士完全同态加密方案,许多优化方案的完全同态加密自2009年以来出现了。2010年,凡戴克et al。18)应用简单的代数结构构建一个完全同态加密方案,基于整数运算,贵族的计划的基础上。这个方案比较简单,但不实用。

2010年,聪明,比·[19)提出了一个完全同态加密方案密钥和密文较小的尺寸。2011年,贵族和Halevi [20.)改善原完全同态加密方案用一个新的密钥生成算法,和不需要完整的多项式反演方案。2011年,贵族和Halevi [21)提出了一些计划,不需要挤进一步的硬度SSSP假设,进一步优化性能,并提高了实用性。2012年,Brakershi et al。10)提出了Brakerski-Gentry-Vaikuntanathan同态加密方案的应用关键切换和模数转换技术,同时与其他BitDecomp技术管理噪音。同年,Coron et al。22)提出了一个完全同态加密方案在降低的公共密钥大小的整数冯·迪等人的计划。

最近的研究成果仍然是通过改善原贵族的方案。Halevi Shoup博士发明了一种新的完全同态加密库,即HELib [23]2013年,基于BGV同态加密方案,使用模数转换技术来减少噪音密文。的同态操作完成减法和转变,原来的基础上增加和乘法。除了功能改善,HELib的性能主要由Smart-Vercauteren密文优化包装技术(24)和Gentry-Halevi优化(25进一步提高同态操作的效率。一般来说,同态加密数据的操作完成,它显示了更好的性能。

考虑到上面的一切,我们采用同态加密方案发布在HELib拟议中的协议。

3所示。拟议中的协议

提出了一个高效的私人循环查询协议,可以实现高精度和低计算成本而不受信任的第三方。

3.1。概述EPCQP

图3说明了EPCQP的整个架构。

3.1.1。初始化过程

步骤1。服务器构建一个摩尔曲线和生成- - - - - -指数为每个注册POI在目标区域。

在这一步中,一个磅服务器选择适当的参数来构造一个摩尔曲线覆盖目标区域,构建POI-table包含所有注册POIs的信息。POI-table包含- - - - - -指数和每个POI的POI-info,例如,经度,纬度,名字。每个存储POI-table POI是编号按照均匀分布- - - - - -指数与公差而不是相关- - - - - -价值。的定义- - - - - -指数将在部分3.2。1。

步骤2。用户生成的公钥和私钥对和发送的公钥到服务器。然后服务器加密POI-table公钥 。

3.1.2。查询过程

步骤3。用户问题神经网络查询到服务器。

步骤4。服务器将POI-table划分为子类型。请注意,- - - - - -指数列的POI-table不会被加密。所有条目的数量在每个子表 。 表示索引的POI包含的子表。服务器存储的映射- - - - - -价值来- - - - - -指数每个POI按照查询表。此外,按照查询表记录为了让用户知道,子表他应该搜索。因此,每个POI的按照查询表包含三个属性: , ,和 。划分方法的细节将在部分3.2。2。

第5步。摩尔的切断宣布设置参数曲线和在公共场合按照查询表的所有注册用户。用户可以检索- - - - - -指数他的当前位置在目标地区和他应该搜索的子表。细节将在部分3.2。3。

步骤6。用户选择一个整数t生成一个 ,抵消循环置换矩阵的转变 和一个向量 。在第一行 ,的 th元素是唯一的非零元素。的th元素是唯一的非零元素。的定义和将在章节3.2。3和3.2。4。

步骤7。用户计算值 模 ——生成转变指数。的从按照查询表中检索根据当前位置。用户加密的第一行的公钥生成的步骤2,表示和 。用户发送的转变指数, ,和到服务器。

步骤8。服务器使用构建一个秘密循环转移矩阵 。服务器聚集所有的子类型到一个新表 。的- - - - - -索引POIs的从编号来 。

第9步。服务器使用执行一个秘密的圆形转变基于完全同态属性与用户的公钥。服务器执行一个神经网络搜索圆转然后返回加密的结果给用户。细节将会出现在部分3.2。4。

第10步。用户用私钥解密接收到的结果选择在步骤2并获得所需的nn POIs。

的用户已经添加的(在步骤7),POIs的秘密圆转移了吗(在步骤9)。基于加法和乘法同态,这个秘密神经网络搜索结果的发生了变化将与搜索结果相一致的明文原来的子表。

3.2。EPCQP的细节

3.2.1之上。的映射地理H值来H量指数

图1显示起始细胞不相邻细胞终止于希尔伯特曲线。搜索范围会减少当用户附近的开始或结束细胞希尔伯特曲线,这意味着查询精度将降低。图2表明摩尔曲线的起点和终点是邻居。因此,我们采用摩尔曲线将一个二维空间的序列 。摩尔的能力曲线,所有POIs可以构造成一个圆形结构是很重要的,当把POI-table在随后的步骤。此外,结果主要依赖的顺序 ,这样改变POIs的不影响查询结果。

表示一个均匀分布的序列编号升序排列的与公差 。 的th POI在摩尔曲线计算 在哪里是一个整数大于或等于一的sequencing-order POI的升序排序吗在给定的摩尔曲线。服务器结构POI-table包含POI-info和POIs的映射和记录来按照查询表。服务器应该更新POI-table和按照查询表任何POI的变化然后公开宣布新按照查询表的所有注册用户。

3.2.2。把POI-Table

PCQP需要大量的计算由于整个POI-table乘法应用。宇都宫等人提出了一种轻量级的神经网络根据POI-table划分搜索协议子类型。服务器将POI-table LPCQP提前在初始化过程中。当用户的问题神经网络查询,他选择只有一子表包含POIs用户需求。尽管LPCQP降低计算成本显著地与PCQP相比,它需要查询精度和计算成本之间的权衡在服务器上。宇都宫等人已经说明了这一点 应该是0.5或更少为了获得查询精度高,在哪里表示子表中的所有条目的数量。查询的准确性LPCQP变得更糟变大,由于一些POIs聚合子类型的损失。极,当 ,服务器只返回POIs给用户。的分裂POI-table只执行一次提前;因此,如果它不能满足查询需求是不合适的。

灵感来自LPCQP,我们提出一个有效的神经网络搜索方案来减轻LPCQP的缺点,称为EPCQP。在EPCQP,每个子表的大小取决于用户的查询需求,而不是把POI-table初始化过程中只有一次。我们把POI-table分成子类型,每个子表POIs。是计算 在哪里表示POI-table中的所有条目的数量。的th子表,表示 ,被定义为 在哪里表示原POI-table和th条目表示- - - - - -th的条目th子表。

就像前面提到的3.2。1,起点与终点的摩尔曲线。地理上,第一个POI最后POI存储在POI-table接近对方。因此,第一个和最后一个POIs是邻居的二维空间不管- - - - - -指数他们之间的距离。如果所有条目的数量th子表小于 ,它将附加使用原始POI-table中的条目从第一th。是计算

如图4,有九个POIs POI-table。如果 ,POI-table将每个包含四个POIs分为三个子类型。第三子表包含 , 。

3.2.3。聚合子类型

用户查找按照查询表的根据当前位置,然后选择子表包含最近的POI作为查询的子表。接下来,用户获得目标子表的索引检索按照查询表的列。不失一般性,我们的th子表是用户选择的那一个。用户生成一个向量定义为

用户加密的公钥然后发送密文到服务器。服务器可以增添的每个元素通过相应的子表。然后th子表就变成了 。

服务器汇集了所有子类型到一个新表计算的

根据(6)和(8),所有条目的POI-info子类型成为明文中的零域除th子表。请注意,- - - - - -索引POIs的屈指可数的来 。

由于同态加密的属性,满足

图4表明聚合子类型的过程。有九个POIs和一个用户在地图上(Q)。根据摩尔曲线,九POIs存储在POI-table升序排列的- - - - - -索引。当用户的问题神经网络搜索与 ,服务器将POI-table划分为三个子类型和每个子表有四个POIs。POI的有最近的- - - - - -指数给用户;因此,用户选择第一子表查询。然后所有的子类型都聚合到一个表的条目第一子表。

3.2.4。秘密循环转变th子表

为了保持原始的- - - - - -指数秘密到服务器,POI-info列的原始POI-table PCQP圆转。Paillier加密方案的基础上,提出了循环移位的加密矩阵向量乘法在PCQP POI-info列在其明文域而置换矩阵是加密的。虽然在整个循环转变POI-table维护与POIs的相邻关系,它需要大量的计算由于整个POI-table乘法应用。宇都宫等人提出了一种轻量级的计划(LPCQP)减轻PCQP的缺点。灵感来自LPCQP,我们利用循环转变和模操作隐藏用户的实际位置。

后将POI-info列单位循环下行,一样的神经网络可以通过改变查询获得搜索结果- - - - - -指数的转变,指数,计算 当是一个负整数,它代表了一种向上的转移。

改变参数是由用户决定;因此,服务器不能获得原始- - - - - -指数用户根据转移的-指数。保护用户的当前位置被披露。

同样,POI-info列上的圆的转变在服务器端应该保持秘密。在PCQP,整个POI-info列被乘以一个加密的圆转 矩阵。乘法和加法同态的运营商将带来一个巨大的开销,尤其是对移动服务。在这篇文章中,只有的POI-infoth子表,用户选择将被乘以一个加密的圆转 ,偏移矩阵 ,这是定义为 在哪里 。

用户加密置换矩阵的公钥得到密文然后将它发送到服务器。服务器的繁殖与聚合表为了圆转变的POI-info列th子表和保持- - - - - -指数列完整。

注意,伪随机数是不同的在每个加密过程,这意味着服务器无法区分加密的“0”和“1”。为了减少计算和通信成本,用户只有加密第一行并发送到服务器。然后切断结构通过循环移位 。为了便于理解,如何构造就是一个例子 。

让的第一行 ,和可以构造成

服务器的繁殖与聚合表获取圆移位和POI-info解密数据。解密后,结果将有相同的转移价值t。

如图5(一个)子表中,有8个POIs, 和 。的- - - - - -指数用户是10,结果 ,和 。的转变,指数是6时 。提出了图5 (b),用户将根据这一变化,获得相同的结果指数。

注意,子表的第一个元素和最后一个条目不相邻的。因此,循环将更改后将相邻关系th子表,这将减少搜索精度。这种效果是微不足道的减少计算和通信开销。

3.2.5。k神经网络搜索

留置权et al。8)提出了一样交叉神经网络搜索算法实现高准确率和显示两个额外的查询从搜索区域的中央细胞能够在大多数情况下实现合理的准确率。然而,它可能包括重复POI尤其是当用户接近边界。宇都宫等。9)提出了一个关于查询点选择算法,实现了更高的准确率。我们采用的方法提出了LPCQP提高准确率。

3.3。安全分析

主要是最常见的攻击,可以获得一些私人信息的用户可以列为以下6的机会。我们把他们分成三组,每组有两个。

第一组包括相关攻击和背景知识的攻击。敌人利用前一个窃听一些输入通过网络查询和输出结果。然后结合一些先验知识从后者获得关于用户的基本信息,如年龄或工作,敌人可以推断出用户的位置和相对较大的概率。

第二组包括离线关键词猜测攻击以及推理攻击。有一个活板门产生一个搜索词和它不泄露任何信息的搜索词。第一次袭击猜测的内容加密的数据通过计算活板门的一些广泛使用的单词。同时,第二个攻击结合了数据内容的一些背景知识和一些访问模式识别的活板门。

最后一组分为中间人攻击(MITM)和链接攻击。MITM,对手需要第三方用户和服务器之间。它需要保证两党相信他们都是直接与另一个人交谈。链接攻击时,哪个更常用的敌人结合用户的准确位置信息和从外部数据源来确定准确的位置或用户的标识。

在本文中,我们的目标是提出一种有效的方案神经网络搜索与完美的保护隐私。在以下部分中,我们将说明的安全分析前面提到的六种不同类型的攻击。

3.3.1。相关的攻击

相关攻击属于明文攻击,利用统计弱点由于布尔函数的一个好选择。

关联攻击可以成功安装由于明显的输出之间的相关性特别线性反馈移位寄存器(LFSR)和所有定义的LFSRs布尔函数的输出可以区分。因此结合keystream知识的一部分,敌人可以得到特殊LFSR通过蛮力的关键。

至于EPCQP相关攻击,用户发送和所有与不同的随机数加密,与这些随机数每次都被改变了。因此,服务器将不知道关联用户的查询。这意味着我们的计划相关的攻击下是安全的。

3.3.2。背景知识的攻击

这种攻击利用一些标准共同属性之间的密切关系的敏感属性就是其中之一。这样,敌人可以减少可能值集的基数来寻找这敏感的属性。

可以看出,只有用户知道的变化量,因为它是加密的方案。至于服务器,它可以了解什么位置虽然可以查询历史和用户的配置文件。这源自于这样一个事实:用户可以改变每次量而变化所有的敏感信息进行加密传输。

而言,这种攻击在我们的方案中,我们只将改变位置时由用户选择神经网络搜索。移位的位置 并不敏感,因为变化量由用户独立和随机选择。因此,不会泄露用户的敏感信息到服务器,因此我们的计划是对这种攻击。

3.3.3。离线关键词猜测攻击

一般来说,离线字典攻击以及猜测攻击发生基于弱可能低熵的秘密。这意味着,它来自价值的一个小基数。同样,关键词也来自一组,而小相比,弱密码等秘密。基本上,低熵意味着高概率,所以用户更有可能查询时使用低熵的关键词表。

在我们的方案中,至于离线关键词猜测攻击,用户的位置,例如,用户很少使用低熵的关键词。特别是在服务器收集位置数据按照查询表这不是用户的敏感信息。因此,通过离线关键字猜测攻击,没有人能猜位置数据用户在查询的方案。

3.3.4。推理攻击

用户的推理攻击的目的是获得知识通过分析数据。如果对手可以获得的敏感信息的真正价值相对较高的概率,我们说用户泄漏信息。在整个过程中,敌人不能直接从一些琐碎的信息获取任何数据。

推理攻击时在我们的方案中,利用用户的访问模式,比如文档,其中包含先前查询关键词。但是,没有用户的访问模式的敏感信息泄露到服务器或敌人因为和与不同的随机数进行加密,用户这些随机数炒的每次当用户查询。因此,我们的计划是健壮的这种攻击。

3.3.5。中间人攻击

的中间人攻击是一种广泛使用攻击存在第三方中间人。它扮演的角色用户与服务器通信时,然后它将扮演的角色服务器当面对用户。因此它需要模仿网络中传播的所有信息让用户和服务器认为他们是真正的与另一个对话。

有两种广泛使用的方法防止中间人攻击。身份验证是用来确保信息传输在通信是一个合法的来源。篡改检测确保信息不会在传输干扰。

在我们的方案中,用户永远不会发送任何敏感信息或明文到服务器,服务器也不会做。用户只能发送 , , , ,和 。至于服务器,它只需要发送摩尔曲线的参数,按照查询表, , ,和最终的结果集是由同态加密加密方案。完全,他们使用不同的随机数加密和数字用户查询时每次都不同。与此同时,信息子类型的位置是传播的形式 。因此,对手不能扮演服务器的角色,因为他不知道也不能与用户沟通。总之,我们的方案可以抵御这种攻击。

3.3.6。攻击的联系

链接攻击时,哪个更常用的敌人结合用户的准确位置信息和从外部数据源来确定准确的位置或用户的识别。然而,所有的位置信息被表示为 在聚合的子表。服务器可以从转变量什么也学不到,尽管它可能获得部分的知识从外部数据源。因此,我们的计划也可以保证链接攻击下的安全性。

4所示。绩效评估

在本节中,我们比较EPCQP的性能与相关的两个作品:PCQP [8]和LPCQP [9]。我们采用同态加密方案在HELib发布。该方案是在JAVA语言中实现和一台笔记本电脑上执行1.6 GHz Intel Core i5处理器和4 GB RAM。

我们使用两个数据集包括一个统一的数据集和真实数据集。每个数据集包含10000 POIs。现实世界的数据集是中国从基站数据中提取。我们在地图上随机选择1000个地点的问题在每个实验和神经网络搜索结果取平均值。

4.1。查询的准确性

都使用精度标准在数据挖掘和机器学习领域(26- - - - - -30.]。同样,查询准确性是用于实验的验证。的价值和是不同的从5到50,从10到500年,分别。让和表示返回的结果集,并神经网络真实结果集,准确率是定义为

在LPCQP,只有th子表被选中的用户搜索。子类型的数量会直接影响到查询的准确性。当大于 ,服务器返回不到POIs给用户。虽然减少计算成本除以POI-table只有一次在初始化过程中,在某些情况下查询准确率降低。后把POI-table分成子类型, POIs丢失由于聚合子类型(8)。因此,结果会更糟的质量子类型的数量变大。相反,服务器可以构造子类型与一个大单位是小,保证满足查询的结果数要求。不过,当远远大于 ,(所7)和(8同态),计算成本的增加和乘法太浪费找到最多POIs。为了找到最大满足高精度和显著降低计算成本,宇都宫等。9)定义了比作为 在哪里和表示LPCQP和PCQP的准确率。结果表明,性能 应该是0.5或更少为了实现吗 。这意味着,当 ,该计划可以保持相当高的精度和降低计算成本。

当 ,从聚合条目失去了太多的子类型。情况将变得更糟k ,和用户将接收不到在这种情况下的结果。

在我们的方案中, 。如上所述,EPCQP达到一个高的查询的准确率,降低了计算成本,提出了部分4.2。EPCQP的优势是明显的情况 在LPCQP。

数据6和7代表了准确率和为不同的数据集。这表明EPCQP的准确率高于LPCQP当是500。尽管EPCQP的准确率略低于PCQP LPCQP当 ,但仍高于LPCQP时 25岁, 。的准确率EPCQP即使高于90%为统一的数据集很大,高于84%时大的现实世界的数据集。我们定义作为 在哪里表示EPCQP的准确率。数据8和9显示比例与两个数据集。当 1的值代表的比例来 。注意,比保持0.9或以上无论各种两个数据集。特别的情况下 500年,EPCQP达到 当 。如数据所示8和9,EPCQP保持LPCQP当准确率高 时,提高准确率 。此外,利用EPCQP时将更为重要比500年大。

4.2。计算成本

在EPCQP的查询过程中,服务器首先将POI-table划分为子类型。而计算暗文和同态加密/解密,划分表的成本可以忽略不计。提出了在部分3.2。3,服务器可以增添的每个元素由POI-info列相应的子表,然后汇集了所有子类型表 。聚合需要的过程乘法和 增加根据(8)。最后,服务器繁殖与聚合表获得需要的圆和解密POI-info数据转移 增加和 )乘法。

表1代表PCQP的计算成本,LPCQP, EPCQP。与转移过程的成本相比,成本聚合子类型时可以忽略不计很大。就像前面提到的4.1,以达到LPCQP精度高,应该大于或等于 。如表所示1EPCQP,乘法的成本是低于LPCQP时 。除此之外,增加的成本转移过程中明显减少。因此,我们提出的方案具有很高的精度和较低的计算成本。

该方案具有近似计算时间聚合相比,在LPCQP子类型。数据10和11代表加密循环转移矩阵的计算时间和转移过程,分别。如图10,加密循环转移矩阵的计算成本EPCQP成为在PCQP或低于1000 ,大约十分之一的LPCQP各种无关当 10。图11显示的计算成本转移过程在EPCQP变得在PCQP或低于1000 ,它是百分之一的LPCQP各种无关当 。数据10和11表明EPCQP的计算成本低于在LPCQP One hundred.尽管EPCQP的计算成本略高于LPCQP当 0和 的准确率高于LPCQP EPCQP。图12代表PCQP的计算总成本,LPCQP, EPCQP。如图12我们的方案,计算成本低于LPCQP不管当 。计算总成本的降低率在图表示13。当 1,它表示的下降速率与PCQP相比计算总成本。从这些结果,我们提出方案的计算成本与PCQP相比减少了99%或更多。当 和 200年,降低利率是正数,这意味着计算LPCQP EPCQP低于成本。

基于上述结果,我们可以说EPCQP保持高精度LPCQP率,同时减少计算成本。之间有一个权衡EPCQP的准确率和计算成本。

4.3。沟通成本

在本节中,我们讨论我们的计划的沟通成本。表2显示了PCQP的沟通成本,LPCQP EPCQP。节中描述3.2。4,加密矩阵是由第一行。让表示一个加密的POI-info的素数。用户发送作为位在PCQP服务器。在LPCQP,用户发送和作为 位。我们的方案的沟通成本 位。搜索后,服务器返回结果给用户。

是显示在表2的下行沟通成本EPCQP PCQP和LPCQP相同。在上行过程中,通信PCQP EPCQP低于成本。总之,沟通成本的方案相比,相同程度的LPCQP;与此同时它达到高精度。

5。相关工作

现有的位置隐私保护的方法主要分为三类。

5.1。空间隐身

空间隐形(31日- - - - - -39)方法生成一个隐形地区位置服务器和服务器将查询结果返回给用户或受信任的第三方。匿名性是最常见的模式40),由Gruteser首先实现磅和格1]。Chow et al。5)维护用户的位置信息通过使用r - tree结构,这是经典的方法保护用户使用的位置匿名模型。它提出了一个方案,准确地搜索在矩形匿名地区最近的邻居。

5.2。位置阻塞

用户继续提交查询与特定的假位置定位服务器,迭代和服务器返回结果基于假位置,直到用户获得的结果满足隐私和安全要求。经典算法的位置阻碍SpaceTwist [41),需要多次的沟通,每个完整的查询所需的沟通成本很大。

5.3。空间的转换

保护位置隐私空间转换的原理是将位置信息从传统数据空间到另一个地方。该计划(42)利用同态加密来完成用户和服务器之间的数据交互。虽然实现了强大的隐私保护,很难适应连续查询和实时响应的应用程序环境极其昂贵的计算成本。为了降低计算成本,计划(6提出了基于希尔伯特曲线。成本的方案,有效地减少了计算加密,将二维空间中所有POIs转换成一个整数序列在一维序列和维护原来的邻里关系约。该方案的缺点是查询准确性不高。一个时间空间区域建设机制(7提出了分布式系统。它结合了用户位置与Hilbert-order与其他对等节点形成一个空间区域,然后向服务器发送区和查询的要求。HilAnchor计划(43)是基于SpaceTwist和希尔伯特曲线。只有两轮沟通,用户可以得到准确的最近的邻居POIs的泄漏位置。MobiCrowd算法(44)利用缓冲区来保证查询可以实现本地为了降低沟通成本。

查询隐私是一样重要的位置隐私。该计划(45)生成伪查询,这样服务器和攻击者不能通过总结来获得用户的偏好信息的规则查询上下文。攻击模式(46标志着查询根据查询上下文,位置,和查询时间。文献[47)提出了近似超越怀疑方案,首先利用聚类算法(如——)集群用户类似的位置和问题类似的查询,然后根据计算匿名区域的时间来保护隐私的位置和查询。

6。结论

在本文中,我们提出一个保护隐私循环查询协议与高精度和低复杂性,可以利用定位神经网络搜索。循环移位和同态加密,该方案同时实现高效的查询和隐私保护。我们采用的方法动态服务器把加密POI-table根据用户的查询。我们计划减轻了PCQP的缺点和LPCQP没有损害他们的优点。计算成本的价格相比减少了99%或更多PCQP通过允许减少6%的准确率不管 。与LPCQP当 ,计算成本降低47.5%减少了5%的准确率。快速发展的空间众包,位置隐私吸引了越来越多的关注。我们预计我们的计划会激励位置隐私保护和加密数据计算的研究在空间众包。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是国家重点支持的研究和发展项目赠款2017 yfb0802202和2017 yfb0802704下的中国和上海技术研究项目领导人在格兰特16 xd1424400。