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.