Base OT

We introduce the CO15 OT as the base OT.

Notation. The protocol is described over an additive group $(\mathbb{G},G,p,+)$ of prime order $p$ generated by $G$. Denote $\mathsf{H}:(\mathbb{G}\times \mathbb{G})\times \mathbb{G}\to {\{0,1\}}^{\lambda }$ as a key-derivation function to extract a $\lambda$-bit key from group elements.

Note that $\mathsf{H}$ here is different from the tweakable hash function in garbled circuit.

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

• The sender samples $y\leftarrow {\mathbb{F}}_p$, and computes $S=y\cdot G$ and $T=y\cdot S$.

• The sender sends $S$ to the receiver, who aborts if $S\notin \mathbb{G}$.

• For $i\in [n]$, the receiver samples $x_i\leftarrow {\mathbb{F}}_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 \mathbb{G}$.

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

• For $i\in [n]$, the receiver computes $k_i=\mathsf{H}(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_{i}y)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=(y{x}_i)G$, then the receive will get ${\mathsf{X}}_i^0$. if $b_i=1$, $k_i^1$ is the hash of $y{R}_i-T=y(S+x_{i}G)-T=(y{x}_i)G$, then the receiver will get ${\mathsf{X}}_i^1$.

Security. We refer the security analysis to CO15.