Efficient Batched Oblivious PRF with Applications to Private Set Intersection

发表于 更新于 分类于

高效的批量不经意伪随机函数与隐私集合求交集的应用

我们描述了一种在半诚实对手存在的情况下对伪随机函数进行不经意评估（OPRF）的轻量级协议。在 OPRF 协议中，接收方有一个输入 ；发送方得到输出 ，接收方得到输出 ，其中 是一个伪随机函数， 是一个随机种子。我们的协议使用了 选 的 OT 扩展协议的新颖改编，当用于生成大批量的 OPRF 实例时，特别有效。实现 个 OPRF 实例的成本大约是实现 个标准 选 OT 实例的成本（使用最先进的 OT 扩展）。

我们详细探讨了我们的协议在半诚实安全隐私集合求交集（PSI）中的应用。最快的最先进的 PSI 协议（Pinkas 等人，Usenix 2015）是基于高效的 OT 扩展。我们观察到，我们的 OPRF 可以用来消除他们的 PSI 协议对各方项目的比特长度的依赖。我们实现了这两个 PSI 协议变体，发现对于 位字符串和足够大的集合的 PSI，我们的比 Pinkas 等人快 3.1 到 3.6 倍。具体来说，我们的协议只需要 3.8 秒就能安全地计算出大小为 集合的交集，而不考虑项目的比特长度。对于非常大的集合，我们的协议只比 PSI 的不安全的朴素散列方法慢 4.3 倍。

1 简介

这项工作涉及 OT、OPRF 和 PSI 的构建。我们首先回顾一下这三个基元。

不经意传输：

不经意传输 (Oblivious Transfer) 一直是安全计算领域的一个核心基本要素。事实上，Yao [30] 和 GMW [7,8] 的原始协议都以关键方式使用了 OT。事实上，OT 是安全计算的必要条件和充分条件 [15]。直到 2000 年初，通用安全计算领域通常被视为主要的可行性工作，改善 OT 性能并不是优先研究方向。这种情况在姚氏混淆电路（GC）首次被实现 [20] 和 Ishai 等人 [12] 设计出一个令人惊讶的快速 OT 协议（我们称之为 IKNP）后发生了改变。

IKNP OT 扩展协议 [12] 确实是一块宝石；它允许以计算和发送少量哈希值为代价执行 选 的 OT（但需要一个公钥原语评估的安全参数来引导系统）。IKNP 立即受到关注，并从那时起在 Yao 和 GMW 协议的实现中普遍使用。几年后，人们才意识到 OT 扩展的用途远远超出了这些基本应用。安全计算的许多方面通过使用 OT 扩展得到了加强和加速。例如，Nielsen 等人 [24] 提出了一种恶意两方安全计算的方法，它将 OT 的输出和输入联系在一个更大的构造中。他们关键性地依赖于批量 OT 的低成本。另一个例子是将信息论的门评估秘密共享（GESS）[16] 应用于计算环境 [17]。[17] 的想法是通过对电路进行浅层评估，并使用 OT 扩展来有效地将它们 "粘合" 在一起，来阻止 GESS 方案的高成本秘密大小。与我们的工作特别相关的是，高效的 OT 被 Pinkas 等人 [28] 认为是隐私集合求交集的有效构件，我们在后面将详细讨论。

IKNP 的 OT 扩展，尽管它被广泛和大量使用，但得到的更新却很少。在半诚实模型中，它仍然是最先进的。稳健性是由 Nielsen [23] 添加的，而在恶意设置中，它最近才得到改进 [2,14]。Kolesnikov 和 Kumaresan [18] 提出了对短秘密大小的改进，这是由 GMW 使用案例所激发的。我们使用他们协议中的想法，并将其称为 KK 协议。在引擎盖下，KK [18] 注意到 IKNP 数据表示的一个核心方面可以被抽象地看作是一个重复纠错代码，他们的改进源于使用一个更好的代码。结果是，在成本几乎相同的情况下，对于高达约 256 的 n，取代了 选 的 OT，变成了 选 的 OT。

不经意伪随机函数：

不经意伪随机函数（OPRF）[6] 是一个协议，其中发送方学习（或选择）一个随机的 PRF 种子 ，而接收方学习 ，即 PRF 对接收方选择的单一输入 的结果。虽然 OPRF 的一般定义允许接收方在多个输入上评估 PRF，但在本文中我们只考虑接收方可以在单个输入上评估 PRF 的情况。

