]> Cryptography - Oblivious Transfer (OT)

## 1-out-of-$n$ Oblivious Transfer

Suppose $A$ has a list $\left({x}_{1},...,{x}_{n}\right)$, $B$ has $i\in \left\{1,...,n\right\}$.

We want a SFE protocol where ${F}_{A}=0,{F}_{B}={x}_{i}$, that is,

1. $B$ learns ${x}_{i}$ and nothing else

2. $A$ learns nothing about $i$

Theorem: [Kilian'87] 1-out-of-2 OT is universal for 2-party SFE

In other words, given a 1-out-of-2 OT protocol, one can do any 2-party SFE. (Yao's construction requires a block cipher in addition to a 1-out-of-2 OT protocol.)

Note that oblivious transfer implies 2-party SFE, which implies key exchange, and hence 1-out-of-2 OT cannot be built from a blackbox one-way function. Instead, we build one using the DDH assumption [Bellare-Micali'92].

## Bellare-Micali Construction

Let $G$ be a group of prime order $p$, and let $g\in G$ be a generator, and $H:G\to \left\{0,1{\right\}}^{n}$ be a hash function.

Suppose $A$ has ${x}_{0},{x}_{1}\in \left\{0,1{\right\}}^{n}$, and $B$ has $b\in \left\{0,1\right\}$.

1. $A$ publishes a random $c←G$, $B$ picks $k←{ℤ}_{p}$, sets ${\mathrm{PK}}_{b}={g}^{K},{\mathrm{PK}}_{1-b}=c/{g}^{k}$ and sends ${\mathrm{PK}}_{0},{\mathrm{PK}}_{1}$ to $A$. $A$ checks ${\mathrm{PK}}_{0}{\mathrm{PK}}_{1}=c$.

2. $A$ encrypts ${x}_{0}$ with El Gamal using ${\mathrm{PK}}_{0}$, i.e. sets ${C}_{0}=\left[{g}^{{r}_{0}},H\left({\mathrm{PK}}_{0}^{{r}_{0}}\right)\oplus {x}_{0}\right]$, encrypts ${x}_{1}$ using ${\mathrm{PK}}_{1}$, and sends ${C}_{0},{C}_{1}$ to $B$.

3. $B$ decrypts ${C}_{b}$ using $K$, i.e. if ${C}_{b}=\left[{V}_{1},{V}_{2}\right]$, $B$ computes ${X}_{b}=H\left({V}_{1}^{K}\right)\oplus {V}_{2}$.

Security: $A$ cannot learn anything about $b$ (information theoretic result).

If $B$ is honest-but-curious, then assuming DDH, $B$ can only decrypt one of ${C}_{0}$ or ${C}_{1}$.

If $B$ is malicious, then assuming DDH is not enough: conceivably $B$ could generate ${\mathrm{PK}}_{0},{\mathrm{PK}}_{1}$ in such a way that $B$ knows partial information about their corresponding private keys, and perhaps $B$ can then learn partial information about both ${x}_{0}$ and ${x}_{1}$. However, if $H$ is a random oracle, then the protocol is secure under CDH.

## Naor-Pinkas Construction

[Naor, Pinkas '00] Let $G$ be a group of prime order $q$ and let $g\in G$ be a generator. Suppose $A$ has ${m}_{0},{m}_{1}$ and $B$ has $V\in \left\{0,1\right\}$.

1. $B$ sends the tuple $\left(g,x={g}^{a},y={g}^{b},{z}_{0}={g}^{{c}_{0}},{z}_{1}={g}^{{c}_{1}}$ to $A$, where $a,b←{ℤ}_{q}$, ${c}_{v}=\mathrm{ab}$ and ${c}_{1-v}←{ℤ}_{q}$.

2. $A$ verifies that ${z}_{0}\ne {z}_{1}$ and applies a partial DDH random self-reduction: $\left(g,x,y,{z}_{0}\right)$ becomes ${T}_{0}=\left(g,x,{y}_{0},z{\prime }_{0}\right)$, and $\left(g,x,y,{z}_{1}\right)$ becomes ${T}_{1}=\left(g,x,{y}_{1},z{\prime }_{1}\right)$.

3. $A$ encrypts ${m}_{0}$ using ${T}_{0}$ and ${m}_{1}$ using ${T}_{1}$, that is, $A$ sends to $B$ the ciphertexts $\left({\mathrm{CT}}_{0}=\left({y}_{0},\mathrm{mz}{\prime }_{0}\right),{\mathrm{CT}}_{1}=\left({y}_{1},\mathrm{mz}{\prime }_{1}\right)\right)$.

4. $B$ decrypts ${\mathrm{CT}}_{v}$.

This protocol is information theoretically secure against $B$, and DDH secure against $A$. The random self-reduction destroys any partial information in the message $B$ sends to $A$. Note that this construction also generalizes to a 1-out-of-$n$ protocol.

## DDH Random Self-Reduction

Suppose we have a tuple $g,{g}^{x},{g}^{y},{g}^{z}$. Then to perform a random self-reduction, pick random $a,b←{ℤ}_{p}^{*}$, and output $g,{g}^{\left(x+b\right)a},{g}^{y},{g}^{\left(z+\mathrm{by}\right)a}$.

Note that this transformation takes DH-tuples to DH-tuples, and non-DH-tuples to non-DH-tuples. Furthermore, the new exponents are independent of the originals. This is easy to see if we start with a DH tuple. On the other hand, if the tuple is not DH, then given any $x\prime ,z\prime$, there exists a unique $a,b$ such that $\left(x+b\right)a=x\prime ,\left(z+\mathrm{by}\right)a=z\prime$ (we can solve to get $a=\left(z\prime -x\prime y\right)/\left(z-\mathrm{xy}\right)$ and $b$ can be easily determined from $a$). As expected, these solutions are not well defined if $z=\mathrm{xy}$, i.e. the original tuple is DH.

## 1-out-of-n From 1-out-of-2

We show how to construct a 1-out-of-$n$ OT protocol from any 1-out-of-2 OT protocol.

Suppose $A$ has ${m}_{0},...,{m}_{N}\in \left\{0,1{\right\}}^{n}$ and $B$ has $t\in \left\{0,...,N\right\}$. Assume $N={2}^{l}-1$ for some $l$.

1. $A$ prepares $2l$ keys $\left({K}_{1}^{0},{K}_{1}^{1}\right),...,\left({K}_{l}^{0},{K}_{l}^{1}\right)$.

2. Let ${F}_{k}:\left\{0,1{\right\}}^{l}\to \left\{0,1{\right\}}^{n}$ be a PRF. $A$ sends to $B$ the tuple $\left({C}_{0},...,{C}_{N}\right)$: view the message index as a bit string $I={I}_{1}...{I}_{l}\in \left\{0,1{\right\}}^{l}$, and encrypt using

${C}_{I}={m}_{I}\oplus {\oplus }_{i=1}^{l}{F}_{{K}_{i}^{{I}_{i}}}\left(I\right)$

Note $A$ sends $O\left(N\right)$ bits to $B$.

3. Let $t={t}_{1}...{t}_{l}\in \left\{0,1{\right\}}^{l}$. Then $l$ 1-out-of-2 OT's are performed where during the $j$th OT, $A$ has $\left({K}_{j}^{0},{K}_{j}^{1}\right)$ and $B$ has ${t}_{j}\in \left\{0,1\right\}$.

4. $B$ now has ${K}_{1}^{{t}_{1}},...,{K}_{l}^{{t}_{l}}$ and can decrypt ${C}_{t}$ to get ${m}_{t}$.

Thus with $\mathrm{log}N$ 1-out-of-2 OT's, a single 1-out-of-$N$ OT can be constructed, that has $O\left(N\right)$ communication complexity.