osdi16pung

Unobservable communication over fully untrusted infrastructure

本周组会汇报的论文 《Unobservable communication over fully untrusted infrastructure》 发布在OSDI16上，其主要工作聚焦于通信当中的元数据的隐私保护问题。

所谓元数据就是指的除了通信信息内容以外的通信消息，如通信双方，通信时间，信息长度，发送方接收方收发消息的频率等可以泄露相关隐私的数据。

论文设计并实现了一个用于通信元数据隐私保护的系统——Pung，如图1。

主体思想就是用一个中间的KV存储系统进行消息的转发，发送者将信息发送到该KV存储中，接收者按照相应的label值进行检索（为了隐藏收发双方的关系，发送和检索的label值需不一样）。

论文中信息的检索采用了PIR的方案，但是PIR的每次访问都需要遍历整个数组，用户事先是不知道想要查找的label值在整个集合中的索引的，在集合有序的情况下，每次都需要log(n)次遍历所有集合的检索操作，需要n*log(n)的操作。

为了改善这一点，文中使用了BST（完全二叉搜索树）来存储集合，树的每一层在检索时都看作一个独立的集合，具体结构如下图2所示，从根节点所在的层，逐步向下搜索到最底层，这样我们只需要遍历一遍整棵树就可以获得任意我们想要的元素

上面讲的都是对于单个消息的检索，对于同时需要检索多个消息的情况只能多轮检索，所以作者提出了一种可以同时检索多个消息的方案，将整个集合分为多个桶，每个桶可以看作一个独立的子集，这样每个桶内都可以检索一条消息，k个桶最多可以同时检索条消息。

但是依然存在问题：每个桶里因为只能遍历一次所以只能检索出一条消息，如果碰到想在一个桶内检索多条消息依然需要多轮，所以在论文中作者提出了一种改进方案2.0版本，就是给所有消息备份，同一条消息会在另外一个桶里有一个备份（两个桶里面的同一条消息的label是不同的），如图3所示，这其实是一种空间换时间的方法。用户可以自己只能冲突最少的检索策略，避免多轮检索的情况。

除了上述的，还有很多措施来实现隐藏元数据目标，Pung这个系统是回合制的，一轮一轮的进行，每一轮都分为发送和检索两个阶段，每个客户端都会在发送和检索阶段发送和检索固定数目的消息，这样可以隐藏发送接受频率等信息。

Pung较好的实现了隐藏元数据的目标，但是也存在一些缺点，一个是通信双方必须事先知道彼此，知道双方的公钥。而且BST方案的网络通信代价较高。所以作者做了一些权衡，在小集合上采用了直接发送一个label-index的布隆过滤器给用户。

Pung 使用rust实现，代码发布在GitHub上https://github.com/pung-project/pung