K-匿名批量认证的位置隐私保护机制.pdf

第 卷第 期重庆邮电大学学报(自然科学版).年 月 ().:./.匿名批量认证的位置隐私保护机制收稿日期:修订日期:通讯作者:宋 成 .基金项目:国家自然科学基金项目()河南省科技攻关计划项目():()()杨囡囡宋 成(河南理工大学 计算机科学与技术学院河南 焦作)摘 要:针对当前位置隐私的安全与效率问题提出一种 匿名批量认证的位置隐私保护方案 方案在基于位置服务()请求用户身份匿名化处理的基础上在相邻网格区域中生成 个假位置采用位置熵进一步选取最优的 个合并真实用户位置形成 匿名增强用户隐私度通过 批量认证 个用户匿名身份提高运算效率降低服务响应时间 安全性分析表明提出的方案满足匿名性、不可伪造性、抗假冒攻击等安全特性 仿真结果表明提出的方案不仅在隐私度方面具有一定的优越性而且在效率上也有所提升关键词:匿名位置熵批量认证位置隐私中图分类号:文献标志码:文章编号:()(.):.:引 言随着移动终端设备、通信技术、定位技术及地理信息系统的迅猛发展用户对位置服务()的依赖性大幅增强如短距离导航、滴滴打车、手机点菜等 但用户在享受位置服务便利的同时用户的个人兴趣、行踪轨迹等隐私信息也存在泄露的风险 若攻击者获取用户位置信息或许给用户的人身安全造成威胁 随着人们生活节奏的加快在确保安全性的基础上用户对位置实时性要求也越来越高 因此位置隐私保护技术的安全和效率是当前信息安全领域的热点之一近年来学者们针对位置隐私问题展开大量研究并取得了一系列的成果 文献构建一个包含位置隐私和细粒度访问控制的双服务器体系架构提出一种基于安全多方计算和同态加密机制的双重位置加密协议和密文位置搜索协议实现了安全精确的 近邻检索但同态加密机制算法复杂计算量较大 文献提出一种双曲线查询解析技术采用单向转换加密将用户位置坐标转换成 序列该方案在数据转换过程需要额外的处理机制来保证较高准确度使得处理复杂度、计算量增加 文献在 端和用户端使用属性加密算法实现位置查询服务和反馈中零信息泄露但通信和计算相对复杂 文献通过 元线性方程组的解实现匿名若系数矩阵的秩小于 则有无穷多解将解和真实身份进行哈希值作为假身份标识当有用户加入或退出时对应的数据表需要更新 文献利用模幂运算实现匿名但在整个过程中匿名认证的空间复杂度高效率较低 文献利用哈希实现匿名但攻击者可根据用户与可信第三方的交互信息求解假名和身份标识之间的对应关系文献使用具有标志性的位置点代替真实用户发起查询但查询结果依赖于代替位置点信息其服务质量难以保证 文献在敏感路段进行等级划分根据位置树的高度分配相应的隐私预算添加 噪声尽管数据可用性较高但服务质量有待提升 文献基于半可信第三方服务的隐私保护系统结构在网格内使用历史查询概率和位置偏移构建 匿名集虽然 博弈优化隐私保护水平但系统整体运行效率不高 文献使用服务相似地图将满足用户服务质量的区域与真实用户所在区域合并构成匿名候选区在候选区域中使用位置熵构建 匿名集并在 匿名集中使用贪心策略选择一个位置点代替真实用户进行服务请求但用户的位置隐私信息通过区域连续关联性可被获取 文献提出无可信第三方的 匿名假位置技术使用语义差异、查询概率以及位置的分散均匀程度构造假位置集避免攻击者结合背景知识攻击但移动用户端计算开销大 文献考虑现在的隐私技术很少关注位置语义信息结合 匿名、语义多样性、差分隐私等技术来保证匿名区域的隐私性 虽然半可信第三方可平衡计算开销但需要合理分配隐私预算 预备知识.位置隐私保护系统架构位置隐私保护系统架构如图 所示系统架构由 部分组成:移动用户终端、可信匿名服务器和 服务器各部分的功能如下图 位置隐私保护系统架构.)移动用户终端 向可信匿名服务器发送匿名化请求筛选出最优的假位置集向 服务器发送查询请求并接收 服务器查询结果)可信匿名服务器 处理移动用户端发送的匿名化请求并将注册结果返回给用户公布系统参数)服务器 批量认证用户处理移动用户终端发位置服务请求并将查询结果返回给用户.位置熵位置熵起源于香农熵是一种度量隐私保护方法熵越大真实用户不被识别的可能性越大 假设在 个位置单元候选区域中有 个候选假位置构成的匿名集合为匿名集合第 个位置的查询概率()则匿名集合中每个位置单元是真实用户的概率为 ()在 个位置单元候选区域中有 个候选假位置构成的匿名集合匿名集合中某一位置单元的查询概率为 那么位置熵为()()第 期 杨囡囡等:匿名批量认证的位置隐私保护机制 位置隐私保护方案.系统初始化阶段步骤 设 表示阶为 的有限域定义一个椭圆曲线:其中 在 上选择一个阶为 生成元为 的加法群 步骤 匿名服务器选取随机数 作为系统主密钥计算公钥 步骤 定义 个哈希函数:步骤 可信匿名服务器公开系统参数()作为系统私钥保存.注册阶段步骤 用户选取随机数 计算 将 个身份标识和参数()()()发送给可信匿名服务器步骤 可信匿名服务器收到用户发送的注册请求后选择随机数 计算 ()并将()()()通过安全信道发送给用户步骤 用户终端收到消息后验证 是否成立若成立则计算私钥 否则返回第 步重新请求 假身份、公钥和私钥分别为、.假位置生成与选取阶段步骤 以用户所在的位置单元为中心向四周均匀扩展成合适大小的矩形其长为 个网格宽为 个网格在所选矩形区域中均匀使用随机点算法生成假位置()结合真实地图背景信息判断假位置是否合理如果不合理则重新生成步骤 计算()()()并判断()其中、表示真实位置和候选位置之间的最短距离和最长距离 如果该点满足条件则 将该点加入假位置集合 中否则返回第 步重新请求步骤 判断假位置集合 中的元素是否小于 个若小于则返回第 步继续生成否则执行下一步步骤 根据()式计算位置集 中每个假位置的查询概率 然后从 个假位置中选择 较高的 个假位置构成最终假位置集合()步骤 用户为真实位置和假位置集合 分配假身份标识.位置服务请求阶段步骤 随机选取 计算 其中 并将 作为公共参数公布步骤 用户随机选取 计算()为查询请求消息()将()作为用户签名其中表示时间戳将()()发送给 步骤 接收到用户发来的签名和查询请求验证签名消息中时间戳 是否满足不等式 其中 表示数据传输时间 表示网络传输延迟 随后 批量认证匿名用户身份验证 ()()是否成立若成立则根据用户的查询请求获取 个请求对应查询结果并选择随机数 计算 ()将()()发送给用户若不成立则返回第 步重新请求步骤 用户收到 的消息后验证()是否成立若成立则用户 计算 的乘法逆元 并解密 ()获得查询结果若不成立则返回第 步重新请求 方案分析.正确性分析正确性包括 方面:用户验证匿名服务器的可信性验证等式 成立 服务器批量验证匿名用户的身份验证等式 ()()成立成立即可处理查询请求 用户验证 的可信性 验证等式 ()成立)验证 ()验证 ()()重 庆 邮 电 大 学 学 报(自然科学版)第 卷 ()()()()()()()()()()()()()()()()()()()()验证 ()()()()()()()()().安全性分析.匿名性匿名性的验证步骤如下步骤 攻击者 发起询问获取系统公开参数和相关参数步骤 攻击者 选取 个不同的信息 步骤 用户 选取随机位(对攻击者 保密)为用户的真实查询内容然后将 发送给 服务器步骤 服务器对接收到的信息 加密得到 并发送给用户 步骤 若用户 收到密文 与 相对应则将 按照随机顺序发送给攻击者 否则停止游戏步骤 若攻击者 进行解密能够得到 则攻击者 赢得游戏攻击者 赢得游戏的优势为:()()其中()表示攻击者 能够解密获得 即解密获得用户真实查询结果的概率定理 如果攻击者 能以可忽略的概率赢得该游戏那么该方案满足匿名性证明 如果攻击者 得到加密结果 其中()攻击者 尝试以解密密文的方式获取消息 需要在猜测正确 的基础上求解()即需要知道系统秘钥 以及参数、则必须通过、求解、面临求解椭圆曲线离散对数问题 所以攻击者 能够解密用户 的隐私信息 的概率()()可忽略不计即该方案满足匿名性.不可伪造性定理 如果攻击者 在多项式时间内不能假冒可信匿名服务器伪造用户注册信息那么该方案满足不可伪造性证明 如果攻击者 可以在多项式时间内以不可忽略的概率注册与用户 相同的注册信息即攻击者 可以在多项式时间内以不可忽略的概率计算出系统私钥 和参数 使等式 成立挑战者 运行并生成系统参数()并向攻击者 公布其中 为系统私钥并对攻击者 保密攻击者 以身份 发起查询挑战者 检测是否在应答列表中若不在相应的应答列表中挑战者 选取一个随机数 将()储存到列表中否则将相应的应答发送给攻击者 在伪造过程中由于攻击者 不能获取系统主密钥 和随机数 无法使等式 成立若攻击者尝试通过等式 、获取系统主密钥 和参数 则面临求解椭圆曲线离散对数难题 因此攻击者 在多项式时间内不能以不可忽略的概率解决椭圆曲线离散对数问题即该方案满足不可伪造性.抗假冒攻击定理 在求解椭圆曲线离散对数问题是困难的情况下如果攻击者 在多项式时间内不能冒充用户发送正确的签名那么该方案抗假冒攻击证明如果攻击者 试图冒充用户向 服第 期 杨囡囡等:匿名批量认证的位置隐私保护机制务器发送正确签名需向 证实等式 ()()成立攻击者 若使该等式成立必须知道参数、和系统主密钥则攻击者 需要通过、和 求解、以及 求解该问题相当于椭圆曲线离散对数难题 因此该方案抗假冒攻击.仿真实验本方案从假位置生成效率和隐私保护程度两方面对方案进行仿真实验 仿真实验在.英特尔、内存的 机和 仿真软件的环境下进行 实验选取.的真实地理地图将地图划分成 个位置单元实验中的主要影响参数为匿名度.效率分析方案以生成时间作为假位置生成效率匿名度与假位置集合生成的时间关系如图 所示 图 中 种方案生成假位置的执行时间都随着 的增大而增大 在匿名度较小时文献与本方案所需时间相近随着匿名度的增大语义差异、查询概率相近及假位置的分布导致文献假位置集生成时间增大 文献在选取假位置时使用 匿名、多样性、差分隐私来保证匿名区域的隐私性根据 语义多样性在道路网上将各部分划分成不同的区域然后在用户所在的区域结合差分隐私和 匿名选出最优的假位置集使得文献方案运行效率低图 匿名度与假位置集合生成的时间关系.本文方案在响应请求服务时不仅效率有所提高而且减少了信息交互次数 文献构建匿名后向 服务器发送 个连续的查询请求 在进行查询服务前需逐个认证用户然后依次进行查询处理 而本方案在构建 匿名后用户将 个用户签名消息和查询请求一次性发送给 收到服务请求后通过批处理的方式一次性对 个用户的匿名身份进行认证然后处理 个用户的服务请求最后将 个服务请求结果一次性发送给用户从而提高认证效率并且减少 与用户之间的信息交互次数.位置熵位置熵是衡量假位置的重要因素 位置熵越大隐私保护程度越大 匿名度与位置熵关系如图 所示 由图 可知本文方案与文献、随机方案的位置熵随着匿名度的增大而增大 随机方案对假位置的合理性考虑不充分所以隐私保护效果一般 文献在选取假位置时充分考虑到语义多样化、地理位置尽量分散使得假位置更加合理但本方案的位置熵始终优于文献 因此隐私保护效果更好图 匿名度与位置熵关系.结束语为了解决移动用户位置隐私泄露问题本文提出一个基于椭圆曲线密码体制的 匿名批量认证的位置隐私保护方案采用批处理减少信息交互次数提升了执行效率通过在匿名区域中结合随机位置点生成算法和位置熵筛选最优的 个假位置增强用户隐私保护度 安全性分析表明本文方案满足匿名性、不可伪造性、抗假冒攻击等安全特性仿真实验表明本文方案在效率和隐私保护度方面具有一定的优势参考文献:王晓光管港云徐嘉铭等.基于 和计算机图像识别的无人机导航系统.吉林大学学报(理学版)():.重 庆 邮 电 大 学 学 报(自然科学版)第 卷 .()():.袁朝春朱昊宇何友国等.弱 环境下的智能车辆自主导航算法.江苏大学学报(自然科学版)():.()():.王宇航张宏莉余翔湛.移动互联网中的位置隐私保护研究.通信学报 ():.():.():.():.():.杜刚张磊马春光等.基于属性基隐私信息检索的位置隐私保护方法.哈尔滨工程大学学报 ():.():.李涛张静杨皓.一种车载网隐私保护方案的分析与改进.北京邮电大学学报 ():.():.:.():.():.():.李洪涛任晓宇王洁等.基于差分隐私的连续位置隐私保护机制.通信学报 ():.():.夏兴有白志宏李婕等.基于假位置和 博弈的位置匿名算法.计算机学报 ():.():.闫光辉刘婷张学军等.抵御背景知识推理攻击的服务相似性位置 匿名隐私保护方法.西安交通大学学报 ():.():.王洁王春茹马建峰等.基于位置语义和查询概率的假位置选择算法.通信学报 ():.():.:.():.():.作者简介:杨囡囡()女河南焦作人硕士研究生主要研究方向为网络与信息安全、位置隐私等:.宋 成()男河南信阳人副教授硕士生导师主要研究方向为无线通信技术、位置隐私等:.(编辑:陈文星)第 期 杨囡囡等:匿名批量认证的位置隐私保护机制