这项工作的核心基元，一个高效的 OPRF 协议，可以被看作是随机值的盲目传输（OT）的变种。我们通过修改 OT 扩展协议 [12,18] 的核心来构建它，其内部结构比之前的 OPRF 工作更接近 OT。因此，我们的介绍是以 OT 为中心的，结果以 OPRF 术语表述。

随机消息的 OT 与 OPRF 共享许多属性。在随机消息的 OT 中，发送方学习随机的 ，而接收方学习 ，选择位 。我们可以认为函数 是一个输入域为 的伪随机函数。同样地，我们可以把随机信息的 选 的 OT 解释为输入域为 。

在这项工作中，我们提出了一个对 IKNP 和 KK 协议的新扩展。在与 选 的 IKNP 和 KK OTs 几乎相同的成本下，我们能够实现任意大的 n 的随机消息的 选 的 OT。也就是说，接收方有一个输入 ，并学习了值 ，而发送方获得了对任何字符串 评估 的能力，其中 是一个伪随机函数。

我们称我们的主要协议为批量的密钥相关的 OPRF（BaRK-OPRF），因为它可以实现大量的 OPRF 实例，其密钥是相关的（以我们后面描述的方式）。这是一个新的基元，但对于我们所考虑的隐私集合求交集的应用来说，这已经足够了。

隐私集合求交集 (PSI):

隐私集合求交集（PSI）指的是两方各自持有项目集，并希望只了解这些集的交集的情况。今天，PSI 是一个真正实用的原始方法，有极快的加密安全实现 [27]。令人难以置信的是，这些实现只比交换散列值的朴素和不安全的方法慢了一个相对较小的系数。在安全计算的问题中，PSI 可能是实践中最强烈推动的一个。事实上，今天像 Facebook 这样的公司已经在例行地分享和挖掘共享信息 [25,31]。在 2012 年，（至少有一部分）这种共享是用不安全的朴素散列法进行的。今天，公司能够并且愿意容忍合理的性能损失，以实现更强的安全性 [31]。我们相信，随着大数据的规模越来越大，隐私成为一个更公认的问题，私人数据共享的普遍性和规模，尤其是 PSI，将继续增长。关于 PSI 的其他讨论和动机，我们请读者参考 [27, 28]。

在我们的工作中，我们通过用 BaRK-OPRF 替换其中的一个组件，大大改进了 [27] 的最先进的 PSI 协议。这一改变使得中等长度的字符串（ 或 位）和合理的大集合的 PSI 的性能提高了 2.3 到 3.6 倍。我们通过实施和详细评估证实了我们的算法结果。我们最大的改进是对于较大的长字符串（ 位）集合（每个 项）的情况，在我们的协议中只需要一分钟，但使用 [27] 需要 214 秒。

1.1 相关工作

不经意传输：我们的 BaRK-OPRF 协议可以被看作是 OPRF 协议，也是 IKNP [12] 范式中的不经意传输的变种。如第 1 节所述，鉴于其在安全计算中的关键重要性，IKNP 的 OT 扩展有一个令人惊讶的简短的后续改进、扩展和概括清单。

与我们最相关的前期工作是 KK 协议 [18]，它从一个新的角度看待 IKNP OT，并提出了一个概括 IKNP 的框架。更具体地说，在 IKNP 协议中，玩家将接收者的选择位 编码为 的 个副本的重复字符串。KK 对此进行了概括，允许使用具有大距离的纠错码（ECC）作为选择位编码。对于一个由 个码字组成的代码，这允许做 选 的 OT，只需消耗 OT 扩展矩阵的一个行。在这项工作中，我们将编码理论的观点发挥到极致。我们观察到，我们从来不需要对码字进行解码，通过使用（伪）随机码，我们能够通过消耗 OT 矩阵的一行来实现相当于多选 的 OT，对于相同的安全保证，这只比原始 IKNP 协议长 3.5 倍左右。

我们的工作严格来说是在半诚实的安全模型中。其他关于 OT 扩展的工作将 IKNP 协议扩展到恶意模型 [2,14] 和 PVC（可公开验证的秘密）模型 [19]。

