我们能用波利格-赫尔曼指数密码和一个PRG来实现一个不经意的PRF吗？

Question

The交换密码设置

• 艾丽斯和鲍勃同意使用2048年位的安全素数p，其中(p-1)/2也是素数.
• 双方都有一个加密指数e在范围(1, p-1)与gcd(e, p-1) = 1。解密指数d选择这样的d * e ≡ 1\bmod (p-1)。爱丽丝有(e_A, d_A)，鲍勃有(e_B, d_B)作为他们的私钥对。

注意:我还发现@fgrieu提出了Pohlig的两个变体，解决了模幂的一些问题。请假设密钥生成是根据双方的解释完成的。变式1，变式2

我们预计，这个交换密码设置应该是足够安全的使用。

The协议

Alice有一条消息m，并且希望对此消息执行一个不经意的PRF。

这些步骤如下：

1. Alice用m种子PRG并生成一个2048 (或2047)位随机输出r a。对于r满足的属性，请通过@fgrieu检查PH变体。
2. Alice用模幂E_A(r) = r^{e_A} \bmod p计算以下加密的随机序列，并将结果发送给Bob。
3. Bob计算E_B(E_A(r)) = (E_A(r))^{e_B}\bmod p = E_{A,B}(r)并将结果E_{A,B}(r)发送回Alice。
4. 最后，爱丽丝计算了D_A(E_{A,B}(r))=(E_{A,B}(r))^{d_A}\bmod p = E_B(r)。

这应该是相同的值，Bob：

• 用消息m为r播下相同的PRG (与爱丽丝从PRG中得到的序列相同)
• 计算E_B(r) = r^{e_B}\bmod p

我认为这个协议应该满足一个不经意的PRF的要求。我假设，在随机输入的情况下，我们可以使用模幂作为PRF。利用模幂的交换性质，我相信我们可以实现一个不经意的PRF。不过，我不确定这是否属实，我也不知道如何证明这一点。

一旦Alice和Bob实现了一个不经意的PRF，我这个OPRF的最终目标就是将它用于私有集交叉协议。基于@Mikero在问题：爱丽丝如何使鲍勃能够在私有映射中查找值？中的回答

您是否在这里看到任何漏洞，无论是泄露任何一方的密钥，还是泄漏Alice的信息？如果有任何可能不安全的点，并且应该避免或修复，您认为我的假设和模块指数的使用有什么问题吗？

Answer 1

我认为这个协议应该满足一个不经意的PRF的要求。

该协议(几乎)与在不透明纸(附录A)中被证明是安全的OPRF是完全相同的。在这里，OPRF被描述为(直到一些正式的表示法)如下，我将在括号中注释您的符号：

参数：以乘法方式编写的组$\mathbb G$ of order $q$，其中离散对数很难实现。哈希函数$H(\cdot，\cdot)：{0，1}^*\\乘\mathbb \to{0，1}^L$。一个散列函数$H'(\cdot):{0,1}^*\to\mathbb $。(您将$H'$称为"PRG“并使用$\mathbb Z_p$，即带有乘法的整数模$p$组，即$\mathbb G$。这意味着，如果它在下面表示$a^b$，就意味着这个组的$a^b\bmod p$。如果您需要关于实例化这些散列函数的指导，请查看听我事先准备好的答案 )

设置：服务器$\mathsf{S}$选择$k\gets_R\mathbb Z_q$，即服务器随机选择一个小于$q$的非负整数。

执行：

$\mathsf U$想要学习$F_k(x)$ with $F:\mathbb Z_q\times {0，1}^*\\ to mathbb {0,1}^l$，而不需要学习$k$，也不想让$\mathsf S$ $k$学习$x$。

1. $\mathsf U\to mathsf S: H'(x)^r$，即$\mathsf U$选择一个$r\gets_R\mathbb Z_q$，存储并发送$H'(x)^r$。(这是协议的第一步和第二步。)
2. $\mathsf S\to mathsf U：\左(H‘(X)^r_右)^k$，即$\mathsf S$简单地用其秘密值对给定的输入进行指数化，并返回结果。(这是协议的第三步)
3. 左(x，\left(\left(H'(x)^r\right)^k\right)^{1/r}\right)$，即$\mathsf U$简单地“取消”接收值(这是交换密码中的解密)，并通过另一个哈希函数返回原始输入和接收值。(最后一个散列步骤已经丢失)

附加说明:在不透明的情况下，$x$是密码，人们可以看到$H'(x)^k$作为"salt“，$H(\text{pw}，s)$是基于密码的密钥派生函数，客户端可以对服务器存储的长期DH密钥对进行解密。然后，这个带短暂键区的密钥对被用于基于DH的标准密钥交换计算(在本例中是HMQV)。