论文分享|Shuffle-based Private Set Union: Faster and More Secure

IoT 3周前 admin
94 0 0

论文分享|Shuffle-based Private Set Union: Faster and More Secure

此次分享的是发表于 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)}}。

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

论文分享|Shuffle-based Private Set Union: Faster and More Secure

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 协议所实现的功能。

论文分享|Shuffle-based Private Set Union: Faster and More Secure

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 只需运行一次。其示意图如下。

论文分享|Shuffle-based Private Set Union: Faster and More Secure

Experimental Results

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

论文分享|Shuffle-based Private Set Union: Faster and More Secure

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

版权声明:admin 发表于 2022年11月13日 下午4:36。
转载请注明:论文分享|Shuffle-based Private Set Union: Faster and More Secure | CTF导航

相关文章

暂无评论

暂无评论...