Efficient Batched Oblivious PRF with Applications to Private Set Intersection

本文主要是介绍Efficient Batched Oblivious PRF with Applications to Private Set Intersection，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

《Efficient Batched Oblivious PRF with Applications to Private Set Intersection》(KKRT16)这篇论文是从运行效率上针对IKNP03-OTE的一个改变，通过将纠错码改为伪随机编码实现1-out-of-∞ OTE，避免了OT数量与元素的大小相关。

与本篇论文相关的还有另外两篇《SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension》(PRTY19) 和《Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF》(CM20)，其中，PRTY19是从通信负载上针对KKRT16-OTE的一个改变，通过将巨大的矩阵传输改为n阶多项式传输实现k-out-of-n OTE，降低了KKRT16的通信复杂度。CM20是从通信负载和运行效率均衡针对KKRT16-OTE的一个改变。通过将纠错码C即伪随机函数的输出从字符串变成矩阵，同样降低了KKRT16的通信复杂度。

摘要

该论文描述了一个轻量级协议，用于半诚实对手存在的情况下对伪随机函数(OPRF)进行不经意评估。该协议使用了一种新颖的OTE协议，在用于生成大量OPRF实例时特别高效。该协议的OPRF可以用来消除PSI协议对各方项目的位长的依赖。该论文实现了PSI协议的两种变体，并对128位字符串和足够大的集合的PSI，提高了计算效率。只需要3.8秒就可以安全地计算出220个大小集合的交集，而不考虑条目的位长。对于非常大的集合，该协议只比不安全的naive哈希慢4.3倍。

PSI

隐私数据保护最早源于安全多方计算，由姚期智院士借百万富翁问题提出。安全多方计算技术是一种密码原语，在解决数据可控共享问题和保证数据信息安全方面有着天然的优势。隐私集合交集PSI是安全多方计算中的热点问题，允许两个或多个参与方联合计算各自输入集合的交集，但不泄露除交集外的任何额外信息。在隐私保护场景中，PSI具有重要意义，如新冠接触者追踪、隐私通讯录查找、在线广告实际效果计算、基因序列配检测等。

OT扩展协议

不经意传输协议，是通信双方用来传输秘密信息的协议，消息发送者持有两条待发送的消息，接收者选择一条进行接收，事后发送者对接收者获取哪一条消息毫不知情，接收者对于未选择的消息也无法获取任何信息。

OT扩展协议的提出主要是为了解决在执行大量OT协议时公钥密码学原语所带来的巨大开销，其主要思想为参与双方先执行少量 Base OT 协议交换“种子”信息，然后通过高效的对称密钥原语(如哈希函数、伪随机数生成器(PRG)、伪随机函数(PRF)等)对种子信息进行长度扩展，进而生成大量 OT 实例。

IKNP具体内容可以看以下内容。

不经意传输(OT)协议 - Mike Rosulek教授课堂笔记_Wuli LQueen的博客-CSDN博客

隐私相等性检测

隐私集合求交场景下有一特殊情况是隐私相等性检测，即两个参与方希望知道两个字符串是否相等。Pinkas、Schneider、Segev和Zohner在2015年提出一PSI协议，他们的PSI协议通过不经意传输扩展实现隐私相等检测，还提出了一个高效的哈希技术，可以将隐私相等检测高效转换为隐私集合求交。

Pinkas、Schneider、Segev、Zohner提出的隐私相等检测协议：

Alice拥有 x=001 ，而Bob拥有 y=011，想知道 x=y 是否成立。他们协议的核心就是利用OT协议对 x 和 y 进行逐比特对比。首先，Bob分别为 0 和1随机采样两个 k 比特长的字符串。随后，Bob和Alice执行不经意传输协议，Alice的输入是她的第一个比特0。协议执行完毕后，Alice收到她第一个比特 0 所对应的字符串0。在此过程中，Bob无法得知Alice的输入是什么。他们继续对第二个比特、第三个比特执行此种操作。现在，Bob从OT协议中取得自己的隐私集合比特所对应的字符串。他的输入比特是011，因此他分别取得0、1、1所对应的三个字符串。他对几个字符串求异或，将结果发送给Alice。Alice也取得OT执行完毕后的结果，即0、0、1所对应的三个字符串。她对几个字符串求异或，并对比Bob发送过来的异或值。这样Alice就知道双方的输入是否相等了。这就是该PSI协议的隐私相等检测过程。

KKRT16

这篇论文的核心技术贡献就是提高隐私相等检测的效率。

该协议将多个 1-out-of-2 OT协议替换为 1-out-of-n OT协议，利用了KK13-OTE协议。

在该论文中，提出了一个OT扩展协议。此协议中的 N 可以任意大。这样，只需要使用一次OT就可以实现隐私相等检测过程。

我们将此协议看成一个黑盒。如果Alice的输入是 x ，而Bob的输入是 k ，这里 k 包含右侧的6个数据块，在PSI协议执行完毕后，Alice收到字符串0、0、1的异或值，我们可以将此异或值看成 $F_{k}(x)$ 。这意味着协议执行完毕后，Alice只能知道 x 所对应的 $F_{k}(x)$ 。而Bob已知全部的6个数据块，因此Bob可以对任意 y 计算得到 $F_{k}(y)$ 。如果 $x\neq y$ ，则对Alice来说 $F_{k}(y)$ 看起来是个随机数。因此，此协议本质上就是一个不经意伪随机函数。进一步，如果Bob将异或值，也就是 $F_{k}(y)$ 发送给Alice，则Alice可以比较 $F_{k}(x)$ 和 $F_{k}(y)$ ，看这两个值是否相等。这就是隐私相等检测协议的原理。

KKRT16等人通过对KK13-OTE的观察发现通过OTE构建隐私相等性测试时，并不需要对纠错码C进行解码，只需要比较两个纠错码映射的值是否相等即可。对于任何两个 r 和 r '，只需要保证 $C(r)\oplus C(r')$ 的汉明距离不小于计算安全参数即可。

因此KKRT16提出他们并不需要纠错码C，只需要一个汉明距离不小于计算安全参数的伪随机函数即可。这是非常小的一个改变但也是本文最重要的一个改变！这使得基于KKRT16-OTE的PSI协议比基于KK13-OTE的PSI协议提升了3倍！

如果将 C 替换为随机函数，则该协议可以支持任意长度的 $r_{i}$ 。也就是说，这里的 $r_{i}$ 可以为任意比特长。从Bob的角度看，他可以计算得到 $H(q_{i} \oplus C(r') \odot s)$ 。在该协议中，Bob可以计算任意哈希值，而Alice只能知道其中一个哈希值。

这就是协议的完整执行流程。

如果 $r_{i}\neq r'$ ，则 $F_{s,q_{i}}(r')$ 看起来像是随机数。而 $F_{s,q_{i}}(r)=H(q_{i}\oplus C(r)\odot s)$ 。

OT矩阵的每一行都定义了一个OPRF实例，每一行对应的第二个密钥 $q_{i}$ 均不相同，但第一个密钥 s 是相同的。因此，得到的是批处理密钥相关OPRF。

很容易在PSI上应用此OPRF。Bob将 $F_{s,q_{i}}(r')$ 发送给Alice，Alice简单比较 $F_{s,q_{i}}(r_{i})$ 和 $F_{s,q_{i}}(r')$ ，并告知这两个值是否相等。如果 $r_{i}\neq r'$ ，则对Alice来说 $F_{s,q_{i}}(r')$ 就是一个随机数，Alice无法猜测得到有关 r' 的任何信息。