Cryptographic protocol for two-party computation Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit. The history of garbled circuits is complicated. The invention of garbled circuit was credited to Andrew Yao, as Yao introduced the idea in the oral presentation of a paper[1] in FOCS'86. This was documented by Oded Goldreich in 2003.[2] The first written document about this technique was by Goldreich, Micali, and Wigderson in STOC'87.[3] The term "garbled circuit" was first used by Beaver, Micali, and Rogaway in STOC'90.[4] Yao's protocol solving Yao's Millionaires' Problem was the beginning example of secure computation, yet it is not directly related to garbled circuits. Background [ edit ] Oblivious transfer [ edit ] In the garbled circuit protocol, we make use of oblivious transfer. In the oblivious transfer, a string is transferred between a sender and a receiver in the following way: a sender has two strings S 0 {\displaystyle S_{0}} and S 1 {\displaystyle S_{1}} . The receiver chooses b ∈ { 0 , 1 } {\displaystyle b\in \{0,1\}} and the sender sends S b {\displaystyle S_{b}} with the oblivious transfer protocol such that the receiver doesn't gain any information about the unsent string S ( 1 − b ) {\displaystyle S_{(1-b)}} the value of b {\displaystyle b} Note that while the receiver doesn't know the S 0 , S 1 {\displaystyle S_{0},S_{1}} values, in practice the receiver knows some information about what S b {\displaystyle S_{b}} encodes so that the receiver is not blindly choosing b {\displaystyle b} . That is, if S 0 {\displaystyle S_{0}} encodes a false value, S 1 {\displaystyle S_{1}} encodes a true value and the receiver wants to get the encoded true value, the receiver chooses b = 1…