不经意伪随机函数：不经意伪随机函数是由 Freedman, Ishai, Pinkas, & Reingold [6] 提出。一般来说，先前最有效的 OPRF 协议需要昂贵的公钥操作，因为它们是基于代数 PRF 的。例如，[6] 的 OPRF 是基于 NaorReingold PRF [22] 的，因此需要进行指数运算。此外，它需要的 OT 数量与 PRF 输入的比特长度成正比。[3] 的协议从独特的盲签名方案中构建了一个 OPRF。[13] 的协议不经意地评估 Dodis Yampolskiy PRF [4] 的变体，因此需要指数化（以及其他代数加密组件以促进 OPRF 协议）。

隐私集合求交集：OPRF 有很多应用，但在本文中，我们深入探讨了对隐私集合求交集（PSI）的应用。我们只考虑半诚实的安全模型。我们的 PSI 协议与 Pinkas 等人 [27] 的协议关系最为密切，该协议本身是 [28] 先前协议的优化变体。我们在第 5 节详细描述了这个协议。

我们请读者参考 [28]，以了解 PSI 的许多不同协议范式的概况。正如我们所提到的，基于 OT 的协议在实践中被证明是最快的。然而，我们确实指出，基于 OT 的协议并不具有最低的通信成本。在计算不是一个因素，但通信却很重要的情况下，最好的协议是那些在 [11] 中介绍的 Diffie-Hellman 范式。在这些协议的半诚实版本中，每一方只发送 个组元素，其中 是每个集合中的项目数。然而，这些协议需要与项目数量成比例的指数化，使得它们的性能在实践中很慢。具体来说，[27] 发现基于 Diffie-Hellman 的协议比基于 OT 的协议要慢 200 倍以上。

虽然我们严格遵循 [28] 的范式，但我们用不经意伪随机函数 (OPRF) 的语言抽象出他们协议的一部分。OPRF 和 PSI 之间的联系已经在 [6] 中指出了。然而，使用 OPRF 实现 PSI 的最直接的方法需要一个 OPRF 协议，其中接收者可以在许多输入上评估 PRF，而我们的 OPRF 只允许接收者有一个评估点。OPRF 已经在其他地方被用于 PSI，一般是在恶意对抗模型中 [13, 10, 9]。

OPRF 的其他应用：就像标准 OPRF 一样，我们的 BaRK-OPRF 变体立即有效地暗示了 [6] 的关键字搜索功能（在 [17] 中也被称为 "字符串选择不经意传输（SOT）"）。关键词搜索允许接收者 通过一个字符串来选择收到的秘密。在 SOT 中，发送方 有一个关键词到秘密值的映射。 收到与它选择的关键词字符串相对应的秘密。在 [17] 中， 位选择字符串的 SOT 是通过执行 个 选 的 OT 来建立的，这种技术也基本上是 [28] 的 PSI 协议中使用的。使用 BaRK-OPRF，我们可以通过只消耗 OT 扩展矩阵的单行来实现关键词搜索。

OPRFs 可用于安全模式匹配 [10,5]，其中一方持有一个长文本 ，另一方持有一个短模式字符串 。双方了解到 内所有 的出现的位置。

2 我们成果的技术概述

我们从 Ishai, Kilian, Nissim & Petrank（IKNP）[12] 的 OT 扩展范式开始。OT 扩展的目标是使用少量的 "基础 OT"，加上仅有的对称密钥操作，以实现 的 "有效 OT"。在这里， 的选择取决于计算安全参数 ；在下文中，我们将说明 应该被设置为什么值。下面我们描述一个 OT 扩展，在半诚实的对手存在的情况下，实现随机字符串的 个 选 的 OT。

我们遵循 [18] 的符号，因为它阐述了 OT 扩展的编码理论框架。假设接收方有选择位 。他选择了两个 的矩阵（ 行， 列）， 和 。 让 分别表示 和 的第 行。这两个矩阵是随机选择的，因此： 发送方选择一个随机字符串 。双方进行了 次 的字符串 OT，角色互换，根据发送方选择的字符串 中的位 ，向发送方 传输 或 的列。在第 个 OT 中，接收方给出输入 和 ，它们分别指的是 和 的第 列。发送方使用 作为它的选择位，并收到输出 。注意，这些是长度为 的字符串的 OT，OT 消息的长度很容易扩展。例如，可以通过加密并发送两个 位的长字符串，并在短字符串上使用 OT 来发送正确的解密密钥。

