论文分享|通过更快的安全比较算法和离线阶段实现高效隐私集合求交协议

密码学 1年前 (2023) admin
369 0 0

论文分享|通过更快的安全比较算法和离线阶段实现高效隐私集合求交协议今天分享的是发表在 NDSS’23 的名为 “Faster Secure Comparisons with Offline Phase for Efficient Private Set Intersection” 的文章,文章第一作者 Florian Kerschbaum 是来自滑铁卢大学的计算机系教授。

Introduction

隐私集合求交集的协议 (private set intersection,PSI)被大家越来越广泛地研究和应用,然而 state-of-the-art 的 PSI 协议通常只能实现比较优的渐近复杂度,性能改进很少并且只能提高常数级复杂度。这篇文章提出了一个新的 PSI 协议,其底层是一个新的并且高效的可供双方对各自输入进行秘密比较的协议。本文提出的 PSI 协议分为线上和线下两个阶段,通过将非常昂贵的密码学操作放在线下阶段进行,其线上阶段对每一个元素仅需要4个快速的域操作,从而使得其线上阶段的运行非常高效。并且文章进行了大量的试验比较来验证其高效的性能。

Preliminary

在讲解其协议构造思想之前,我们首先给出几个所需的基本组件的定义。

Oblivious Linear Evaluation (OLE) OLE 是一个两方协议,假设有 A, B 双方,B 的输入为域内的两个元素 a, b, 同时 A 的输入为另一个域元素 u, 协议结束后,A 会得到 f(u) = au + b。

product sharing product sharing 可以看作为 OLE 的另一个对称版本。在这个协议中, A, B 双方分别知道 u 和 v,协议结束后他们双方会得到关于 u 和 v 乘积的加法分享 a 和 b。即协议结束后 A、B 双方分别会得到 a, b, 其满足 u * v = a + b 。

OLE 元组 在这篇文章中,作者需要的是 OLE 元组 (tuples),其中所有的元素都在一个模质数的域内。ra, sa, sb 是三个域内任意的元素,rb 是域一个任意非0的元素,其满足关系式:ra * rb = sa + sb。

如果 sa + sb = 0,那么将会有 sa = 0, 因为 sb 是一个非0的数。如果我们设定 ra = u, rb = a, sb = -b, sa = f(u),那么我们将得到在上面介绍 OLE 时重排列的式子。

这样一组 (ra, rb, sa, sb) 被称为 OLE 元组。与 OLE 中类似, ra 和 sa(即 u 和 f(u))被 A 知道,rb 和 sb(即 a 和 b)被 B 知道。

布谷鸟哈希(cuckoo hashing) 布谷鸟哈希中包含 k 个哈希算法, h1, h2, …, hk,同时包含 a 个盒子 (bins),每个盒子最多只能容纳一个元素。将一个元素 x 插入布谷鸟哈希表中时,首先查看 h1(x) 位置上是否有其他元素,如果没有,则直接将 x 放入 h1(x) 位置;如果有(假设为 y),则将 y 插入到 h2(y)(或其他) 位置中,然后将 x 放入 h1(x)。这样将有一定的概率进入无限的循环,如果上面代替的操作超过某个阈值,则直接将未插入的元素放入 stash 区域中。

Overview of Private Comparison Protocol

下面,我们使用介绍的 OLE 元组来构造一个双方可以秘密比较其输入是否相等的协议。协议双方为 A、B, 其输入分别为 x 和 y。假设已经提供好了一组 OLE 元组 (ra, rb, sa, sb),其中 ra、sa 为 A 拥有,rb、sb 为 B 所拥有。所需的还有一个抗碰撞的哈希 h。

协议如下:

  1. 1. A 首先计算 c = sa – h(x),并将 c 发送给 B

  2. 2. B 计算 d = [c + h(y) + sb] / rb, 并将 d 发送给 A

  3. 3. A 验证 d 是否等于 ra, 如果是,则说明 x 和 y 相等;否则说明不相等。

Overview of Full Protocol

整个协议分为线上和线下两个部分。线下部分为 A、B 双方 提前生成 OLE 元组,以便为线上阶段使用。

而线上阶段则运用上述的秘密比较协议,构造双方 PSI 协议。我们用 {xi} {yj} 来分别表示 A, B 双方的集合。为了避免将双方的每两个元素进行比较,协议首先使用布谷鸟哈希 (cuckoo hashing) 技术将双方输入进行映射,这样只需要将一方的输入的每一个元素与另一方输入的常数个输入进行比较即可。其线上协议大致如下:

  1. 1. A: 将自己的输入 {xi} 通过布谷鸟哈希映射到一个布谷鸟哈希表(假设有 k 个哈希)中。

  2. 2. B: 由于 B 不知道 A 会把每一个元素映射到什么位置,因此,B 将自己的每个元素都使用 k 个哈希并映射到 k 个位置。

  3. 3. A 和 B: 双方对每个位置 (bin) 内的元素运行上述的秘密比较的协议,从而得出结果。

可以看出,有了 OLE 元组后,大大提高了线上阶段双方的效率,从而可以构造非常高校的算法。针对如何在线下阶段生成 OLE 元组,文中给出了三种可能的方式:1). 使用一个可信第三方生成 2). 使用可信计算环境 (TEE) 3). 使用密码学算法。具体方法如果感兴趣可以在原文中查找。同时,文章还对其完整协议做了优化,使得其通信量和计算量大大减少,这里也不再展开。

Evaluation Results

论文分享|通过更快的安全比较算法和离线阶段实现高效隐私集合求交协议

作者对其协议做了非常详细、大量的实验和比较,以验证其效 率。下面的图检验了在不同带宽的情况下,本文协议与其他 PSI 协议的通信量以及时间的对比。可以看出,本文的新构造在时间和通信量上有着非常好的表现,特别是当要比较的集合内的数量变大时,优势更加明显。


原文始发于微信公众号(COMPASS Lab):论文分享|通过更快的安全比较算法和离线阶段实现高效隐私集合求交协议

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...