# OT extensions paper: Why is $G_{m+1} \nleq m \times AND_B$?

I am reading this paper, in which Beaver shows how to take a small number of Oblivious Transfers (OTs) and extend them into an arbitrary number of OTs by implementing a pseudo-random number generator inside of a garbled circuit. Very cool.

He then goes on to show that, while this works in the settings where the parties are computationally bounded, it is in fact impossible to do OT-extension when the parties are not computationally bounded.

This is where I'm getting stuck. I don't understand his proof of Lemma 7. What does "Bob applies 1" mean? What are $$x$$ and $$y$$? (I thought they were Alice's and Bob's respective inputs to an $$AND$$ gate, but that does not seem to make sense in the context.)

First, what is $$AND_B$$? $$AND_B$$ is the asymmetric AND protocol, in which Alice and Bob each has a bit $$x$$ and $$y$$, at the end Alice always learns nothing (get output 0) and Bob learns $$x \land y$$. In Lemma 4 it says $$AND_B$$ can be realized by 1 invocation of $$(^2_1)OT$$.
Then what is $$G_{m+1}$$? $$G_{m}$$ is a protocol in which Alice has a $$m$$-bit long string $$x$$, and Bob has a bit $$y$$. At the end, Alice always learns nothing (gets output $$0^m$$ -- $$m$$-bit string with all 0s), and Bob gets $$0^m$$ if $$y=0$$ or $$x$$ if $$y=1$$. Lemma 6 says $$G_{m}$$ can be realized by $$m$$ invocation of $$AND_B$$. It is simple: for the $$i$$-th invocation of $$AND_B$$, Alice uses $$x_i$$, the $$i$$-th bit in $$x$$, as the input to $$AND_B$$, and Bob uses $$y$$ as the input to get either 0 or $$x_i$$. After $$m$$ invocations, Bob get either $$0^m$$ or $$x$$.
Lemma 7 then shows $$G_{m+1}$$ cannot be realized by $$m$$ invocation of $$AND_B$$ (in the presence of a computationally unbounded adversary). Now $$x$$ is Alice's input that is an $$m+1$$ bit string and $$y$$ is Bob's input that is a bit. One thing immediately clear is that if Alice and Bob continue to do what they did above, there is no way Bob can get all $$m+1$$ bits securely because there is always the last bit that cannot be securely transferred to Bob.
So they have to do things differently. But how? One possibility is that instead of always using $$y$$ as the input to $$AND_B$$, Bob may use $$y'\ne y$$ as input, with some probabilities. The first part in the proof simply tries to say "no, Bob has to always use $$y$$". In the proof Bob applies 1 | y=0'' means Bob uses $$y'=1$$ as input to the invocation of $$AND_B$$ even though $$y=0$$. There are 3 cases, in the first case Bob gets nothing from the invocation -- so no point doing this; in the second case Bob gets things he should not know (violation of Alice's privacy); in the third case it is secure and Bob gets what he is entitled, but he has to use $$1$$ when $$y=1$$ and $$0$$ when $$y=0$$. In conclusion, Bob cannot do anything differently.
Then can Alice do something differently? Alice can encode her message $$x$$ into something $$(\tau,\sigma)$$ such that $$\tau$$ is given to $$Bob$$ in clear, and $$\sigma$$ is $$m$$-bit long. So if $$y=1$$, Bob can receive $$\sigma$$ using $$m$$-invocation of $$AND_B$$. Then Bob can decode $$x$$ back using $$(\tau,\sigma)$$. However, $$\tau$$ is not independent of $$x$$, thus giving $$\tau$$ to Bob will leak information about $$x$$ when $$y=0$$. Note that Alice cannot give $$\tau$$ to Bob only when $$y=1$$ because that implies Alice knows $$y$$. Thus Alice cannot do this encoding thing and has to act as before.
Now since Bob and Alice cannot do anything differently, there is no way $$G_{m+1}$$ can be realized by $$m$$ invocation of $$AND_B$$.