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.

Ideal OT functionality

The ideal 1-out-of-2 OT functionality receives from and from , sends to and sends nothing to . In the OT-hybrid model the parties of a protocol may call between any two of them, any number of times, as a trusted subroutine.

Malicious Security

The sender- and receiver-privacy definitions 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 , hands it an input of its choice for the corrupted 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 total communication at most for a polynomial and a constant , 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.

Two-round OT

A two-round OT is an OT with sender privacy and receiver privacy whose interaction is one message each way: the receiver computes and sends , the sender replies with , and the receiver outputs . is as in the syntax above, so a common reference string is allowed. Two-round OT is necessary and sufficient for two-round MPC secure against semi-honest adversaries corrupting any number of parties — BL18, GS18.

UC-secure OT

An OT protocol is UC-secure if it UC-realizes 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. A UC-secure protocol also has sender and receiver privacy with the same reference string, since a UC environment can choose the inputs after learning the reference string through the adversary (UC-secure OT ⇒ OT) — folklore.

Two-round UC-secure OT

A two-round UC-secure OT is a UC-secure OT protocol whose interaction is one message from the receiver followed by one message from the sender, as in two-round OT. The dual-mode protocols of PVW08, from DDH, QR or LWE, and the protocol of DGHMW20, from CDH, are two-round UC-secure OT protocols. Two-round malicious OT in the common reference string model gives two-round MPC secure with abort against a malicious adversary corrupting any number of parties — GS18.

Malicious security with expected polynomial-time simulation

Malicious security with a simulator that need only run in expected polynomial time, with and the distinguisher efficient as before. Malicious security implies it by the identity map (malicious OT ⇒ malicious OT with expected-time simulation) — folklore; the converse is not an identity, as for MPC with expected polynomial-time simulation.

Four-round OT

A four-round OT is an OT protocol with malicious security with expected polynomial-time simulation in the plain model, outputting , whose interaction is four messages sent alternately by the receiver and the sender, the receiver first, and whose simulator is black-box: an oracle algorithm , running in expected polynomial time, such that for every efficient corrupting either party the simulator , which runs only as an oracle and may rewind it, meets the definition. It has malicious security with expected polynomial-time simulation, by the identity map (four-round OT ⇒ malicious OT with expected-time simulation) — folklore. Four-round OT gives four-round MPC against a malicious adversary corrupting any number of parties (four-round OT ⇒ four-round MPC) — CCG+20.

Other results

Participates in

Builds on Oblivious transfer

Produces Oblivious transfer

Barriers

Graph View

Backlinks