我们能否通过不经意的传输(OT)协议将伪随机函数( PRF )转换为不经意的PRF (OPRF)？

Question

我是一名软件工程师，所以我一般认为是积木。而且我不太熟悉冷冻术中的数学符号，所以我将继续使用函数调用和函数蓝图(我认为这将是直观的)。

最近，我在这里问和读了几个问题，还有一些关于这些主题的相关论文。因此，我将首先列出如何理解它们的定义，并提出使用OT和PRF的OPRF协议。

请你评论一下这个协议的有效性和安全性。

以下是我的定义，它们是相互独立的。

PRG

Alice启动带有任意种子的PRG。Alice可以生成任意长度n的随机输出，如果Alice在另一个时间，而另一个系统用相同的种子为PRG种子，则输出的前n个比特将与先前得到的输出相同。

PRF

爱丽丝有把钥匙。爱丽丝用这把钥匙启动她的PRF。给定任意长度比特的任何输入，Alice都可以确定地得到任意长度k的随机输出。(大小k和n不一定相互有任何关系)

OT (特别是1-2 OT)

Alice创建两个长度相同(n位)的m0和m1消息。Bob选择0或1并获取相应的消息。爱丽丝不知道鲍勃得到了哪一个，如果他选择了0，鲍勃就会得到m0，也永远不会知道m1 (反之亦然)。

OPRF

鲍勃有个输入。爱丽丝有OPRF功能的钥匙。在执行OPRF期间，Alice交互地根据Bob的输入生成一个随机的输出，但是Bob的输入对Alice隐藏。爱丽丝永远不会知道鲍勃的输入，鲍勃也永远不会知道爱丽丝的钥匙。然而，如果Alice要与Bob共享她的密钥，或者Bob要与Alice共享他的输入，那么同样的“随机外观输出”可能会被重新生成。

根据我所列出的定义，我现在尝试提出一项符合上述OPRF定义的协议。

首先，我将提出一个天真且可能不太安全的版本；并尝试用一个小的转折来解决我所看到的安全问题。

爱丽丝有一个PRG，她就是这样用它来构建PRF的。

//输入和输出是任意大小的位数组。//输出用0初始化(XOR的标识元素)

    prf(key, input[], output[]) {
      prg.setSeed(key)

      for(i = 0; i < input.length; i++) {

      bits0 = prg.nextBits(output.length)
      bits1 = prg.nextBits(output.length)

      if(input[i] == 0)
        output (XOR) bits0
       else
        output (XOR) bits1

      }
    }

这种利用PRG创建PRF的方法建立在以下前提之上：

• 异或运算将保持熵
• PRG将生成不相关的随机序列。

现在Bob想用Alice的密钥来使用这个PRF。OPRF如下。

• Bob有一个大小为n的输入，并想要大小为k的随机输出。
• 爱丽丝用她的钥匙播下了PRG的种子。
• 加班对Bob输入的每一位执行OT协议
• 加班 Alice创建两个大小为k位{bits0，bits1}的随机消息。
• 加班如果鲍勃输入的当前位数为0，则鲍勃选择bits0，否则选择bits1
• 最后，Bob是获得输出的所有消息。

该协议相当于上述PRF。

上述议定书将是安全的：

1. 如果我们只运行这个协议一次
2. 如果Alice在每次执行时都使用随机密钥

因为在第二次运行时，Bob可以切换输入中的位，并从Alice的PRG中学习完整的随机序列。

然而，上述任何一项要求都不现实。要使这一议定书具有安全性，需要采取以下措施：

• Alice需要大小相等的输入。
• Bob有一个2n大小的输入，并且想要一个大小为k的随机输出。
• 使用带有一次种子的PRG，Alice生成n个k位随机掩码。
• Alice在每条消息被重复一次的序列中，生成这些n个掩码的随机排列。(给我们一个2n大小的序列，记住这就是Bob输入的大小)
• 现在，他们对加班输入中的每一位执行OT协议
• 加班 Alice使用序列{bits0 (XOR) maskR，(bits1 (XOR) maskR} )中的下一个掩码创建两个大小为k位的随机消息{bits0，bits1}和XOR。
• 加班如果Bob输入的当前位数为0，则Bob选择蒙面bits0，否则选择屏蔽bits1
• 最后，Bob是所有的信息。

因为掩码会互相取消，这个协议的每一个执行都会包含一个随机的掩码。该议定书仍应等同于上文所界定的PRF，不应受到前一议定书所界定的问题的影响。

这个OPRF的最后一个目标是将它用于专用集交叉协议。见问题中@Mikero的答案：爱丽丝如何使鲍勃能够在私有映射中查找值？

请你评论一下这个协议的有效性和安全性。如果你看到它的任何缺点，我该如何改进它。

Answer 1

基本上，如果我正确理解，您希望创建一个协议，允许Alice和Bob一起计算一个随机值，而不向对方透露它们的秘密(Alice的密钥和Bob的输入)。如果是这样的话，这种协议已经有了一个推广，叫做秘密共享。秘密共享协议的思想是计算只能使用密钥获得的秘密值。这些密钥是在各方之间分配的，每一方都不愿意共享其密钥。