论文笔记

《Riffle: An Efficient Communication System With Strong Anonymity》是 2016 年隐私增强国际研讨会(PETS)的会议论文

该论文主要提出并实现了一个叫做 Riffle 的匿名网络，可以在权衡带宽和运算量的前提下，实现强匿名（即使大部分节点都是恶意节点，只要还有一个可信的服务端，即可确保匿名）

作者: Albert Kwon 主页
实现开源于 Github
论文PDF

补充知识

私有信息检索

私有信息检索(Private Information Retrieval, PIR) ¹是一种检索协议：用户从服务端数据库查询信息的同时，确保不会泄露自己所查询的信息本身

最简单的方案是：服务端返回数据库的所有信息，再由客户端本地检索（完美符合要求，但是很不现实）

要实现理论安全，需要假设有多个不合作服务器，每个服务器都有数据库的副本。（如果没有此假设，则理论上只有返回整个数据库才能确保安全）

对于 $N$ 个数据库，其中有 $T(T \lt N)$ 个数据库存在共谋关系，共存有 $K$ 条消息，用户理论上最少的下载量为^{2 3}
$L=1+\frac{T}{N}+\frac{T}{N^2}+\cdots+\frac{T}{N^K}=1+\sum^{K}_{i=1}{\frac{T}{N^i}}$

要解决的问题

目前的匿名通信，拥有以下特点：

• Tor
  • 低时延
  • 高带宽
  • 可扩展的匿名性
  • 容易受到流量分析攻击
• 基于 DC-Nets 的方案
  • 抗流量分析
  • 带宽消耗大
• 基于 Mix-Nets 的方案
  • 高度匿名性
  • 计算消耗大

可以看出他们都拥有一些缺点存在，而常用的 Tor 也是牺牲了部分匿名性，来适应更多的环境，仍然无法做到理论上的强匿名性（只是受限于攻击者的能力，无法实现针对所有流量的分析）

要解决上述的问题，提出了 Riffle 这个权衡带宽和计算量的强匿名系统

符号定义

论文中设计的符号含义

系统架构

Riffle 不同于 Tor 这种基于中继的匿名通信，即使大部分节点都是恶意节点，并且有足够能力监管网络的攻击者存在，都可以保证匿名性（强匿名）

该匿名系统主要基于 Dissent 的思路。

首先需要划分出群组(Group)，其类似于互联网中的局域网(Local Area Network, LAN)，但是这里的群组只是逻辑上的邻居，在实际的地理位置上可能相聚很远。每一个群组可能有多个服务端和多个客户端（通信的主体）存在，且群组内只要至少有一个可信服务端，就可以保证强匿名性

系统主要分为两个阶段

• Setup: 只运行一次，用于共享密钥
• Communication: 分为多个 round，每个 round 每个客户端都要上传和下载数据，且其又分为多个阶段
  • Upload: 客户端分层加密信息发送给服务端
  • Shuffle: 服务端按顺序解密顺序，并对内容洗牌
  • Download: 将解密后的明文广播给所有客户端

数据初始化

每一个服务端 $S_i$ 都要产生一个公私钥对 $(K_{Pu_i},K_{Pr_i})$
并且，所有的公钥都要广播给群组内的别的服务端与客户端

每一个客户端可以根据时延、带宽等因素，选择一个首选服务端(primary server)，用于后续过程中的通信（客户端只需要和自己的首选服务端通信）

为了实现私人消息检索，每个客户端需要和除去首选服务端外的服务端协商一个伪随机数种子 $seed$ 和一个密钥 $secret$

循环轮(round)

每一个客户端在每一个循环(round)中，都必须发送和接收数据，以保证匿名性，如果他并不需要发送或接受，则发送和接收随机的内容

发送信息（上传）与洗牌

普通洗牌协议

首先先思考下普通的洗牌（shuffle）协议：

1. 客户端下载所有服务端的公钥
2. 客户端上传任意分层加密后的信息到服务端
3. 服务端对内容进行洗牌洗牌后解密，并广播明文
4. 客户端选择自己需要的明文下载

假设有两个客户端 $C_1$、$C_2$ 和两个服务端 $S_1$、$S_2$：
客户端要发布的消息分别是 $m_1$ 和 $m_2$，服务端的公私钥分别是 $K_{Pr_1}$、$K_{Pu_1}$、$K_{Pr_2}$、$K_{Pu_2}$
那么，$C_1$、$C_2$ 将会发送给服务端 $E(E(m_1,K_{Pu_2}),K_{Pu_1})$、$E(E(m_2,K_{Pu_2}),K_{Pu_1})$
首先由 $S_1$ 进行操作，他先要将内容解密得到 $E(m_1,K_{Pu_2})$ 和 $E(m_2,K_{Pu_2})$。接着使用置换序列 $\pi_1$ 对消息的顺序进行置换。
$S_2$ 进行同样的操作，并且得到实际的明文 $m_1$ 和 $m_2$，但是由于 $S_1$ 不知道 $\pi_2$ 并且 $S_2$ 不知道 $m_1$，因此服务器都无法得知明文和发送者的关系

