Naor Pinkas OT -发件人安全性.减少到DDH

Question

这个问题涉及到Naor Pinkas OT中发送者的安全。协议可以找到这里。

我们可以将安全性降低到DDH假设。这到底是怎么做到的？有人能建造一个显示这种减少的对手吗？

简化这个问题。使用基于模拟的定义，真实视图和模拟视图使我们无法区分$(g^a，g^b，g^c，g^{a\cdot b})$和$(g^a，g^b，g^{a\cdot b}，g^c)$。

让我们假设$D$可以区分这两个分布(可以用不可忽略的概率来区分)。

也就是说，$$|\mathsf{Pr} -\mathsf{Pr}溶胶$是不可忽略的。

什么样的对手能够打破DDH假设？也就是说，我们必须构造$A(D)$ (它接受$D$作为输入)，这样$$|\mathsf{Pr} -\mathsf{Pr}$是不可忽略的。

谢谢

Answer 1

<#>提示

由于DDH，我们有$(g^a，g^b，g^{a\cdot b}，g^c)$和$(g^a，g^b，g^c)$是不可区分的(其中$c'$是一致随机的，独立于$c$)。由于同样的原因，$(g^a，g^b，g^c，g^{a\cdot b})$和$(g^a，g^b，g^c}，g^{c'})$无法区分。

你能看到怎么把东西放在一起吗？