现在让 表示发送方获得的矩阵，其列为 。让 表示第 行。关键的观察是， 让 是一个随机预言机（RO）。我们有，发送方可以计算两个随机字符串 和 ，接收方只能通过 计算其中一个。请注意， 等于 或 ，取决于接收方选择的位 。请注意，接收者没有关于 的信息，所以直觉上他只能学到两个随机字符串 ， 中的一个。因此，矩阵的 行中的每一行都可以用来产生一个 的 OT。

正如 [12] 所指出的，只需假设 是一个相关稳健的哈希函数，这是一个比 RO 更弱的假设。需要一个特殊的假设，因为每个产生的 OT 实例都使用相同的 。相关稳健性的定义见第 3 节。

3 技术预案

我们用 来表示二进制字符串 的汉明权重。我们的计算安全参数是 ，统计安全参数是 。

3.1 相关性的稳健性

3.2 伪随机码

3.3 我们的不经意伪随机函数变体

3.3.1 我们的伪随机函数变体

3.3.2 我们的 BaRK-OPRF 功能

在图 1 中，我们正式描述了我们实现的变体 OPRF 功能。它生成了具有相关密钥的 PRF 的 个实例，并允许接收者在每个密钥的一个输入上学习（松弛的）输出。

图 1

图 1：批量的、密钥相关的 OPRF（BaRK-OPRF）的理想功能。

该功能由一个宽松的伪随机函数 、 个实例和两方（发送方和接收方）组成参数。

在接收方的输入 ：

  • 选择随机成分作为伪随机函数的种子： ，并把这些交给发送方。
  • 将 交给接收方。

4 主要结构

我们提出了我们的主要结构，这是一个针对图 1 中功能的半诚实的安全协议，并以定理 2 中定义的宽松 PRF 为例进行实例化。

4.1 符号

4.2 BaRK-OPRF 的结构

图 2

图 2：BaRK-OPRF 协议

的输入： 个选择字符串 ， 。

参数：

  • 一个 家族 ，输出长度为 。
  • 一个 相关的稳健 。
  • 一个理想的 原语。

协议：

  1. 选择一个随机的 并将其发送给 。

  2. 随机选择 。让 表示 的第 位。

  3. 以下列方式形成 矩阵 和 ：

  • 对于 ，选择 ，并设置 。

让 和 分别表示矩阵 和 的第 列。

  1. 和 以如下方式与 互动：
  • 作为接收方，输入 。
  • 作为发送方，输入 。
  • 收到输出 。
$S$ 形成 $m×k$ 矩阵 $Q$ ，使得 $Q$ 的第 $i$ 列是向量 $q^i$ (注意  $q^i = t^i_{s_i}$ )。让 $q_j$ 表示 $Q$ 的第 $j$ 行。注意， $q_j = ((t_{0,j} ⊕t_{1,j} )\cdot s)⊕t_{0,j}$ 。简化后， $q_j = t_{0,j} ⊕(C(r_j) \cdot s)$ 。

  1. 对于 ， 输出 PRF 种子 。

  2. 对于 ， 输出松弛的 PRF 输出 。

5 改善隐私集合求交集

BaRK-OPRF 的主要应用是提高半诚实安全的隐私集合求交集（PSI）的性能。Pinkas 等人 [28] 对该模型中 PSI 的许多不同范式做了详尽的总结。

为了我们的目的，我们只总结了最有效的 PSI 协议，也就是 [28] 的基于 OT 的范式，包括后续工作 [27] 中建议的优化。以下我们把他们的协议称为 "PSSZ" 协议。

5.1 PSSZ 中隐含的 OPRF

PSSZ 的主要构件，私人平等测试，可以看作是一个基于随机 OT（即随机信息的不经意传输）的松弛 OPRF，它可以从 OT 扩展中有效地得到。该协议如下，Bob 有输入 ，其中 。

  • 双方进行 个 选 的随机 OT，Alice 作为接收者。Bob 作为接收方，使用 的比特作为他的选择比特。在第 个 OT 中，Alice 学习了随机字符串 和 ，而 Bob 学习了 。
  • 定义映射 ，其中 是一个随机预言机。然后，我们可以把 看作是一个 PRF，其密钥是 的值（Alice 知道）。鲍勃只在 上学习 的输出。更确切地说，他学到了松弛的输出 ，对其而言， 的所有其他输出都是伪随机的。

