没有合适的资源?快使用搜索试试~ 我知道了~
0网络空间安全与应用1(2023)1000070ScienceDirect提供的内容列表0网络空间安全与应用0期刊主页:http://www.keaipublishing.com/en/journals/cyber-security-and-applications/0PPT-LBS:用于位置基础服务外包数据的隐私保护top-k查询方案0周友生a,李霞a,王明b,刘媛妮a0a 重庆邮电大学网络空间安全与信息法学院,中国重庆400065 b 重庆邮电大学计算机科学与技术学院,中国重庆4000650a r t i c l e i n f o0关键词:隐私保护基于位置的服务 Top-k查询外包计算0a b s t r a c t0基于位置的服务(LBS)随着移动互联网的快速增长而受到广泛欢迎。随着数据量的急剧增加,越来越多的位置服务提供商(LSPs)将LBS数据移至云平台,以获得经济性和稳定性的好处。然而,云服务器提供了便利和稳定性,但也导致了数据安全和用户隐私泄露。针对现有LBS数据外包方案中隐私保护不足和查询效率低下的问题,本文提出了一种新颖的用于外包情况的隐私保护top-k查询。首先,为了确保LSP的数据安全和用户的隐私,采用了增强的对称标量积保留加密和公钥可搜索加密来加密外包数据和LBS查询,这可以有效降低计算成本并实现隐私保护搜索。其次,通过使用编码四叉树和布隆过滤器构建了一个高效安全的索引结构,以便云服务器可以快速定位用户的查询区域,以提高检索效率。最后,在随机预言模型下给出了正式的安全分析,并通过实验评估了性能,证明了我们的方案优于现有方案。01. 引言0基于位置的服务(LBS)已经在许多领域得到应用,如军事、医疗、紧急救援等,这是由于移动设备的迅速普及[1]。然而,随着LBS数据集的激增,LBS数据的高存储和计算成本给位置服务提供商(LSPs)带来了沉重的负担。云计算的快速发展为LBS提供了一种新的运行模式,即LSP将大量的LBS数据上传到云端,利用其强大的计算能力来处理用户的查询,从而有效降低了LSP的成本。然而,云计算在促进数据计算和存储的同时也带来了数据安全和用户隐私问题。在传统的计算模式中,用户的数据通常在LSP控制或受信任的平台上进行处理。但是,将数据外包给云服务器(CS)后,数据的物理控制能力就转移到了云端。在外包环境中,CS通常被认为是“半诚实的”,它会诚实地执行用户的查询请求。与此同时,它还会试图从用户的查询和存储的数据中推导出有用的信息[2-5]。因此,在不受信任的云环境中进行LBS数据安全存储和计算已经成为一个迫切需要解决的关键问题。为了在外包环境中实现LBS系统的隐私保护,研究人员提出了一系列位置隐私保护0� 通讯作者。0电子邮件地址:s190802004@stu.cqupt.edu.cn(X. Li)。0方法。曾等人[6]提出了一种基于增强的对称标量积保留加密算法和加密倒排索引技术的新搜索方案,以支持在云环境下对加密数据进行通用LBS查询。在该方案中,用户可以指定地理范围和搜索关键词。搜索后,CS返回与给定区域和关键词匹配的兴趣点(POI)记录。杨等人[7]提出了一种基于Voronoi图、2-Hop标签索引和一些密码原语的道路网络环境下kNN查询的可验证隐私保护方案,可以同时保护空间数据和kNN查询的隐私,并验证查询结果的可靠性。谢和王[8]提出了一种基于属性加密的LBS隐私保护方案(CP-ABE),它计算并比较授权用户的位置距离,而不会泄露其隐私。朱等人[9,10]针对LBS范围查询服务过程中的隐私和效率问题,利用改进的同态加密算法设计了一种具有高效隐私保护的LBS圆形区域和多边形区域范围查询方案,可以在确保用户查询隐私和LSP数据机密性的同时提供查询服务。然而,现有关于LBS数据外包的隐私保护的研究主要集中在地理范围或兴趣关键词查询上,很少支持top-k查询。此外,LBS数据的检索算法未能保护用户的搜索模式。0https://doi.org/10.1016/j.csa.2022.100007 收稿日期:2022年4月19日;修订稿收到日期:2022年6月10日;接受日期:2022年8月18日 在线发表日期:2022年8月23日2772-9184/© 2022 The Authors. Published by Elsevier B.V. on behalf of KeAi Communications Co., Ltd. 本文是根据CCBY-NC-ND许可(http://creativecommons.org/licenses/by-nc-nd/4.0/)的开放获取文章。Y. Zhou, X. Li, M. Wang et al. Cyber Security and Applications 1 (2023) 100007 2 0图1. 系统模型。0我们的贡献概述如下:1)首先,我们提出了一种用于LBS外包数据的top-k查询方案。为了保护LBS数据和用户的查询免受攻击者的侵害,我们利用增强的非对称标量积保留加密和公钥可搜索加密来构建我们的安全查询方案,同时支持对加密的LBS数据进行准确的top-k搜索。2)其次,我们基于编码四叉树和布隆过滤器构建了一个安全的索引结构,使得CS能够快速定位用户的查询区域和用户的查询请求,从而提高检索效率。3)最后,我们进行了正式的安全性证明和基于实验的性能分析,表明我们提出的方案是安全和高效的。组织。我们的论文其余部分组织如下。0第2节介绍了系统模型和设计目标。在第3节中,我们介绍了一些初步知识。然后,在第4节中详细介绍了所提出方案的构建。安全分析和性能评估分别在第5节和第6节中进行了演示。最后,在第7节中对论文进行了总结。02. 问题陈述02.1. 系统模型0我们的方案旨在为用户提供安全和高效的查询服务,同时确保LBS数据的安全性和用户查询的隐私性。有三个实体:位置服务提供商(LSP)、云服务器(CS)和LBS用户,如图1所示。0∙位置服务提供商(LSP):LSP拥有大量的LBS资源。它将大量的LBS数据外包给CS,以从廉价的存储和可靠的计算服务中受益。为了保证LBS数据的保密性,每个LBS数据都将首先加密,然后上传到云端。此外,LSP还为LBS用户提供注册服务。一旦用户通过注册,LSP通过安全通信渠道向用户发送认证证书和密钥。0∙云服务器(CS):CS拥有丰富的存储和计算资源,负责存储来自LSP的密文数据集,并为用户提供LBS查询服务。0∙LBS用户:LBS用户首先向LSP注册以获取密钥。为了保护隐私,用户的查询请求以陷阱门的方式提交给CS。02.2. 设计目标0在本文中,假设CS是“诚实但好奇”的。换句话说,它会诚实地执行用户的查询请求,但也会尝试0从用户的查询和存储的LBS数据中研究有用的信息。与其他相关研究一样[2,3,6,7,9],假设LSP和用户是诚实的,并且LSP和用户不会与CS共谋获取其他用户的隐私。因此,为了保护LBS数据和用户的查询,我们的方案实现了以下安全目标:(1)保密性:CS无法理解LSP存储的任何LBS数据内容。外包的LBS数据已加密,以防止CS从数据集中获取任何有效信息。(2)隐私性:用户的查询应对CS保密,因为它包含区域和个人兴趣等私人信息。为了确保用户的查询隐私不被泄露,本文将用户的查询请求加密并以查询陷门的形式提交给CS,从而防止CS获取有关用户查询的任何有用信息。03. 准备工作0本节介绍了我们方案中使用的一些基础知识,包括双线性配对映射、困难问题假设和布隆过滤器。03.1. 双线性配对映射0�和� � 是两个�阶乘法循环群,其中�的生成元为�。�∶�× � → � �是一个双线性映射,具有以下性质:(1) 双线性性:对于任意�,�∈���,有�(� �,� �) = �(�,�)��。(2) 非退化性:�(�,�) ≠ 1。(3)可计算性:存在一个概率多项式时间(PPT)算法来评估�(�,�)。03.2. 困难问题假设0决策性双线性迪菲-赫尔曼(DBDH)假设:假设存在一个�阶群�和一个生成元�。给定� �,��,� �∈ �,�∈ � �,其中�,�,�∈ ���,DBDH问题是0cide � ? = � ( � , � ) ��� . m决策性线性(mDLIN)问题:mDLIN问题是DLIN问题的一个变种。假设存在一个群�,其阶为�,生成元为�。给定� �,� �,� ��,� �∕�,��,其中�,�,�,�,�随机选择自���。mDLIN问题是确定0� � ? = � � + �。03.3. 布隆过滤器0布隆过滤器可以轻松确定一个元素是否属于当前集合,其核心是一个位数组和�个独立的哈希函数��∶{0,1}�→{1,2,…,…,�},�∈[1,�],数组中值的初始状态为0。给定一个集合�={� 1,� 2���},选择�个哈希函数将每个元素映射到布隆过滤器,并将每个生成的哈希值的位位置设为1。在验证某个元素� �,�∈[1,�]是否存在于集合�时,使用�个哈希函数将��映射到布隆过滤器。如果其中一个对应位置为0,则��必定不属于�。如果每个对应位置都为1,则��可能是�的成员,如图2所示。布隆过滤器的错误率�定义为:0� = 1 − ( � − �� � ) � (1)0其中�为位数组的长度,�表示�的大小,�表示哈希函数的数量[3]。04. PPT-LBS的构建0本节描述了我们提出方案的具体构建。我们的方案是基于赵等人[11]改进的,其3 0Y. Zhou, X. Li, M. Wang等.网络安全与应用1 (2023) 1000070图2. 布隆过滤器的示意图。0表1 符号定义0符号定义0M 1 , M 2 可逆矩阵0� 矩阵维度,在本方案中设定�=800� ∈ {0 , 1} � 长度为 � 的位串0(( � � , � � ) , � ) 用户的坐标为( � � , � � ),查询半径为 �0� � 用户的查询关键词0� 用户想要查询距离他/她位置最近的POI数量0� 交集区域0� � 所有扩展码序列的集合0使用户能够执行POI的关键字查询和top-k查询。例如,Alice想要查询距离他/她500米范围内最近的三家餐馆。同时,在确保她的位置和查询关键词不泄露的前提下,CS返回符合Alice条件的POI记录。所提出的方案由八个阶段组成:系统初始化、密钥生成、用户注册、LBS数据加密、索引构建、LBS查询生成、LBS数据检索。所使用的符号如表1所定义。04.1. 系统设置0系统设置用于生成一些公共参数,由LSP执行。具体步骤如下:(1)LSP选择两个具有大素数阶�的乘法循环群�和� �。令�为�的生成元,�∶�× � → ��为双线性配对映射;(2) LSP选择一个单向哈希函数�0∶{0,1}�→�和一个具有�个哈希函数��∶{0,1}�→{1,2,…,…,�}的哈希族,其中�表示布隆过滤器的大小,其主要功能是将位串映射到布隆过滤器向量。LSP公开公共参数�����={�,� �,�,� 0,� �},�∈[1,�]。04.2. 密钥生成0(1)LSP选择两个�×�维的可逆矩阵M1,M2,长度为�和�−3的比特串�和{��}�∈[1,�−3。这里矩阵维度�应足够大以抵抗暴力破解攻击,矩阵维度设为�=80;(2) ���={M1, �, {��}�∈[1,�−3]}存储为LSP中的安全密钥,用于用户生成陷门和解密数据;(3)LSP随机选择��∈���并设置其私钥���=��,公钥为���=���。04.3. 用户注册0当新用户加入LBS系统时,LSP在此阶段注册用户。0图3. 地图划分。0(1) 用户随机选择��∈���并设置其私钥���=��,公钥为���=���;(2)用户计算注册信息����=�0(���),并将其发送给LSP进行注册请求;(3)当LSP接收到用户发送的注册请求消息时,LSP为用户计算认证证书��=�((����)���,�)并通过安全通信渠道将���发送给用户;(4)LSP将��发送给CS,CS将其存储在用户列表中以供后续用户认证。04.4. LBS数据加密0LSP中存储的POI数据集表示为DB={�1, �2, … , ��}。为简单起见,使用��={(�, �),�}表示一个POI记录,其中(�,�)表示POI的坐标,�表示POI的关键词(例如餐馆、酒店、酒吧等)。为了确保数据的机密性,LSP以密文形式将数据集DB外包给CS。(1)坐标加密 对于POI坐标(�,�),LSP生成一个�维向量��,其中数据的前三个维度为(�, �, −0.5(�2+�2))。对于�∈[4,�],设置��[�]=��−3。然后,根据比特串�,��被分割成两个�维向量���和���:0∙ 如果�[�]=1,�∈[1, �],则设置���[�]+���[�]=��[�];∙ 如果�[�]=0,�∈[1,�],则设置���[�]=���[�]=��[�]。计算:C�=M1����,C�=M2����。输出坐标密文:�����={C�, C�}。(2)关键词加密 LSP随机选择�∈���,并推导关键词密文0��={��1, ��2},其中0��1 = �0(�)������,(2)0��2=����。(3)0到目前为止,一个POI密文数据��表示为:�� = {�����,��}。LSP对DB中的所有POI数据进行加密,密文数据集表示为:EDB = {���},�∈[1,�]。LSP将密文数据集EDB上传到CS。04.5. 索引构建0(1) 地理数据的二进制编码 LSP递归地将地图分成四个区域,直到每个子区域中存储的POI数量不超过指定阈值。同时,LSP选择00,01,10,11来表示四个区域,每个区域可以用一个比特串来表示,如图3所示。例如,在图4中,整个区域被划分为四个子区域,编码为00,01,10,11。比特串“01”表示的右上子区域进一步划分为编码为0100, 0101, 0110,0111的四个子区域,“0101”区域再次被划分,依此类推,使得每个区域都是唯一的比特串编码。4 0Y. Zhou, X. Li, M. Wang等人.网络安全与应用1 (2023) 1000070图4. 区域的分层编码。0(2) 编码四叉树索引构建LSP使用四叉树存储上述划分区域的比特串和POI密文数据。在这种编码四叉树索引结构中,根节点表示整个区域,每个非叶节点有4个子节点表示四个子区域。非叶节点存储每个区域的比特串,叶节点存储区域内的POI的密文。对于给定的POI数据�,LSP首先将其加密为��,然后找到其子区域编码,最后将其添加到编码四叉树的相应叶节点中。以在比特串为“001001”的区域中插入数据为例。从根节点开始搜索数据记录,分别属于子区域00, 010,01001。然后,数据记录被插入到子区域001001中,如图5所示。04.6. LBS查询生成0LBS用户的查询请求可以表示为:{(( � � , � � ) , � ) , � � , �},其中(( � � , � � ))是用户当前坐标和查询半径,� � 是用户的查询关键词,�是用户想要查询的最接近其位置的POI数量。在基于云的LBS系统中,为了防止私人查询被泄露,用户将以陷门形式发送查询。0图6. 用户查询示例。0(1)索引陷门 V �� 生成首先,用户根据当前位置( � � , � � )和查询半径 �计算圆形区域,如图6的绿色阴影部分所示。用户查询范围与分割的子区域的交集表示为 � = { � 1 , � 2 , … , � � },如图6的蓝色阴影部分所示。一旦确定了 �,即 � = { � 1 , �2 , … , � 7 },它可以通过列出每两个相邻位的 � � ( � ∈ [1 ,7])的所有前缀子串来扩展为一系列位串。例如,假设一个位串是111101,扩展的码序列表示为 � �,� � = { 11 , 1111 , 111101 }。用户将所有查询子区域 � � ( � ∈ [ 1 ,�])的扩展码序列组合起来得到一个集合0码序列,� � = � = � �0� =1 � �。对于 � � 中的每个位串,用户使用0� 个哈希函数 � � ∶ { 0 , 1 } � → { 1 , 2 … … � },� ∈ [1 , �],对 � �中的每个位串序列进行哈希,以获得索引陷门 V ��。0图5. 数据插入示例。5 0Y. Zhou, X. Li, M. Wang等人。网络安全与应用1(2023)1000070图7. 范围推导示例。0以图7为例。假设用户当前坐标为(26,81)。用户首先根据查询半径 �确定查询范围,表示为绿色圆形区域,其与分割的子区域的交集为蓝色阴影部分,表示为 � = { � 1 , … … , � 5 }。七个子区域的位串为 � = {1100 , 1101 , 1110 , 111100, 111101 , 111110 , 111111}。然后用户将这些位串扩展为集合 � � = { 11 , 1100 ,1101 , 1110 , 1111 , 111100 , 111101 , 111110 , 111111}。最后,用户使用 �个哈希函数对 � � 中的所有位串进行哈希,以获得索引陷门 V ��=10101100101011。(2)坐标陷门的生成用户随机选择正整数�,计算数据的前3个维度( �� � , �� � , �)。对于 � ∈ [4 , � - 1],设置 � q [ � ] = � � ( � �是一个随机数)。0维数)。对于最后一个维度,设置 � q [ � ] = − ∑ � −1 � =4 � � −3 � � � � −3。然后, � q 为0根据位串 � 将其分割为两个 � 维数据 � q � 和 � q � :0∙ 如果 � [ � ] = 0,� ∈ [ 1 , �],设置 � q � [ � ] + � q � [ � ] = � q [ �];∙ 如果 � [ � ] = 1,� ∈ [ 1 , �],设置 � q � [ � ] = � q � [ � ] = � q [�]。计算:T � = M 1 −1 � q �,T � = M 2 −1 � q �。输出坐标陷门:� � = { T � , T�}。(3)关键词陷门的生成由于用户搜索的关键词可能暴露敏感信息,如兴趣、爱好、行为习惯等,用户在发送查询请求前需要对搜索关键词进行加密。用户首先选择其查询关键词 � �,然后随机选择 � ′ ∈ � � �0加密 � � 成为 � � = { � � 1 , � � 2 , � � 3 },其中0� � 1 = � ( � 0 ( � � ) � � � , � � � � ′),(4)0� � 2 = � � ′,(5)0� � 3 = � � � � ′。(6)0用户向CS发送查询陷门 TRAPDOOR = { � � � � , V �� , � � , � � , � }。04.7. LBS数据检索0CS一旦收到用户的TRAPDOOR,首先验证用户的身份,并确定是否建立了��=�(���,����)。如果没有,CS拒绝查询;否则,CS搜索用户的查询。具体步骤如下:0图8. 坐标匹配示例。0(1) 坐标匹配用户从用户的查询陷门中接收V��后,CS利用它搜索编码四叉树。在编码四叉树中,每个非叶节点由一个比特串表示。CS检查节点的��的映射位置是否在V��中都是“1”。如果是,CS随后向下搜索编码四叉树;否则,CS更改分支继续搜索,直到击中��中的所有数据,如图8所示。CS将这些数据存储在临时资源列表(TRL)中,然后进行步骤(2);(2) 关键字匹配 验证TRL中的数据��1��(��2, ��2)=�(��1,��3)是否建立。如果建立,表示POI记录符合用户的查询关键字,然后进行步骤(3);否则,选择下一个POI记录进行匹配;(3) 最接近的�个POI 假设{�1�, �1�}和{�2�,�2�}是数据的密文0���1和���2分别,{��,��}是用户查询的陷门。确定(C1�−C2�)��+(C1�−C2�)��>0是否为真。如果为真,则���1对用户比���2更近。最后,CS执行距离比较和排序,并将前�个加密的POI返回给用户。Pr ||𝜇′ = 𝜇 = 1 2 + 𝜖𝐶 ⋅ Pr 𝑡𝑒𝑟 . (10) 6 0Y. Zhou, X. Li, M. Wang等人。网络安全与应用1 (2023) 10000704.8. 用户解密0用户从CS获取�个指定的POI密文记录,表示为0{C��, C��},�∈[1, �]。对于POI的一个密文记录,用户首先计算:0���=��(M�1)−1×C�,(7)0���=��(M�2)−1×C�,(8)0其中��=(��, 0)是一个2×80矩阵,��是一个2×2的单位矩阵。0对于���和���,如果��=1,�∈[1,2],则设置���[�]=���[�]+���[�];否则0���[�]=���[�]=���[�]。POI的真实坐标是(�=���[1], �=���[2])。05. 安全性分析05.1. 数据保密性0对于每个LBS数据,LSP以密文形式将其外包给CS。具体来说,对于POI记录的坐标,我们使用增强的ASPE算法[12]对其进行加密。在已知密文模型中,如果CS想要获取POI坐标的真实值,必须从密文中恢复两个矩阵M1,M2,并正确猜测比特串�。对于CS,用于确定转换矩阵的方程是:C�=M�1×���和C�=M�2×���,其中M1和0未知的�×�维矩阵中,M1和M2中有2�2个未知数。向量���,���从�维比特串�中中有2�个未知数。由于只给出了2�个方程,这少于未知数的数量,因此转换矩阵无法在没有足够信息的情况下被对手解决。此外,Wong等人[12]的安全性分析表明,当�=80时,其安全性等同于1024位密钥RSA加密算法。因此,在密钥安全的前提下,CS不能通过密文数据恢复POI的真实位置。0引理1.假设mDLIN问题很难,那么对于任何概率多项式时间对手�,区分关键字密文的概率优势Adv��(�)是可以忽略的。0证明1.假设存在一个对手�,能够以非常规概率优势��正确区分关键字密文。我们证明挑战者可以以非常规优势��解决mDLIN问题。给定参数为(�, ��, ��, ���, ��∕�, �) ∈�的mDLIN问题实例,其中�, �, �, � ∈���,�的目标是确定�=��+�或�的随机元素。�设置�∈{0,1},如果�=��+�,则�则�=1。0(1) 初始化:挑战者 � 设置 ( � � � , � � � ) = ( � � , � � ) 并将其发送给对手 � 以及公共参数 ����� = ( � ,� � , �, �, � )。(2) 查询:� 可以向 � 请求以下查询:a) 哈希查询 � �:� 向 � 发送关键以进行哈希查询。�0将执行以下操作:� � 维护一个最初为空的列表 � � � � � , � � , � � , � � � 用于 �� 已经出现在 � � 中,� 发送响应 � ( � � ) = � � 给 �。� 否则,� 生成一个随机数 以概率的方式,使得 � � [ � � = 0] = �。如果 � � = 0,随机选择 � � ∈ � � � 并计�;否则,设置 � � = � � �。� � 存储元组 � � � , � � , � � , � � � 在 � � 中并返0� 。b) 密文查询 � �:� 向 � 发送关键词 � � 以进行密文查询,并且 � 从列表 � � 中� , � � � 。如果 � � = 0,它随机输出一个比特 � ′ ∈ { 0,1 } 作为它对 �的猜测。否则,它随机选择 � � ∈ � � � 并计算密文 � � = ( � 1 , � 2 ) =0( ( � � � ) � � � � � = � � � � + � � , ( � � ) � � )。� 然后将 � � 返回给 �0c) 陷门查询 � �:� 向 � 发送关键词 � � 以进行陷门查询,并且 � 从列表 � � 中检索 � � � , � � , � � , � � �。如果 � � = 0,它随机输出一个比特 � ′ ∈ { 0,1 } 作为它对 �的猜测。否则,它随机选择 � � ∈ � � � 并推导出陷门 � � = { � 1 , � 2 , � 3 } = { � ( � � � � , � � � � ) = �( � ( � � ) � , � � � � ) , � � � , � � � � } 。� 然后将 � � 返回给 �。(3) 挑战:在多项式查询之后,� 向 �发送两个关键词 � � 0 , � � 1,这两个关键词尚未被 � � 或 � � 查询。然后,� 执行以下操作:� � 对 � � 0 , � � 1 分别执行哈希查询:� ( � � 0 ) = � � 0 和 � ( � � 1 ) = � � 1。� � 0 , � � 1 对应于元组 � �* 0 , � * 0 , � * 0 , � * 0 � 和 � � * 1 , � * 1 , � * 1 , � * 1 �,如果 � * 0 , � * 1 都为 1,�中止查询并随机输出 � ′ ∈ { 0,1 } 作为它对 � 的猜测;� 如果 � * 0 和 � * 1中至少有一个为 0,设置 �� 为比特,使得0� � �� = 0。� 计算密文 � � = ( � � 1 , � � 2 ) = ( � � ( � � * �� ) � � � � � , � � � � )0( � + �� * �� ),� * 2 = � � � �,其中0� + � � 在 � 视角中是随机的。如果 � 是 � 的随机元素,那么 � * 1也是随机的。此外,由于 � � 是随机的,� * 2 在 � 中也是随机的0视角。(4) 更多的陷门查询:� 向 � 发送 �� 以进行更多的陷门查询,其中 �� ≠ � � 0,�� ≠ � � 10并且 � 像以前一样响应查询。(5) 猜测:� 输出它的猜测 � � ′ ∈ {0 , 1} . 如果 � � ′ = ��,则 �输出 � ′ = 0;否则,� 输出 � ′ = 1。参考[13],我们使用 ��� 来表示挑战者 � 的两种情况0在游戏过程中中止,如下:� 当 � 模拟 � � 和 � � 时,� � = 0。由于每个 � �都是随机且独立选择的,� 中止游戏的概率是 Pr | | �� � 1 | | = (1 − � ) � � + � �,其中 � � 和 � �分别表示对手 � 最多调用 � �,� � 次查询 � � 和 � �。� 在对手 � 选择的挑战关键词中,� � 0 = � �1 = 1,� 中止游戏的概率是 Pr | | �� � 2 | | = 1 − (1 − � ) 2。因此,�不中止游戏的概率是 Pr | || ��� | || = ( (1 − � ) � � + � � )(1 −0� � + � � +2,概率 � � || | ��� || | 达到最大值0最大值:0� � | || ��� | || = ( � � + � �0� � + � � + 202�20� � + � � + 2,(9)0� 猜测位 � 的成功概率(即解决 mDLIN 问题)是:0如果 � � 是非可忽略的,那么 | | Pr [ � ′ = � ] − 1∕2 | |也是非可忽略的。05.2. 用户查询隐私0每个LBS数据在用户查询时将被加密并提交给CS作为查询陷门。具体来说,对于POI坐标,如加密阶段中所讨论的,向量 � q 也将根据位串 � 分成两个随机向量 � q � 和 � q� 。由于CS无法获得可逆矩阵 M 1 ,M 2 和位串 �,经过一系列的操作,如分割和矩阵乘法,CS无法获取用户的实际坐标和查询半径与用户的查询陷门。0引理 2. 假设DBDH问题是困难的,那么对于任何PPT �,我们方案中违反关键词陷门隐私的概率优势 Adv � � ( � ) 是可以忽略的。0证明 2. 假设存在一个概率多项式时间的对手 �可以违反我们提出的方案的陷门隐私,其优势是非可忽略的。 𝑞 𝑇7 0Y. Zhou, X. Li, M. Wang 等人。《网络安全与应用》1 (2023) 1000070那么存在一个挑战者 �,其解决DBDH问题的概率不能被忽略。给定DBDH问题的实例,参数为 ( � , � � , � � , �) ∈ � ,� ∈ � � ,其中 �, �, � ∈ � � � ,� 的目标是确定 � = � ( � , � ) ��� 或随0� � 中的元素 � 的成功概率是:0(1) 初始化:� 设置 ( � � � , � � � ) = ( � � , � � ) 并将其发送给对手以及公共参数 ����。(2) 查询:� 可以向 � 询问以下查询:a) 哈希查询 � � : � 将关键词 � � 发送给 �进行哈希查询。�0将执行以下操作: � � 维护一个最初为空的列表 � � � � � , � � , � � , � � � 用于 出现在 � � 中,� 向 � 发送响应 � ( � � ) = � � 。 � 否则,� 以概率随机选择 � � 0� � [ � � = 0] = � 。如果 � � = 0 ,随机选择 � � ∈ � � � 并设置 � � = � � + � 0� � = � � � 。 � � 将元组 � � � , � � , � � , � � � 存储到 � � 中并返回 � ( � � ) = � �0返回给 � 。b) 密文查询 � � : � 将关键词 � � 发送给 � 以进行密文查询,� 从列表 � , � � , � � , � � � 。如果 � � = 0 ,则中止查询并随机输出一个位 � ′ ∈ { 0,1 } 作为的猜测。否则,它随机选择 � � ∈ � � � 并计算密文 � � = ( � 1 , � 2 ) =0( ( � � � ) � � � � � = � � � � + � � , ( � � ) � � ) . � 然后将� � 返回给 � . c) 陷进行陷门查询,然后 � 从� � 中检索 � � � , � � , � � , � � � 。如果 � � = 0,则中止查询并随机输出一个位 � ′ ∈ { 0,1 } 作为其对 � 的猜测。否则,它随机选择 �� ∈ � � � 并推导出陷门 � � = { � 1 , � 2 , � 3 } = { � ( � � � � , � � � � ) = � ( �然后将 � � 返回给 � . (3) 挑战:在多项式查询后,� 向 � 发送两个关键词 � � 0 , � � ,这两个关键词既没有被查询到 � � 也没有被查询到 � � 。然后,� 执行以下操作: �� 0 , � � 1 分别执行哈希查询:� ( � � 0 ) = � � 0 和 � ( � � 1 ) = � � 1 。� � 0 , , � * 0 , � * 0 , � * 0 � 和 � � * 1 , � * 1 , � * 1 , � * 1 � ,如果 � * 0 , � * 1 都为 1 中止查询并随机输出一个位 � ′ ∈ { 0,1 } 作为其对 � 的猜测; � 如果 � * 0 和 � * 1中至少有一个为 0 ,则令 �� 为满足 � � �� = 0 的位。� 计算陷门 � * = { � � 1 , � ,其中0��1=���(��,����)����,��2=���,��2=����。如果�=�(�,�)���,则�*1=0�)0�(���′,���),�输出0;如果�是��的随机成员,则�*1也是��中的随机元素,�输出1。另外,由于��是随机值,�*2,(4)更多陷门查询:�发送��给�进行更多的陷门查询,其中��≠��0,��≠��10并且�像以前一样响应查询。(5)猜测:�输出其猜测��′∈{0,1},如果��′=��,则�否则�输出�′=1。参考[13],我们使用���来表示挑战者�0在游戏过程中中止,如下:�当�模拟��和��时,��=0。由于每个��0随机选择,并且分别选取挑战者��0 = ��1 =1的挑战关键字,攻击者中止游戏的概率为Pr || �� � 2 || = 1 − (1 − �)2。因此,0�在游戏中不中止的概率为Pr || ��� || = ((1−�)��+��)(1−0� � + � � +2,概率� � || | ��� ||| 取最大值0表2 符号定义。0符号定义0� LBS数据量0� 数据维度,本文假设� = 20�� 群上的一次指数运算操作的运行时间0� � 群上的一次乘法操作的运行时间0�� 双线性配对操作的运行时间0� �� 普通乘法操作的运行时间0最小值:0� � | || ��� | || = ( � � + � �0��+��+202 � 20��+��+2,(11)0成功猜测位�(即解决DBDH问题)的概率为:0Pr || �′=� || = 02 + � � � Pr ||| ��� ||| . (12)0如果��是不可忽略的,则| | Pr[�′=�]−1∕2||也是不可忽略的。05.3. 索引安全0引理3. 即使攻击者�获得索引,成功推导关键字或坐标的概率也是可以忽略的。0证明3.在我们的方案中,子区域的位串存储在编码四叉树的每个非叶节点中,LBS数据密文存储在叶节点中。即使攻击者获得了编码四叉树,也无法在没有密钥的情况下解密数据密文。当用户查询时,假设查询范围为{(��,��),(��,��),�},其中(��,��)和(��,��)分别表示查询区域�的左上角和右下角顶点,�表示查询区域�中的子区域数量。由于用户的位置坐标可以在任何划分的子区域中,正确猜测用户在某个子区域的位置的概率为1/n。另外,鉴于哈希函数的单向性,即使索引V��泄露,攻击者也无法获得任何有价值的信息。06. 性能评估0在本节中,我们分别从数据加密、陷门生成和数据检索的角度分析了PPT-LBS的性能。实验在Windows 10操作系统上运行,使用Intel(R) Core(TM) i5-10200HCPU @2.40GHz和16GB内存。加密操作是通过使用Java Pairing-BasedCryptography (JPBC)库实现的。 (1) 计算成本比较为方便起见,表2列出了比较中使用的符号描述定义。由于矩阵和向量乘法操作、哈希操作、对称加密和解密操作的时间成本相对较低,在比较中被忽略。0表3显示了PPT-LBS和现有方案[9,14,15]在计算成本方面的比较结果。(2) 特征比较在表4中,我们的方案和现有方案0[9,14,15]进行了比较。(3) 实验比较图9显示了我们的方案与现有类似方案[9,14,15]在数据加密阶段的比较结果。其中,我们的方案和欧等人[14]的方案使用矩阵运算和公钥可搜索加密来处理LBS坐标和关键词。计算成本低于林等人[15]和朱等人[9]的方案,后者使用同态加密。8 0Y. Zhou, X. Li, M. Wang等人.网络安全与应用1(2023)1000070表3 每个阶段的计算成本比较。0数据加密 诱饵生成 数据检索0欧等人[14] � ( � � + � � ) 2 � � � ( 2 � � + � � )0朱等人[9] � ( 6 � � + 2 � � ) 4 � � � �� � 2 � � ( 5 � � + 2 � � )0林等人[15] �� ( 3 � � + � ��
下载后可阅读完整内容,剩余1页未读,立即下载
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功