Please read this blog, if you’ve never heard of GC.
Originally proposed by [Yao82][Yao82] for Secure general 2PC for arbitrary polynomial functions.
a  b  AND 

0  0  0 
0  1  0 
1  0  0 
1  1  1 
AND gate: Two parties involved are Garbler/Evaluator: $A/B$ with individual inputs: $a,b$

Fix an encryption function $Π:(Gen,Enc,Dec)$, where $Enc:K×M→C,Dec:K×C→M$.

$A$ creates two key pairs $(K_{L},K_{R}),(K_{L},K_{R})$

Create garbled table:
a b and $K_{L}$ $K_{R}$ $c_{1}=E(K_{L},E(K_{R},0))$ $K_{L}$ $K_{R}$ $c_{2}=E(K_{L},E(K_{R},0))$ $K_{L}$ $K_{R}$ $c_{3}=E(K_{L},E(K_{R},0))$ $K_{L}$ $K_{R}$ $c_{4}=E(K_{L},E(K_{R},1))$ 
Send $c_{1},c_{2},c_{3},c_{4}$ and $K_{L}$ to $B$

$A,B$ perform 12 OT for $K_{R}$ for bit $b_{′}$ of $B$.

$B$ performs decryption of all ciphertexts, but only one of them is valid.

Performs $a∧b$ and return output to $A$.
Security against:
 Semihonest sender: sender only obtains output of OT and final $a∧b$. If OT is secure against malicious sender, then sender can only obtain information about a’s input which can be inferred from output $a∧b$.
 Semihonest receiver: obtains $c_{i},K_{L},K_{R}$ from $A$. for CPA secure encryption, all ciphertext are indistinguishable to each other. $K_{L},K_{R}$ is chosen uniformly, thus, receiver can’t gain any information from input about $A_{′}s$ bit.
General 2PC
Above protocol can be used to perform general computation on boolean circuits. For each input wire, create Key pairs, and a garbled table for each gate as follows:
a  b  AND 

$K_{L}$  $K_{R}$  $c_{1}=E(K_{L},E(K_{R},K_{out}))$ 
$K_{L}$  $K_{R}$  $c_{2}=E(K_{L},E(K_{R},K_{out}))$ 
$K_{L}$  $K_{R}$  $c_{3}=E(K_{L},E(K_{R},K_{out}))$ 
$K_{L}$  $K_{R}$  $c_{4}=E(K_{L},E(K_{R},K_{out}))$ 
With ciphertexts and two decryption keys, one can decrypt to obtain key for the next intermediate gate. Final output wire decrypts to $0/1$.
 Compute: function $f:{0,1}_{n}×{0,1}_{n}→{0,1}_{∗}$, with inputs $x,y$ with each party.
 Sender computes $4.n$ key pairs for $2n$ input wires.
 Garbles each gate and obtains $4.∣G∣$ ciphertexts, where $∣G∣$ denotes number of gates in the function.
 Sends $K_{1},…,K_{n}$ to $B$.
 Perform n $1−2$ OT to obtain $K_{1},…,K_{n}$.
 $B$ decrypts each gate to obtains keys for subsequent intermediate gate.
 $B$ learns final output $f(x,y)$ and sends it to $A$.
Refer to above protocol as $Π(C,x,y)$ with $C,x$ as sender’s private input, and $y$ as evaluator’s input. Round complexity of above protocol is same as complexity of underlying OT. Using a 2round OT, one can securely compute any function where the circuit itself is private input to the evaluator.
More generally, a Garbling scheme $G$ can be denoted using $(Gb,En,ev,Ev,De)$:
 $Gb(1_{n},f)→(C,e,d)$: circuit $C$, encoding information $e$, decoding information $d$.
 $ev$: plaintext circuit evaluator $ev(C,x)=f(x)$
 $En(e,x)→X$: on input encoding information $e:(K_{i},K_{i})_{i∈[1,n]}$ and input $x∈{0,1}_{n}$ gives garbled input $X$.
 $Ev(F,X)→Z_{′}$: garbled evaluator that on input takes garbled circuit and inputs, and gives garbled output.
 $De(d,Z_{′})→z$: takes the decoding information and gives plaintext output.
Security
Against semihonest adversary:
$Pr[D(1_{n},Π(C,x,y),y,A)=1]−Pr[D(1_{n},S(C(x,y),y),A)=1]≤negl(n)$
For any given function $f:{0,1}_{n}×{0,1}_{n}→{0,1}$ implemented by a boolean circuit $C$, multiEncryption CPA secure $Enc$ function, protocol $Π$ is secure if $∀x,y∈{0,1}_{n}$, PPT adversary $A$, there exists a PPT simulator $S$ such that no PPT distinguisher $D$ can distinguish between real world and simulated protocol.
Informally, there should exists a simulator which can output the transcript of real world protocol from a circuit output $z=C(x,y)$, and evaluator’s input $y$.
First prove for a single gate, then since $Π$ can be used to build protocol for any polynomial function, the following proof holds.
$Π_{S}$ algorithm:

Run $Gen$ of Enc to derive $k_{1},…,k_{5}$, where $k_{5}=k_{z}$ is the output key.

Run $S_{OT}$ on key $k_{3}$ to derive $y$ from the transcript.