在这个描述中，我们把 当作一串比特，因此使用 选 （随机）OT。然而，当使用 [18] 的 OT 扩展协议时， 选 的随机 OT 的成本与 选 的随机 OT 基本相同。因此，PSSZ 将 解释为 上的字符串。该协议对 的每个字节（不是比特）使用 选 的随机 OT 的一个实例。

不管是使用 选 还是 选 的 OT，这个 OPRF 协议的成本随着输入 的长度而变化，而我们的成本与输入长度无关。我们对 PSSZ 的主要改进包括用我们的 OPRF 替换他们的 OPRF。该协议的其余部分基本没有变化。

5.2 基于 OPRF 的 PSI

我们现在描述 PSSZ 范式如何使用 OPRF 实现 PSI。整个 PSI 协议的这一部分在我们的实现和 [27] 的实现之间几乎是相同的（我们包括一个额外的小优化）。为了具体化，我们描述当双方有大致相同数量的 n 个项目时，在 PSSZ 中使用的参数。

该协议依赖于布谷鸟散列法 [26] 和 个散列函数，我们现在简要地回顾一下。使用布谷鸟散列法将 个项目分配到 个仓中，首先选择随机函数 并初始化空仓 。为了哈希一个项目 ，首先检查 中是否有任何一个仓是空的。如果是，那么就把 放在其中一个空仓中，然后终止。否则，随机选择一个 ，驱逐当前在 中的项目，用 代替它，然后递归地尝试插入被驱逐的项目。如果这个过程在一定的迭代次数后没有终止，那么最后被驱逐的元素将被放置在一个特殊的仓中，称为储藏室。

PSSZ 以如下方式将布谷鸟散列法用于 PSI。首先，双方选择 个适合三路布谷鸟散列的随机散列函数 ， 和 。假设 Alice 有一个输入集 ，Bob 有一个输入集 ，其中 。Bob 用布谷鸟散列法和一个大小为 的储藏室将他的项目映射到 个仓中。在这一点上，Bob 每个仓中最多有一个项目，他的储藏室中最多有 个项目，然后他用假项目填充空仓，以便每个仓正好包含 个项目，储藏室刚好包含 个项目。

然后双方运行 个 OPRF 实例，其中 Bob 扮演接收者的角色，并使用他的 个项目作为 OPRF 输入。让 表示在第 个 OPRF 实例中评估的 PRF。如果 Bob 通过布谷鸟散列将项目 映射到第 仓，那么 Bob 学习 ；如果 Bob 将 映射到储藏室的 位置，那么 Bob 学习 。

另一方面，Alice 可以对任何 计算 。所以她计算候选 PRF 输出的集合： 她随机地将 的元素和 的元素进行置换，并将其发送给 Bob。Bob 可以按以下方式识别 和 的交集。如果 Bob 有一个映射到储藏室的项目 ，他检查相关的 OPRF 输出是否存在于 中；如果 Bob 有一个没有映射到储藏室的项目 ，他检查其相关的 OPRF 输出是否在 中。

直观地说，根据 PRF 特性，该协议对半诚实的 Bob 是安全的。对于一个项目 ，相应的 PRF 输出 是伪随机的。很容易看出，即使 Bob 学习了松弛的 PRF 输出，并且 PRF 实现了 RK-PRF 安全，定义 3（即 Alice 的 PRF 输出对于学习了松弛的 PRF 输出的对手来说是伪随机的），安全性也是成立的。同样，如果 PRF 输出即使在相关密钥下也是伪随机的，那么对于 OPRF 协议来说，用相关密钥实例化 PRF 实例是安全的。

只要 PRF 不引入任何进一步的碰撞（即 对于 ），该协议就是正确的。下面我们讨论防止这种碰撞所需的参数。

一个优化的过程：在上面的协议总结中，Bob 必须在集合 或集合 中搜索他的每一个 OPRF 输出。此外， ， 。即使在使用合理的数据结构进行这些比较时，它们也会对协议的运行时间产生非同小可的影响。现在我们介绍一种优化方法，它可以减少这种成本（在我们的实现中大约减少 10%）。完整的协议在图 3 中描述。

