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 , where is the private input of Alice, and is the private input of Bob. Let and , where and 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 OTs, where Alice is the sender and Bob is the receiver. Alice obtains , and Bob obtains

  • Alice chooses uniformly random labels . Alice uses and global to generate the garbled circuit of and sends to Bob. Alice also sends the decoding information to Bob.

  • Alice encodes her inputs and sends to Bob.

  • With the encoded labels and labels, Bob evaluates to get the output labels, and then decodes these output labels with decoding information and gets the output bits.