此次分享的是发表于 Usenix’22 的名为 “Shuffle-based Private Set Union: Faster and More Secure” 的文章。文章的第一作者为 Yanxue Jia, 上海交通大学博士生。

Introduction

这篇文章介绍了一种可以计算双方隐私集合并集 private set union (PSU) 的方法。之前介绍的文章大多在构建 PSI 协议， 与其类似的协议则是 PSU。虽然现在学术界对于 PSU 的关注并没有 PSI 那么多，PSU 仍存在很大的应用空间，比如用于计算不同个体的 ip 黑名单集合以进行网络风险评估等。

这篇文章聚焦于构造两方 PSU 协议， 一方称为发送方（输入为集合 X = {x_1, x_2, …, x_m}），另一方称为接收方（输入为集合 y = {y_1, y_2, …, y_n}）。安全要求是，协议结束后，接收方可以收到两集合的并集，但不能知道他们的交集。

Preliminaries

One Fact

我们先来看一个简单的性质：y 可以被分成 s 以及 (y xor s) 两部分，其满足任意两个元素做 xor 运算都能得到另一个元素，比如， s = y xor (y xor s)。

Permute and Share

这是一个包含发送方和接收方双方的协议。在协议中，接收方输入为集合 Y，发送方输入为一个随机的排列（permutation）pi ；协议完成后，发送方将会收到经过随机排列过的一部分（shares）的集合 S1 = {s_1^{pi(1)}, s_1^{pi(2)}, …, s_1^{pi(n)}}, 接收方将收到经过排列过的另一部分的集合 S2 = {s_1^{pi(1)} xor y_{pi(1)}, s_2^{pi(2)} xor y_{pi(2)}, …, s_1^{pi(n)} xor y_{pi(n)}}。

下面这张图比较形象地描述了这一协议的功能。

Oblivious transfer (OT)

这个协议包含发送方和接收方，文章中使用的是 1-out-of-2 OT, 即发送方的输入有两个 x_0, x_1，接收方的输入为一个比特 b。当 b = 0 时，接收方可以得到 x_0，而 b = 1 时，接收方得到 x_1。其安全性为发送方无法知道接收方的选择比特，而接收方只能收到他选择的发送方的一个输入，无法知道另一个输入。

Multi-point oblivious pseudorandom function (OPPRF)

多点 OPPRF 协议包含发送方和接收方双方，发送方没有输入，接收方输入为集合 X = {x_1, x_2, …, x_n}。协议完成后，发送方将得到一个伪随机函数 F 的密钥 k, 而接收方将得到在此密钥下对其所有输入进行的评价（evaluation）：{F(k,x_1), F(k,x_2), …, F(k,x_n)}。

下面这张图描述了多点 OPPRF 协议所实现的功能。

Their Construction

First Attempt

我们首先考虑最简单的情况，发送方只有一个输入(x)， 接收方仍有 n 个输入 （y_1, y_2, …, y_n）。对接收方的每个输入，使用上面简单的办法将其每个都分成两份，y_i = s_1^i xor (y_i xor s_1^i)，我们可以把其第二部分记为 s_2^i (= y_i xor s_1^i)。

接收方再将所有的 y_i 的第一部分发给发送方，这个集合记为 S。发送方在拿到 S 后，将 S 内的每个元素都与自己的输入 x 进行 xor 操作，并把结果发给接收方，xor 后的集合记为 S’。接收方收到后将 S’ 内的元素与自己集合 Y 内的元素进行对比：如果有相同的元素，则说明 x 在集合 Y 内，接收方输出 Y 即是双方的并集；否则， 拿出集合 S’ 内任意一个元素与相应的 s_1^i 进行 xor 运算则能拿到 x：(s_1^i xor x) xor s_1^i = x。

Second Attemp

然而，上述方法存在一个问题：如果 x 属于集合 Y, 由于接收方通过比较可以得知是哪个位置有了重复，因此接收方除知道 x 是属于交集外，还知道交集，违背了 PSU 协议的安全性。