我们的修改工作如下。首先，Bob 为每一个没有被映射到储藏室的 的项目追踪一个哈希索引 。例如，如果 Bob 的布谷鸟散列将 映射到仓 ，那么 Bob 将 与 联系起来。如果 被两个散列函数 映射到仓，那么 Bob 可以任意选择 或 。

然后在前 个 OPRF 实例中，Bob 使用输入 。综上所述，如果 Bob 将项目映射到储藏室的第 个位置，那么 Bob 学会了 。如果他没有将 映射到储藏室中，那么他就会学到 ，正好是一个 。

然后，Alice 计算出以下几组： 她随机地将每个 和每个 的内容置换，并将其发送给 Bob。对于 Bob 的每个项目 ，如果 没有被映射到储藏室，那么 Bob 可以检查 是否属于 ，对于相关的哈希指数 ，如果他的布谷鸟散列将项目 映射到储藏室的位置 ，他可以检查 是否属于 。

将哈希指数 附加到 PRF 输入的原因如下。假设 ，这确实可以以明显的概率发生，因为 、 的输出范围很小（ ）。如果不附加 ， 和 都会包含相同的值 。这将泄露一个事实，即发生了碰撞 。这样的事件是取决于输入的，所以无法模拟。

通过我们的优化：（1）Alice 对 PRF 的所有调用（计算 和 ）都在不同的键输入对上调用 PRF。这确保了这些集合的内容可以很容易地被模拟；（2）Bob 只在 个项目的一个集合（ 或 ）中搜索他的每个 PRF 输出。这与之前描述的方法形成了对比，Bob 必须在一个大小为 或 的集合中找到每个 OPRF 输出（取决于该项目是否在储藏室中）。

回顾一下，只要 PRF 输出之间没有虚假碰撞，该协议就是正确的。由于发生虚假碰撞的机会最多只有 次（Bob 每次都在 个项目的集合中搜索一个 PRF 输出），我们可以通过使用长度为 的 PRF 输出，将虚假碰撞的总体概率限制在 。

图 3：我们对 PSSZ PSI 协议的优化，以 OPRF 功能的方式编写

图 3：我们对 PSSZ PSI 协议的优化，以 OPRF 功能的方式编写

参数：Alice 有输入集 ，Bob 有输入集 ，集合的大小 。 是布谷鸟哈希的储藏室大小。

协议：

  1. Bob 指定随机哈希函数 ，并告诉 Alice。

  2. Bob 用布谷鸟哈希将他的输入集 散列到 个仓中。让 Bob 为每个 记录 ，以便如果 ，则 放在储藏室，否则 在 仓中。将储藏室中的物品按任意顺序排列。

    Bob 选择 OPRF 输入如下：对于 ，如果 号仓是空的，那么设置 为一个假值；否则如果 在 号仓中，那么设置 。对于 ，如果储藏室中的位置 是 ，那么设置 ；否则设置 为假值。

  3. 双方调用 个 OPRF 实例，Bob 为接收方，输入为 。Alice 收到 ，Bob 收到所有 的 。

  4. Alice 计算： 并向 Bob 发送每个集合的排列组合。

  5. Bob 初始化一个空集 ，并对 做如下处理：如果 ，并且 在储藏室的位置 ，并且 ，则 Bob 将 加入 。如果 且 ，则 Bob 将 加入 。

  6. Bob 向爱丽丝发送 ，双方都得到 。

5.3 比较 OPRF 子协议

6 实现与性能

我们实现了我们的 PSI 协议，并报告了它与最先进的 PSI 协议 [27] 的性能比较。我们的完整实现可以在 GitHub 上找到。

在我们的实现中，我们使用了与 PSSZ 一致或更严格的参数设置，并在我们的系统上运行他们和我们的代码，以便获得有意义的比较。与 PSSZ 一样，我们使用了来自 [1] 的矩阵转置代码和其他一些优化。

6.1 选择合适的参数

6.2 环境设置

6.3 实施细节

鸣谢

我们感谢 Peter Rindal 为我们的协议实现提供了库和有益的建议。我们也感谢 Michael Zohner 回答了我们关于实现 [27] 的许多问题。最后，我们感谢 CCS 的匿名审稿人提供的有益反馈。

