Base OT

We introduce the CO15 OT as the base OT.

Notation. The protocol is described over an additive group $(\bG,\G,p,+)$ of prime order $p$ generated by $\G$. Denote $\sH:(\bG\times \bG)\times\bG\rightarrow \bit^\lambda$ as a key-derivation function to extract a $\lambda$-bit key from group elements.

Note that $\sH$ here is different from the tweakable hash function in garbled circuit.

In the CO15 protocol, the sender holds $n$ $128$-bit strings $\{(\sX^0_i,\sX^1_i)\}_{i\in[n]}$ and the receiver holds $n$-bit string $b\in\bit^n$. The protocol is as follows.

• The sender samples $y\leftarrow \bF_p$, and computes $\S = y\cdot \G$ and $\T = y\cdot \S$.

• The sender sends $\S$ to the receiver, who aborts if $\S\notin\bG$.

• For $i\in[n]$, the receiver samples $x_i\leftarrow \bF_p$, and computes: $\R_i = b_i\S+x_i\G$

• The receiver sends $\{\R_i\}_{i\in[n]}$ to the sender, who aborts if $\R_i\notin\bG$.

• For $i\in[n]$, the sender computes $k_i^0 = \sH(\S,\R_i,y\R_i),~k_i^1 = \sH(\S,\R_i,y\R_i-\T)$ and sends $\{(c_i^0 = k_i^0\oplus \sX^0_i, c_i^1 = k_i^1\oplus\sX^1_i)\}_{i\in[n]}$ to the receiver.

• For $i\in[n]$, the receiver computes $k_i = \sH(\S,\R_i,x_i\S)$, and outputs $c_i^{b_i}\oplus k_i$

Correctness. The receiver always computes the hash of $x_i\S = (x_iy)\G$. The sender sends the hashes of $y\R_i$ and $y\R_i-\T$. If $b_i = 0$, $k_i^0$ is the hash of $y\R_i = (yx_i)\G$, then the receive will get $\sX^0_i$. if $b_i = 1$, $k_i^1$ is the hash of $y\R_i - \T = y(\S+x_i\G)-\T = (yx_i)\G$, then the receiver will get $\sX_i^1$.

Security. We refer the security analysis to CO15.