Full Protocol

With garbled circuit and oblivious transfer, we are ready to describe the well-known Yao’s method to construct secure two-party computation protocols for any polynomial-size function.

Given any function $F(x,y)$, where $x$ is the private input of Alice, and $y$ is the private input of Bob. Let $x=x_1\Vert x_2\Vert \cdots \Vert x_{{\ell }_1}$ and $y=y_1\Vert y_2\Vert \cdots \Vert y_{{\ell }_2}$, where $x_i$ and $y_i$ are bits.

Let Alice be the garbler and Bob be the evaluator, Yao’s protocol is described as follows.

• Alice and Bob run a COT protocol to generate ${\ell }_2$ OTs, where Alice is the sender and Bob is the receiver. Alice obtains $({\mathsf{Y}}_1,{\mathsf{Y}}_1\oplus \Delta ),\dots ,({\mathsf{Y}}_{{\ell }_2},{\mathsf{Y}}_{{\ell }_2}\oplus \Delta )$, and Bob obtains $({\mathsf{Y}}_1\oplus y_1\cdot \Delta ,\dots ,{\mathsf{Y}}_{{\ell }_2}\oplus y_{{\ell }_2}\cdot \Delta )$

• Alice chooses uniformly random labels ${\mathsf{X}}_1,{\mathsf{X}}_2,\dots ,{\mathsf{X}}_{{\ell }_1}$. Alice uses $({\mathsf{X}}_1,\dots ,{\mathsf{X}}_{{\ell }_1},{\mathsf{Y}}_1,\dots ,{\mathsf{Y}}_{{\ell }_2})$ and global $\Delta$ to generate the garbled circuit of $F$ and sends $\mathcal{G}\mathcal{C}(F)$ to Bob. Alice also sends the decoding information to Bob.

• Alice encodes her inputs and sends ${\mathsf{X}}_1\oplus x_1\cdot \Delta ,\dots ,{\mathsf{X}}_{{\ell }_1}\oplus x_{{\ell }_1}\cdot \Delta$ to Bob.

• With the encoded $\mathsf{X}$ labels and $\mathsf{Y}$ labels, Bob evaluates $\mathcal{G}\mathcal{C}(F)$ to get the output labels, and then decodes these output labels with decoding information and gets the output bits.