第一作者由海军研究办公室（ONR）的合同号 N00014-14-C-0113 支持。第二位作者得到美国国家科学基金会资助 CNS-1350619 和 CNS-1414119 的支持，部分得到国防高级研究计划局（DARPA）和美国陆军研究办公室的合同 W911NF-15-C-0226 的支持，以及麻省理工学院转化奖学金。第三和第四位作者得到了美国国家科学基金会 1149647 号奖和谷歌研究奖的支持。这项工作是在前三位作者访问西蒙斯计算理论研究所时开始的，该研究所由西蒙斯基金会和 DIMACS / 西蒙斯密码学合作组织通过 NSF 资助 #CNS-1523467 支持。

参考文献

  1. Asharov, G., Lindell, Y., Schneider, T., and Zohner, M. More efficient oblivious transfer and extensions for faster secure computation. In Sadeghi et al. [29], pp. 535–548.
  2. Asharov, G., Lindell, Y., Schneider, T., and Zohner, M. More efficient oblivious transfer extensions with security for malicious adversaries. In EUROCRYPT 2015, Part I (Sofia, Bulgaria, Apr. 26–30, 2015), E. Oswald and M. Fischlin, Eds., vol. 9056 of LNCS, Springer, Heidelberg, Germany, pp. 673–701.
  3. Camenisch, J., Neven, G., and shelat, a. Simulatable adaptive oblivious transfer. In EUROCRYPT 2007 (Barcelona, Spain, May 20–24, 2007), M. Naor, Ed., vol. 4515 of LNCS, Springer, Heidelberg, Germany, pp. 573–590.
  4. Dodis, Y., and Yampolskiy, A. A verifiable random function with short proofs and keys. In PKC 2005 (Les Diablerets, Switzerland, Jan. 23–26, 2005), S. Vaudenay, Ed., vol. 3386 of LNCS, Springer, Heidelberg, Germany, pp. 416–431.
  5. Faust, S., Hazay, C., and Venturi, D. Outsourced pattern matching. In ICALP 2013, Part II (Riga, Latvia, July 8–12, 2013), F. V. Fomin, R. Freivalds, M. Z. Kwiatkowska, and D. Peleg, Eds., vol. 7966 of LNCS, Springer, Heidelberg, Germany, pp. 545–556.
  6. Freedman, M. J., Ishai, Y., Pinkas, B., and Reingold, O. Keyword search and oblivious pseudorandom functions. In TCC 2005 (Cambridge, MA, USA, Feb. 10–12, 2005), J. Kilian, Ed., vol. 3378 of LNCS, Springer, Heidelberg, Germany, pp. 303–324.
  7. Goldreich, O. Foundations of Cryptography, Volume 2: Basic Applications. Cambridge University Press, The address, 2004.
  8. Goldreich, O., Micali, S., and Wigderson, A. How to play any mental game or A completeness theorem for protocols with honest majority. In 19th ACM STOC (New York City” New York, USA, May 25–27, 1987), A. Aho, Ed., ACM Press, pp. 218–229.
  9. Hazay, C. Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs. In TCC 2015, Part II (Warsaw, Poland, Mar. 23–25, 2015), Y. Dodis and J. B. Nielsen, Eds., vol. 9015 of LNCS, Springer, Heidelberg, Germany, pp. 90–120.
  10. Hazay, C., and Lindell, Y. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. Journal of Cryptology 23, 3 (July 2010), 422–456.
  11. Huberman, B. A., Franklin, M. K., and Hogg, T. Enhancing privacy and trust in electronic communities. In EC (1999), pp. 78–86.
  12. Ishai, Y., Kilian, J., Nissim, K., and Petrank, E. Extending oblivious transfers efficiently. In CRYPTO 2003 (Santa Barbara, CA, USA, Aug. 17–21, 2003), D. Boneh, Ed., vol. 2729 of LNCS, Springer, Heidelberg, Germany, pp. 145–161.
  13. Jarecki, S., and Liu, X. Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In TCC 2009 (Mar. 15–17, 2009), O. Reingold, Ed., vol. 5444 of LNCS, Springer, Heidelberg, Germany, pp. 577–594.
  14. Keller, M., Orsini, E., and Scholl, P. Actively secure OT extension with optimal overhead. In CRYPTO 2015, Part I (Santa Barbara, CA, USA, Aug. 16–20, 2015), R. Gennaro and M. J. B. Robshaw, Eds., vol. 9215 of LNCS, Springer, Heidelberg, Germany, pp. 724–741.
  15. Kilian, J. Founding cryptography on oblivious transfer. In 20th ACM STOC (Chicago, Illinois, USA, May 2–4, 1988), ACM Press, pp. 20–31.
  16. Kolesnikov, V. Gate evaluation secret sharing and secure one-round two-party computation. In ASIACRYPT 2005 (Chennai, India, Dec. 4–8, 2005), B. K. Roy, Ed., vol. 3788 of LNCS, Springer, Heidelberg, Germany, pp. 136–155.
  17. Kolesnikov, V., and Kumaresan, R. Improved secure two-party computation via information-theoretic garbled circuits. In SCN 12 (Amalfi, Italy, Sept. 5–7, 2012), I. Visconti and R. D. Prisco, Eds., vol. 7485 of LNCS, Springer, Heidelberg, Germany, pp. 205–221.
  18. Kolesnikov, V., and Kumaresan, R. Improved OT extension for transferring short secrets. In CRYPTO 2013, Part II (Santa Barbara, CA, USA, Aug. 18–22, 2013), R. Canetti and J. A. Garay, Eds., vol. 8043 of LNCS, Springer, Heidelberg, Germany, pp. 54–70.
  19. Kolesnikov, V., and Malozemoff, A. J. Public verifiability in the covert model (almost) for free. In ASIACRYPT 2015, Part II (Auckland, New Zealand, Nov. 30 – Dec. 3, 2015), T. Iwata and J. H. Cheon, Eds., vol. 9453 of LNCS, Springer, Heidelberg, Germany, pp. 210–235.
  20. Malkhi, D., Nisan, N., Pinkas, B., and Sella, Y. Fairplay—a secure two-party computation system. In Proceedings of the 13th Conference on USENIX Security Symposium - Volume 13 (Berkeley, CA, USA, 2004), SSYM’04, USENIX Association, pp. 20–20.
  21. Naor, M., and Pinkas, B. Efficient oblivious transfer protocols. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA, 2001), SODA ’01, Society for Industrial and Applied Mathematics, pp. 448–457.
  22. Naor, M., and Reingold, O. Number-theoretic constructions of efficient pseudo-random functions. Journal of the ACM 51, 2 (2004), 231–262.
  23. Nielsen, J. B. Extending oblivious transfers efficiently how to get robustness almost for free. Cryptology ePrint Archive, Report 2007/215, 2007. ia.cr/2007/215.
  24. Nielsen, J. B., Nordholt, P. S., Orlandi, C., and Burra, S. S. A new approach to practical active-secure two-party computation. In CRYPTO 2012 (Santa Barbara, CA, USA, Aug. 19–23, 2012), R. Safavi-Naini and R. Canetti, Eds., vol. 7417 of LNCS, Springer, Heidelberg, Germany, pp. 681–700.
  25. Opsahl, K. The disconcerting details: How Facebook teams up with data brokers to show you targeted ads. https://www.eff.org/deeplinks/2013/04/disconcertingdetails-how-facebook-teams-data-brokers-show-youtargeted-ads, 2013. [Online; accessed 23-May-2016].
  26. Pagh, R., and Rodler, F. F. Cuckoo hashing. J. Algorithms 51, 2 (2004), 122–144.
  27. Pinkas, B., Schneider, T., Segev, G., and Zohner, M. Phasing: Private set intersection using permutation-based hashing. In 24th USENIX Security Symposium, USENIX Security 15 (2015), J. Jung and T. Holz, Eds., USENIX Association, pp. 515–530.
  28. Pinkas, B., Schneider, T., and Zohner, M. Faster private set intersection based on OT extension. In 23rd USENIX Security Symposium, USENIX Security 14 (2014), K. Fu and J. Jung, Eds., USENIX Association, pp. 797–812.
  29. Sadeghi, A.-R., Gligor, V. D., and Yung, M., Eds. ACM CCS 13 (Berlin, Germany, Nov. 4–8, 2013), ACM Press.
  30. Yao, A. C.-C. How to generate and exchange secrets (extended abstract). In 27th FOCS (Toronto, Ontario, Canada, Oct. 27–29, 1986), IEEE Computer Society Press, pp. 162–167.
  31. Yung, M. From mental poker to core business: Why and how to deploy secure computation protocols? https://www.sigsac.org/ccs/CCS2015/pro keynote.html, 2015. ACM CCS 2015 Keynote Talk.