因此在确保至少有一个可信服务器的前提下，即使剩余的所有恶意服务器串通，仍然无法对发送者去匿名化

但是这个方案仍然存在被攻击的可能性：
假设有一个串通好的服务端 $S_1$ 和客户端 $C_1$，该服务端其在接收到消息后，想要知道 $C_2$ 的内容是什么，其可以将 $C_2$ 的内容复制一遍，替换 $C_1$ 的内容。
在最终全部解密后，可以找出重复的明文，并从此可以得知 $C_2$ 的内容（由于 $C_1$ 是恶意客户端，其消息丢失并不会导致系统产生警惕）

该攻击手段是利用洗牌协议的洗牌过程无法被验证是否存在对信息进行更改
要对信息进行验证，本身是很耗时的：针对 100000 个 ElGamal 进行验证要花费超过 2min，在通信系统中，这个代价是无法忍受的
因此需要单独设计一个特有的验证手段

混合洗牌算法

1. 共享密钥：证明者 $P$ 和验证者 $V$ 生成公私钥对 $(K_{Pu_P},K_{Pr_P})$、$(K_{Pu_V},K_{Pr_P})$，同时客户端 $C_j$ 生成密钥 ${k'_j}$ 提供给 $P$， ${k_j}$ 提供给 $V$
2. 密钥洗牌：客户端将密文组 ${\{E(E(k_j,K_{Pu_V}),K_{Pu_P})\}}_{j \in [n]}$ 发送给 $P$ 和 $V$。证明者按照确定的置换序列 $\pi$ 对密钥进行置换，并将 $\pi(\{E(k_j,K_{Pu_V})\})$ 发送给 $V$，$V$ 再次解密得到 $\pi(k_j)$
3. 信息发送：在 $r=1, \dots, R$ 中执行洗牌算法
   1. 洗牌：要发送消息 ${\{M_j^r\}}_{j\in[n]}$，客户端需要发送 ${\{AE(AE(r(M_j^r),k_j),k'_j)\}}_{j\in[n]}$。$P$ 按照同样的 $\pi$，将 ${\{AE(r(M_j^r,k_j))\}}_{j\in[n]}$ 发送给 $V$ 验证。在这里 $AE$ 是经过身份验证的加密
   2. 验证：$V$ 使用 ${\{k_{\pi(j)}\}}_{j\in[n]}$ 和 $r$ 来解密，并且得到 ${\{M_{\pi(j)}^r\}}_{j\in[n]}$

按照上述的算法，可以确保以下两条原则：

• 验证者不知道消息的顺序（验证者只知道密钥与消息之间的对应关系）
• 验证者需要能验证消息是否修改或丢失（消息使用客户端与验证服务端协商的密钥加密，证明服务端无法伪造）

接收信息（下载）

普通私有信息检索

1. 客户端上传加密信息至服务端
2. 服务端广播明文给所有客户端
3. 每个客户端从对应的索引下载数据

该方案实现了接收者匿名性但无法实现发送者匿名性，且该方案在细节上还有很多地方值得讨论

Riffle 中的私有信息检索

在实际使用中，客户端并不需要获取其不需要的数据，特别是由于 $\pi$ 固定，如果客户端只与特定客户端通信，其完全可以只请求特定索引的数据

假设 $C_j$ 想要获取 $I_j$ 对应的数据，其需要首先按照准备阶段协商的随机数种子生成 $m-1$ 个长度为 $n$ 的随机二进制掩码(mask)，并且计算出特定的二进制掩码发送给首选服务器，使得其与 $m-1$ 个数据异或后只有 $I_j$ 位置为 $1$
每一个掩码将对应一个服务端（服务端也会通过协商好的随机数种子获得相同的掩码）。服务端将掩码中值为 $1$ 对应的的数据异或后与协商好的密钥 $secret$ 异或，发送给首选服务端

服务端将收集结果异或后发送给客户端，客户端将收到的内容与之前所有的密钥异或，得到其需要的数据

也即，该方案，实现了客户端只需要下载自己需要长度的数据，同时避免了被别人知晓自己实际想要的数据（除非所有服务器联手）

简单的例子

假设共有 $6$ 个客户端，本轮对应的数据分别是：

• $00110010$
• $01010110$
• $10010111$
• $11011000$
• $10011001$
• $01010101$

客户端需要第 $2$ 条消息($01010110$)

如果有 $3$ 个服务器，提前协商的密钥为：

• $secret_1=11001101$
• $secret_2=10100101$
• $secret_3=01100011$

那么客户端要生成三个长度为 $6$ 的掩码，前两个随机产生：

• $mask_1=101101$
• $mask_2=011000$

为了确保最终异或结果只有第二位为 $1$，则要求第三个掩码为 $110111$ ($101101\oplus011000\oplus110111=000010$)

则三个服务器要返回的信息分别为：

首选服务器将结果异或，得到 $11100111\oplus11100100\oplus01011100=01011111$

客户端从首选服务器获得的信息($01011111$)与三个密钥异或：
$01011111 \oplus 11001101 \oplus 10100101 \oplus 01100011 = 01010110$

问责机制

针对客户端的问责

客户端可以发送错误的初始化信息或发送错误加密的密文给服务端，但该过程只会影响与其自己相关的数据（洗牌阶段并不会将错误的信息扩散到别的信息中）

而在下载阶段，服务端按照要求将信息发送给客户端，也即客户端可能可以获得所有的信息，但是其可能并不能正确识别内容。客户端获得的明文可能本身是加密后的

针对服务端的问责

当一个服务端在混合洗牌的验证过程中，发现问题，其可以提出指控（可能是之前的服务器存在恶意，也可能是客户端存在恶意）

但是恶意的服务器也可能会恶意发出指控，因此需要有一个允许大家对恶意节点的验证操作：

• 验证密钥确实是被指控的客户端和服务端协商的密钥
• 验证密文就是服务端发出的

验证算法如下：

1. 提出指控的服务器 $S_i$ 公布自己要指控的信息位置 $j$、信息密文 $AE(r(M^r_j),k_j)$、协商密钥 $k_j$
2. 从提出指控的服务器开始，每一个服务器都由上一个服务器来验证自己收到的密文确实是他发出的内容以及自己的使用密钥解密出的结果无误
3. 每一个服务器公布对应的消息在自己的洗牌过程中的位置变化 $j'=\pi^{-1}(j)$ 以及自己收到的信息密文、协商密钥
   4，大家对每一个服务器的过程进行验证
4. 所有的过程都需要公布给所有客户端，并由客户端再次验证
   • 验证通过：被指控的客户端被踢出群组
   • 验证失败：找到导致错误的服务器，将其提出群组

简单而言，就是出错后，大家就都将自己的操作过程公布，并由其他节点验证

密钥承诺

//TODO: 【该部分需要进一步补充】

但在这里存在一个问题：如何判断服务器公布的协商密钥未被修改
要解决这个问题，需要使用零知识证明以及 ElGamal 加密

证明者 $P$ 拥有自己掌握的密钥 $s$、自己声明的协商密钥 $k'$。要证明 $k=k'$，其要首先证明：

• $g^{rs'}=\frac{k}{k'}\cdot g^{rs}$（可以使用⁴证明）
• $log_{g^r}(\frac{k}{k'}\cdot g^{rs'})=log_g(g^s)$（可以使用⁵证明）

验证者 $V$ 拥有证明者声明的协商密钥 $k'$、密文 $c=(g^r,k\cdot g^{rs})$、公钥 $g^s$ 并计算 $\frac{k}{k'}\cdot g^{rs}$

综合上述内容，来说明服务器生成自己协商的密钥，就是在初始阶段其和客户端协商的密钥

带宽消耗

• 上行带宽：$b + m\lambda + n$
• 下行带宽：$b \cdot n\cdot r$

证明系统安全性

1. 当正确运行协议时，每一个可信客户端的消息都可以送达所有的可信客户端，则说明协议是正确的
2. 攻击者每一轮猜测一条消息的发送者是 $k$ 个可信客户端中的某一个的概率是 $\frac{1}{k}$，则证明发送存在匿名性
3. 攻击者每一轮猜测一条消息的接收者是 $n$ 个可信客户端中的某一个的概率是 $\frac{1}{n}$，则说明接收存在匿名性

论文未解决的问题

• 跨群组通信：对于不同的群组间，也需要进行信息的交互，可以使用 Herbivore 来实现组间通信
• 访问互联网：将某些服务端作为出口节点，用于访问互联网
• 大量恶意服务端：大量恶意服务端共同联手伪造证据，来控告可信的服务端
• 服务端间带宽：Riffle 主要节省了客户端的带宽和计算，但是每个服务端的带宽和工作量消耗很大
• 动态加入离开：客户端可能会动态加入和离开网络，每次群组变化都需要重新进行 setup 阶段，而这是很耗时的
• 审查攻击：如果客户端无法保证持续在线，可能会被审查攻击

参考资料