空间众包中基于多种距离计算的位置隐私保护研究

摘要

空间众包(SC)是一种近几年新兴的代替性平台，不同于传统的解决问题的渠道，人们可以在上面发布时空相关的任务以寻求帮助，让平台的工作者去完成这些任务。总之，SC给不同的社会人带来了一些新的机遇，例如创造了更多的创业就业机会，也给人们的社会生活带来巨大的革新，如使人们的出行更加方便。然而，在SC系统中往往也存在着严重的隐私问题。特别是，位置隐私越来越被研究人员和业界学者所关注。本文提出了在SC系统中基于不同的距离计算的位置隐私保护协议，它们分别是EMB-L3P，MMB-L3P，CDB-L3P以及MDB-L3P。这四种协议对应所用的距离分别是欧氏距离(EM)、曼哈顿距离(MD)、切比雪夫距离(CD)和明氏距离(MD)。同态加密(HE)是所有协议主要所用的加密方法，而前缀家族也应用于MMB-L3P和CDB-L3P，用来进行密文大小比较。此外，为了削弱加密方法所带来的效率开销，本文所提出的协议都构造了数据库存储形式KD树，为加密的工作者位置进行索引。最后，本文对所提出的协议进行了相关的安全分析，证明了协议可以阻止外部强攻击者以及有特权的内部人员得到位置隐私。之后的性能评估针对每个协议的计算开销和通信开销等方面进行分析比较，得出如下结论:1）文中所提出的协议具有可行性，又较基于差分隐私的方法通过插入噪音——伪位置来达到位置隐私保护的目的，具有零分配失败率的优势。2）四种协议除了具有不同的物理应用环境，针对不同的原始数据长度，不同的基站下工作者数量以及不同的候选工作者数量，各有优势。EMB-L3P的两种开销都不受原始数据长度的影响，主要受限于每个基站下的工作者数量影响。而MMB-L3P和CDB-L3P则是随着原始数据的比特位而增长。如果候选工作者的数量小于每个基站中的数量，MMB-L3P和CDB-L3P的计算开销可以有很大程度的降低，两者比值越小，比EMB-L3P越有优势。
　　本文的创新点主要有:
　　不同于其他有关SC论文基于差分隐私方法的位置隐私保护协议，本文所提出的协议采用了HE和前缀家族的方法，对原始位置进行处理后传输，整个过程不进行解密，以密文的形式进行传输、存储和计算，完全消除因加入虚假位置而带来的失败概率。同时，为了提高SC系统的效率，论文中的位置密文以KD树的形式存储，SC服务器在分配任务之前要先由CSP搜索KD树查询到合适的工作者群，然后再进行距离计算寻求一组最合适的候选工作者;
　　本文提出了四种基于不同的距离计算的位置隐私保护协议，分别是EMB-L3P，MMB-L3P，CDB-L3P以及MDB-L3P。针对不同的业务的开展环境，SC系统有不同的协议取向。其中，在道路不规则的城市或者农村，EMB-L3P是首选。而MMB-L3P是针对建筑物成块状排列、街道都是笔直地以直角形式相交的城市，然而，在这样的城市中，每当请求者发布任务地点在不可直达区域时，CDB-L3P更加合适。最后，MDB-L3P是以上三种协议的扩展。

目录

摘要

插图

表格

缩写、符号清单、术语表

1 绪论

1．1 研究背景

1．2 国内外研究现状

1．3 论文主要贡献

1．4 论文组织安排

2 预备知识概述

2．1 系统模型

2．2 攻击模型以及安全需求

2．3 加密系统

2．3．1 双线性映射

2．3．3 切比雪夫不等式

2．4 本章小结

3 基于欧几里得距离计算的位置隐私保护协议

3．1 问题思路

3．2 系统初始化

3．3 工作者／请求者注册

3．4 工作者位置报告

3．4．1 认证

3．4．2 报告

3．4．3 数据完整性验证

3．4．4 KD树构造

3．5 请求者任务提交

3．6 任务分配

3．6．1 距离计算

3．6．2 任务通知

3．7 本章小结

4 基于其他距离计算的位置隐私保护协议

4．1 核心思想

4．2 协议详述

4．2．1 曼哈顿距离

4．2．2 切比雪夫距离

4．2．3 明氏距离

4．3 本章小结

5 安全分析以及性能评估

5．1 安全分析

5．2 性能评估

5．2．1 计算开销，通信开销以及储存开销

5．2．2 实现

5．3 本章小结

6 总结与展望

6．1 工作总结

6．2 未来展望

参考文献

致谢

声明