Oblivious Transfer

Oblivious transfer (OT) protocol is an essential tool in cryptography that provides a wide range of applications in secure multi-party computation. The OT protocol has different variants such as $1$-out-of-$2$, $1$-out-of-$n$ and $k$-out-of-$n$. Here we only focus on $1$-out-of-$2$.

An OT protocol involves two parties: the sender and the receiver. The sender has $2$ strings, whereas the receiver has a chosen bit. After the execution of this OT protocol, the receiver obtains one of the strings according to the chosen bit, but no information of the other string. Then sender get no information of the chosen bit.

                    Sender                               Receiver
    
                                      +----------+
                    (x_0,x_1) ------->|          |<------ b
                                      | OT Prot. |
                                      |          |-------> x_b 
                                      +----------+                

Due to a result of Impagliazzo and Rudich in this paper, it is very unlikely that OT is possible without the use of public-key cryptography. However, OT can be efficiently extended. That is, starting with a small number of base OTs, one could create many more OTs with only symmetric primitives.

The seminal work of IKNP03 presented a very efficient protocol for extending OTs, requiring only black-box use of symmetric primitives and $\lambda$ base OTs, where $\lambda$ is the security parameter. This doc focuses on the family of protocols inspired by IKNP.