有人能解释OPRF (不经意伪随机函数)是如何基于OT (不经意转移)的吗？

Question

有人能向我解释OPRF是如何基于OT扩展的吗？我目前正在阅读关于使用基于OPRF的高效OT协议的私有集交叉问题的论文，本文的链接在这里：https://eprint.iacr.org/2016/930.pdf。

我理解基于OT的PSI是如何工作的，以及OPRF是如何用于PSI的，但我搞不懂OPRF是如何在基于OT的PSI中隐式使用的。在本文提出的协议中，如果我们只对PSI使用OPRF，在通过OT评估OPRF的情况下，我看不到它们的区别(在计算成本上)。

根据我在他们的协议(s+b)中的理解，OPRFS将被使用，而根据我的理解，如果我们只是将OPRF用于PSI，我们将使用几乎相同数量的OPRFs实例，这将取决于输入的数量。那有什么区别？

Answer 1

从不经意转移

构造一个“不经意伪随机发生器”我将尝试解释你提到的[1]文件的第4.3节。就我个人而言，[2]这篇建立在[1]协议基础上的论文对我帮助很大。 以下是基本想法：

• 发送方和接收方同意哈希函数$ h_i $
• 发送方创建一个包含随机值的数组$G$
• 对于其集合$X$中的每个元素$x $，发送方XOR将$G$的项合在一起，通过散列函数散列$y$获得$G$的索引：

$$ m_{P_1} = \bigoplus_i G $$

• 发送方将这些值(在[2]中称为“摘要值”)发送给接收方。
• 对于其集合$Y$中的每个元素$y $，接收方将使用OT检索与$x$对应的$G$单元格，以便能够计算自己元素的“摘要值”：

$$ m_{P_2} = \bigoplus_i G $$

• 接收方将得到的摘要值与他收到的摘要值进行比较，以找出交集，即$ y_i \in X$当且仅当$ j存在时，~ m_{P_1} = m_{P_2} $。

OT扩展的使用只是一个优化，因为$G$相当大，而且“标准OT”很昂贵。他们还使用了另一个优化，因为$G$是随机填充的，这简单地说就是允许您不支付不使用的$G$的费用。 现在，不经意的伪随机发生器在哪里？首先要注意的是，this不是一个不经意的伪随机函数，而是一个生成器。OPRF必须计算一个定义良好、计算效率高的函数.例如，在本文[3.]中，构造一个OPRF的函数是Dodis-Yampolskiy伪随机函数： $$ f_k(x) = g^{1/(k+x)} \text{在复合阶$n$} $$的群$$中 在[1]和[2]的情况下，我们不是计算“函数”本身，而是“抛出”随机值，这与[1]中给出的"OPRG“的定义相匹配。实际上，我第一次看到术语“不经意的伪随机生成器”是在[1]中，他们定义它的方式(第4.3节的第二个文本块)使我认为他们是第一个使用这个概念的人。 也许这就是让你困惑的原因？因为您也可以使用OPRF构建PSI协议(请参阅[4.])，但这不是他们在[1]第4.3节中所做的。