施文杰

论文信息：

论文发表在TDSC’19上，https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8607097

作者：

Xiaojie Zhu，Informatics Universitetet i Oslo Det Matematisk-naturvitenskapelige Fakultet  

Erman Ayday，Computer Engineering, Bilkent University

Roman Vitenberg，Department of Informatics, University of Oslo

摘要

论文的工作主要关注位置数据的隐私保护这一问题。在目前的移动互联网环境下，位置服务提供商的查询负载非常大，这使得位置服务提供商需要将数据外包到云服务商的云服务器上进行存储，由云端负责响应大量用户的查询服务。这就带来了多方面的数据安全问题，首先位置服务提供商不希望将位置数据泄露给云服务商，其次用户既不希望自己的数据被泄露给云服务商，又不希望位置服务商探查到自己的数据。因此，先前有不少工作都提出了一些针对这一场景的隐私保护框架，这篇论文同样提出了一个针对这一问题的隐私保护框架，克服了一些先前工作的缺陷。论文的工作开创性地提出一种基于Bloom Filter的查询索引，索引根据实际的地理位置组织为层次化的树状结构（如下图所示），使用户能够发送多个位置的联合查询，并支持基于位置属性的查询；同时论文提出在查询索引中加入隐私保护级别这一机制，可以让用户自己对发出的每一条查询规定一个隐私保护级别，防止云服务商探查到用户的查询意图；另外，论文使用了基于密钥策略的属性加密，实现了对用户的细粒度的访问控制。

主要工作

论文主要提出了一种针对位置数据的隐私保护框架，系统中有三类参与者，分别是终端用户（Client）、位置服务提供商（LBSP）以及云服务商（CSP）。各参与者的大致交互流程如下图所示，

    图中LBSP掌握所有的位置数据，并对数据生成索引，使用KP-ABE加密数据，使用FHIPE加密算法对索引进行加密（FHIPE加密算法是斯坦福大学的Sam Kim和Facebook的Kevin Lewi等人于18年提出的一种内积加密算法），这些工作都是离线进行的。这部分工作完成后，LBSP将数据和索引上传到CSP。用户要想发出查询请求，必须先到LBSP注册用户身份，每次发出查询请求前先对查询加密，LBSP给加密后的查询生成一个盲签名，确保用户发出的查询内容不会泄露给LBSP和CSP双方。

论文中最主要的工作在于构建了一种基于Bloom Filter的索引结构，如下图所示，

根据实际的地理划分，将位置数据组织成一个层次化的树状索引结构，每个叶节点都表示一个位置数据，并将其映射到一个Bloom Filter中。每个非叶节点表示一个地理划分，并且非叶节点同样也用一个Bloom Filter表示，由其子节点的Bloom Filter向量做OR操作生成。而用户发出的query也同样表示成一个Bloom Filter，这样，系统在处理用户发出的查询请求时可以很容易通过对query和非叶节点向量做内积操作来判断每个非叶节点所包含的地理范围是否包含query中的各个位置。

论文中还提出了一个保护query本身的隐私的方案，用户可以在发出每条query之前对这个query设定一个隐私级别，云端会根据这个隐私级别给用户返回一个包含位置的地理范围，而不返回这个位置本身，以此来保护query本身的隐私。具体做法是给上面的索引树中的每个节点计算一个熵值，如下图所示，熵值从下往上越来越大，熵值越大，则代表隐私级别越高，返回的结果越模糊。处理query时，如果查询算法遍历到某个节点时发现该节点的隐私级别和用户指定的隐私级别相同，就停止继续遍历索引树，并给用户返回结果。

   除此之外，论文还针对位置属性构建了索引，给用户提供了根据属性查找位置的服务，这是先前的工作所没有的。论文还采用盲签名保护query的隐私，组织query的信息泄露给LBSP。

思考

这篇论文没有着重关注加密算法的研究，而是提出了一套隐私保护系统的设计思路。其中采用Bloom Filter构建索引的方式值得借鉴。当然论文的工作也有一些缺陷，例如，论文并没有考虑索引在线生成和加密的情况，由于位置服务这一场景的特殊性，数据服务商的位置数据并不会经常变动，因此论文并没有考虑这一情况，索引都是离线生成和加密的。而在很多其他的大数据业务场景中，需要实时地上传大量数据，在这种情况下，如何设计加密数据的索引还有待研究。此外，论文中没有对系统的性能提出很多分析，存在一定的优化空间。