问OT扩展纸:为什么$G_{m+1} \nleq m\x倍AND_B$？

EN

首先，什么是AND_B？AND_B是非对称和协议，在协议中，Alice和Bob各有一个x和y，最后Alice总是什么都不知道(获取输出0)，Bob学习x \land y。在引理4中，它说AND_B可以通过1次调用(^2_1)OT来实现。

那么G_{m+1}是什么呢？G_{m}是一种协议，在该协议中，Alice有一个m-bit长字符串x，而Bob有一些y。最后，Alice总是一事无成(获得输出0^m -- m-bit string，所有的0)，而Bob获得0^m (如果y=0 )或x (如果y=1 )。引理6说G_{m}可以通过m调用AND_B来实现。这很简单:对于i-th调用AND_B，Alice使用x_i ( x中的i-th位)作为AND_B的输入，而Bob使用y作为获取0或x_i的输入。在m调用之后，Bob得到0^m或x。

引理7则说明G_{m+1}不能通过m调用AND_B来实现(在计算上无界对手存在的情况下)。现在，x是Alice的输入，是m+1位字符串，y是Bob的输入，它是位的。有一件事马上就清楚了，如果Alice和Bob继续做他们上面所做的事情，那么Bob就不可能安全地获得所有m+1位，因为始终有最后一个不能安全地传输到Bob的位。

所以他们必须采取不同的做法。但是怎么做呢？一种可能是，鲍勃可以使用y作为AND_B的输入，而不是总是使用y'\ne y作为输入，但也有一些可能性。证据的第一部分只是试图说“不，鲍勃必须总是使用y”。在的证明中，Bob应用1μy=0‘意味着Bob使用y'=1作为AND_B调用的输入，即使是y=0。有3种情况，在第一种情况下，Bob从调用中得不到任何东西--因此没有必要这样做；在第二种情况下，Bob得到了他不应该知道的东西(侵犯了Alice的隐私)；在第三种情况下，它是安全的，Bob得到了他应得的东西，但是他必须在y=1时使用D48，而在y=0时使用0。总之，鲍勃不能做任何不同的事情。

那么爱丽丝能做些不同的事情吗？爱丽丝可以将她的消息x编码成某种(\tau,\sigma)，这样\tau就会被清晰地交给Bob，而\sigma就是m-bit long。因此，如果是y=1，鲍勃可以使用m-invocation of AND_B接收\sigma。然后，Bob可以使用x来解码(\tau,\sigma)。然而，\tau并不独立于x，因此将\tau交给Bob将在y=0时泄漏关于x的信息。请注意，Alice不能只在\tau时将y=1交给D69，因为这意味着Alice知道y。因此，Alice不能做这个编码的事情，必须像以前一样。

现在，由于Bob和Alice不能做任何不同的事情，所以G_{m+1}不可能通过m调用AND_B来实现。