如何从n OT中1/2 OT的单个实例中生成1/2 OT的logn实例？

Question

我在看报纸改进的OT扩展。作者认为，在半诚实模型中，可以使用n个OT中1的单个实例来从2 OT生成1的\log n实例。更准确地说，\text{OT}_{l}^m的成本与n \text{OT}_{l\log n}^{m/\log n}中的1的成本完全相等。

我不知道为什么会这样。有关于这件事的参考资料吗？

Answer 1

通过执行以下操作，您可以使用一个\log n OT生成1/2 OT的1-of-n实例。

让我们修正一下符号。让x作为接收方的选择索引，r_1, \dots, r_n是来自发送方的输入，因此在协议的末尾，接收方获得r_x。注意，x有\log n位。

另外，让\log n 1-of-2 OT的输入为接收方为b_1, \dots, b_{\log n}，发送方为(m_0^1, m_1^1), \dots, (m_0^{\log n}, m_1^{\log n})。

现在，接收方只将\log n选择位b_i编码成x。发送方为所有i \in [n]编码r_i = (m_{bit(1,i)}^1 || \dots || m_{bit(\log n,i)}^{\log n}) ，其中bit(j,i)是i比特分解的j第四位.