上述问题出现的原因是因为发送方知道 y_i, 和 s_1^i 的对应关系， 为了避免这种信息泄漏，需要打乱这种对应关系。因此，在接收方发送集合 S1 之前，需要将 S1 内的元素与原来集合 Y 内元素的对应关系打乱。这里需要用到的工具是在上面介绍的 permute+share 子协议。在此子协议完成后，发送方继续用收到集合 S1 内的每个元素与 x 进行 xor 操作得到 S1′ 并将其发给接收方。此时，如果 S1′ 与 S2 有交集，说明 x 存在于集合 Y 中，而此时，由于接收方已经不知道此（有交集的）位置对应的 y 是什么，因此无法知道他们之间的交集元素具体是什么，从而避免了上述问题。

如果 S1′ 与 S2 没有交集，则说明 x 不存在与集合 Y 中，而此时由于接收方不知道该使用哪一个 s_1^j 去获取发送方的输入（因为接收方不知道 permute 的顺序），因此不能使用第一种方法。这里，需要再引入一个新的子协议，OT，其中他们的角色不变。当 S1′ 与 S2 没有交集时，接收方输入为 1，可以得到 x；而当 S1′ 与 S2 有交集时，接收方输入为 0，其收到的结果为空。OT 的安全性保证了发送方无法得知接收方的选择。

Third Attempt

然而，上述方法还存在一个问题：由于集合 S1，S2 以及 Y 中的元素与仍然存在着其任意两个做 xor 运算后即能得出另一个元素的关系，而 S2 和 Y 由接收方掌握，S1 中的元素被发送方用来隐藏自己的输入 x, 接收方仍然可以通过 S2 和 Y 中的元素恢复出用来隐藏 x 的值，从而非法得到发送方的输入。

为了避免这种问题，他们又引入了多点 OPPRF 子协议对刚刚集合 S1 和 S2 中的元素进行评价 (evaluation)。在此协议中，发送方和接收方角色不变，接收方输入为集合 S2，协议结束后，发送方将得到一个密钥 k, 而接收方得到在此密钥下对集合 S2 每个元素的评价。发送方用此密钥对其集合 S1 也进行评价，记为 S1’，并将结果发送给接收方。此时，接收方将 S1′ 与 S2 进行对比，后面的操作与上述一样。

Fourth Attempt – Extend

当把发送方的集合由 1 个元素扩展到 m 个元素时，其总的协议继承了上述思想，唯一不同是，需要对发送方集合中的每个元素 x_i 都运行一次多点 OPPRF 以及 OT 协议，而 permute+share 只需运行一次。其示意图如下。

Experimental Results

作者也对提出的协议在运行时间和通信量方面做了实验，并与已知最好的 PSU 协议 [KRTW19] 做了对比。当协议双方集合内有包含大于 2^14 个元素时，其运行时间能快 4-5倍，同时，通信量只需要 [KRTW19] 的一半。更多的实验数据比较可以参考原文。

Conclusion

这篇分享中主要由简单到复杂将此篇文章的设计思路做了大概整理，原文还进一步对其协议进行了优化。比如，由于需要对发送方中集合中的每个元素都做一次多点 OPPRF，同时需要将其与 permute+share 中收到的每个元素做 xor 操作，这个开销是非常大的。原文使用了 cuckoo hashing 的手段将每个元素进行 “定位”， 从而进一步减少其开销。更多细设计节可以参考原文。

References

[KRTW19] Vladimir Kolesnikov, Mike Rosulek, Ni Trieu, and Xiao Wang. Scalable private set union from symmetric-key techniques. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part II, volume 11922 of LNCS, pages 636–666. Springer, Heidelberg, December 2019.

原文始发于微信公众号（COMPASS Lab）：论文分享|Shuffle-based Private Set Union: Faster and More Secure