Garble the table as follows, and send permuted table.
AND $E(k_{1},E(k_{3},k_{z}))$ $E(k_{1},E(k_{4}),00…00)$ $E(k_{2},E(k_{3},00…0))$ $E(k_{2},E(k_{4},00…0))$ 
send output map as $ϕ=(k_{z}:z,k_{r}:1−r)$, garbled table, and $k_{1}$ to $A$.
Run 4 hybrid arguments and prove each’s probability is negligible:
 Substitute OT in $Π$ to $S_{OT}$ that on input $y$ from evaluator outputs $k_{b,y}$, i.e. the output of ideal OT.
 This is secure due to security of OT protocol.
 Substitute one of the three remaining inputs to $00…0$, i.e. $E(k_{1},E(k_{4},00…0))$, but the rest of the ciphertexts remain same, $E(k_{i},E(k_{i+2},k_{c}))$
 Substitute next two ciphertexts.
 Above hybrid proofs are secure, and can be proven using reduction proof. Adversary $A_{′}$ breaks Enc if distinguisher $D_{∗}$ is able to output correct bit.^{1}
Security against malicious adversary:
$Pr[De(d,A(F,X))∈{f(x),⊥}]≤negl(n)$
Authenticity: any PPT adversary on input garbled circuit $F$ and garbled input $X$ can only output correct plaintext output or aborts. This implies that even an actively corrupted adversary cannot cheat.
 Actively corrupted evaluator: Evaluator performs OT after receiving garbled circuit $F$, i.e. it has access to ciphertexts corresponding to each wire, and wiring information. It can then change the inputs in such a way to receive keys for ciphertexts of its choice, and then aborts the protocol, getting to know about x’s input during this phase.
 How to prevent this? Change the order of ciphertext and OT, i.e perform OT before ciphertext communication.
 Actively corrupted garbler: Garbler can choose circuit $f$ such that it either outputs correct information or aborts (revealing partial information about Evaluator’s inputs).
 Can be handled by randomly evaluating multiple encryptions of circuit by garbler, i.e. let $C_{1},…,C_{k}$ be k different encryptions of same circuit. Evaluator chooses either all but one approach, or majority cutandchoose approach to check if the circuit is same or not.
 Can abort OT such that $Ev$ fails for a wrong key, and garbler learns partial information about Evaluator’s input.
Optimisations
 Pointandpermute: prevent decryption of 4 ciphertext, and pass additional data in keys so that evaluator determines which ciphertext to decrypt.
 Choose a select bit $p∈{0,1}$ and set $p$ as LSB of keys: $K_{0}=K_{0}∥p,K_{0}=K_{0}∥(1⊕p)$, similarly for $K_{1}$.
 Encrypt as $H(K_{i},K_{j})⊕K_{k}$.
 Permute the table canonically by select bits: $LSB(K_{i}),LSB(K_{j})$.
 Evaluator on receiving ciphertexts and key, checks LSB of key and choose the respective ciphertext from the table.
 FreeXOR: select a random difference delta $Δ$, and create keys as $K_{0}=k,K_{1}=Δ⊕k$. Using this, XOR gates can be evaluated independently as $K_{L}⊕K_{R}=K_{L}⊕K_{R},K_{L}⊕K_{R}=K_{L}⊕K_{R}$.
 For FreeXOR to be compatible with Pointandpermute (only when no extra select bit is chosen) $LSB(Δ)=1$.
 Garbled Rowreduction 3: Eliminate one ciphertext by picking one key such that ciphertext for that key is 0.
 Suppose from FreeXOR, first key is $c_{0}=H(K_{L},K_{R})=H(K_{L}⊕Δ,K_{R})$. Set this ciphertext to 0, and xor all other ciphertext with $c_{0}$.
 Evaluator can directly compute the key, if select bits evaluate to 0.
 Garbled RowReduction 2: Use polynomial interpolation instead of onetime decryption to get output keys.
 For odd gates (OR, AND): ciphertexts corresponding to output bit 0 can be used to form a quadratic polynomial $P$. yintercept of this polynomial gives $P(0)=c_{0}$. And extrapolating the polynomial to get 2 more points $P(5),P(6)$. Form a new polynomial $Q=(K_{1},P(5),P(6))$, yintercept of this polynomial $Q(0)=c_{1}$.
 For even gates (XOR, NXOR): create a linear polynomial $P$ using $(1,K_{1}),(4,K_{4})$. Set $K_{3}=P(0)$, set $P(5)$ in garbled table as per select permutation bit. Similarly, create polynomial $Q$ as $(2,K_{2}),(3,K_{3})$. Set $K_{3}=Q(0)$. set $Q(5)$ in remaining garbled table row.
 FleXOR: have more offset instead of one like FreeXOR. Using this, one can make a xor gate more flexible by converting offset on the fly. For a unary gate, let $A,A⊕Δ_{1}$ be the input. To convert this to $A_{∗},A_{∗}⊕Δ_{2}$, set as $A_{∗}=E_{A}(0_{n})$ and send $E_{A⊕Δ_{1}}(A_{∗}⊕Δ_{2})$ as ciphertext. Evaluator on getting key using OT, can generate the key accordingly.
 This can be generalised to binary gate using ${0,1,2}$ ciphertexts depending on whether differences of key pairs $(A,A⊕Δ_{A}),(B,B⊕Δ_{B}),(C,C⊕Δ_{C})$ match. If none match, then $2$ ciphertexts need to be sent for XOR.
 Half gate:
 Garbled Gadgets:
References
 CS355: Lecture 6
 CS498: Lecture 22
 Secure Computation Lecture Series
 Rafail’s Lecture notes: 14
 Orlandi’s CryCom: Lecture 5
 A Gentle Introduction to Yao’s Garbled Circuits
 Ben Lynn notes: Yao’s SFE
 Mina Book: Garbled Circuits
 Mike Rosulek’s talk on GC optimisations