Cryptology City

Oblivious transfer

Oblivious Transfer (OT) is a two-party protocol between a sender and a receiver . In the basic 1-out-of-2 variant, the sender holds two messages and the receiver holds a choice bit; at the end, the receiver learns the chosen message while the sender learns nothing about the choice, and the receiver learns nothing about the unchosen message.

Syntax

A 1-out-of-2 OT is a pair with message space , following the two-party protocol syntax:

  • is a randomized algorithm generating public parameters,
  • and are stateful interactive algorithms with:
    • input: a pair of messages
    • input: a choice bit
    • output:
    • output:

We write

Properties

Correctness

An OT is -correct if for all and ,

where and When we say is perfectly correct.

Sender Privacy

The receiver should not learn the unchosen message . The adversary commits to a choice bit and two sender input pairs that agree on the chosen value (); after observing the honest receiver’s view, it tries to determine which pair the sender used.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{s-priv}}_{\OT,\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp \gets \Setup(1^\secpar)$
\State $(c, x_0, x_1, x_0', x_1', \stA) \gets \calA(1^\secpar, \pp)$
\Comment{Admissible: $x_c = x_c'$}
\State $(x_0^{(0)}, x_1^{(0)}) := (x_0, x_1)$; $(x_0^{(1)}, x_1^{(1)}) := (x_0', x_1')$
\State $b \getsr \bits$
\State Run $\langle S(\pp, x_0^{(b)}, x_1^{(b)}), R(\pp, c) \rangle$; let $\View_R$ denote R's view
\State $b' \gets \calA(\View_R, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

An OT has sender-private (or message hiding) if for all efficient admissible ,

is negligible. Because , the receiver’s output is identical in both worlds; any distinguishing advantage must come from the view alone.

Receiver Privacy

The sender should not learn the receiver’s choice bit . The adversary commits to sender inputs ; after observing the honest sender’s view, it tries to determine which bit the receiver chose.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{r-priv}}_{\OT,\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp \gets \Setup(1^\secpar)$
\State $(x_0, x_1, \stA) \gets \calA(1^\secpar, \pp)$
\State $c \getsr \bits$
\State Run $\langle S(\pp, x_0, x_1), R(\pp, c) \rangle$; let $\View_S$ denote S's view
\State $c' \gets \calA(\View_S, \stA)$
\Return $[c' = c]$
\end{algorithmic}
\end{algorithm}

An OT has receiver-private (or choice-hiding) if for all efficient ,

is negligible.

Malicious Security

The definitions above are semi-honest: both parties follow the protocol honestly, and security holds against a party that tries to learn extra information from its view. An OT has malicious security if for every efficient that corrupts or and may deviate from the protocol arbitrarily there is an efficient simulator such that, for all and , the output of together with the honest party’s output in a real execution is computationally indistinguishable from the output of together with the honest party’s output in an ideal execution. There the honest party hands its input to a trusted party, hands it an input of its choice for the corrupted party, the trusted party returns to for the resulting and , and also produces — Gol04. The semi-honest games do not carry over by letting deviate: in the sender-privacy game a malicious receiver can announce and run on , so the simulator must extract the choice bit a malicious receiver effectively uses — standard.

Variations

Rabin OT

Introduced by Rab81, Rabin’s OT is a simpler variant where the sender transmits a single message and the receiver obtains it with probability , receiving otherwise — without the sender learning which outcome occurred. Rabin OT and 1-out-of-2 OT are equivalent; each implies the other by efficient reductions.

-out-of- OT

A generalization where the sender holds messages and the receiver chooses a set of size , learning while the sender learns nothing about .

Single-server SPIR is 1-out-of- OT with communication sublinear in , so it implies 1-out-of- OT — folklore; the converse is not known (SPIR ⇒ OT).

OT Extension

OT from public-key primitives requires expensive operations per transfer. OT extension generates any polynomial number of OTs from a number of base OTs that depends only on the security parameter, using only symmetric-key primitives beyond them — Bea96; each extended transfer costs a constant number of hash evaluations in IKNP03.

Random OT

In a Random OT, the parties do not choose their inputs: the sender receives uniformly random and the receiver receives a uniformly random bit and the value . Random OT can be converted to standard OT with a single round of communication.

UC-secure OT

An OT protocol is UC-secure if it UC-realizes the ideal 1-out-of-2 OT functionality in the common reference string model, with as the reference string, against a malicious adversary that statically corrupts either party — Can01. UC security implies stand-alone malicious security, and by the composition theorem a UC-secure protocol can replace the ideal functionality in any protocol in the OT-hybrid model — Can01.

Other results

Participates in

Builds on Oblivious transfer

Produces Oblivious transfer

Barriers

Graph View

Backlinks