Oblivious Transfer

Main motivation that blew my mind when started learning about OT was that it could be used by multiple parties to compute arbitrary functions. It’s one of the most basic primitive in mpc that allows building gc, pir,

Oblivious transfer: Alice and Bob are two parties allowed to participate. Alice has access to message: $m_0,m_1\in \{0,1{\}}^k$, and Bob wants to know $m_b$, where $b\in \{0,1\}$ of its choice. Alice wants to ensure that $m_{1-b}$ remains hidden in the process.

$\frac{1}{2}-OT$

flowchart LR
subgraph S
b
end
S-->ROT["Rabin OT"]
ROT--1/2-->R1["b"]
ROT--1/2-->R2["#"]
subgraph R
R1
R2
end

Originally introduced by Rab81, where sender can send the message with probability 1/2, and thus, it’s name as $\frac{1}{2}-OT$.¹

• run $\text{GenModulus}\to (N,p,q)$ such that $N=pq$ and $p,q$ are prime.
• receiver choose x\xleftarrow{\}{ 1,\dots,N-1 }$,where$\gcd(x,N)=1$,compute$t=x^2 \mod{N}$.
• Sender knowing, $p,q$ computes $s=\sqrt{t}$, and send to R.
  • Note: there are four values possible for $t$, i.e. $\pm x,\pm y$. Sender chooses 1 out of 4 randomly.
• Receiver factors $N$, if $t=\pm y$ as $\gcd (N,x+s)$ OR $\gcd (N,x-s)$.
• $\mathrm{Pr}[t=\pm y]=\frac{1}{2}$.

$\frac{1}{2}-OT$ implies $$\begin{gathered} \left(\text{array}2 \\ 1\right)-OT \end{gathered}$$: Proven in Cre87.

OT variations

Simple 1-2 OT: sender has two messages, and receiver receives 1 out of 2 messages. Mainly used for secure evaluation of GC.

Oblivious Key Generation: ¹

Apart from the 3 PKE method: $\text{Gen,Enc,Dec}$, introduce a new $\text{OGen}(r)\to pk$. For $\text{OGen}$ to be secure, it needs to have 3 properties:

• No efficient adversary $\mathcal{D}$ such that $\mathcal{D}(p{k}_b)\to b$, where $p{k}_0\leftarrow \text{Gen}(\cdot );p{k}_1\leftarrow \text{OGen}(\cdot )$.
• A preimage sampling algorithm ${\text{OGen}}^{-1}$ such that $pk\leftarrow \text{OGen}(r),r^{\prime }\leftarrow {\text{OGen}}^{-1}(pk)$, then $\text{OGen(r’)}=pk$, and $r^{\prime }$ is uniformly distributed.
• CPA security of $pk\leftarrow \text{OGen}(\cdot )$.

These can be used to prove 2 properties:

• no efficient $\mathcal{A}$ exists such that $sk\leftarrow \mathcal{A}(r)$, where $\text{Gen}(sk)=\text{OGen}(r)$.
• No efficient $\mathcal{D}$ such that $\mathrm{Pr}[\mathcal{D}(r,\text{Enc}(pk,m_0))=b]$ is noticeable, i.e. no PPT distinguisher that can distinguish between $c_0,c_1$.

Let’s consider a simple 1-2 OT using elgamal-pke (Ideally, any CPA secure PKE, with Oblivious Key Generation (OKE) can be used):

• Two parties involved are Alice, Bob. Alice has two messages $m_0,m_1$, and Bob wants to know one of both.
• Bob generates two keys: Run ElGamal KeyGen to generate a public, private key pair: $(p{k}_b,sk)\leftarrow \text{Gen}(1^n)$, and choose another public key uniformly: pk_{1-b}\xleftarrow{\}\textsf{OGen}(r)$.Send$pk_{0},pk_{1}$ to Alice.
• Alice encrypts both messages: $c_0:={\text{Enc}}_{p{k}_0}(m_0),c_1:={\text{Enc}}_{p{k}_1}(m_1)$. Send $c_0,c_1$ to Bob.
• Bob decrypts $m_b:={\text{Dec}}_{s{k}_b}(c_b)$.

Prove receiver's security for unbounded sender.

Here, $\text{Samp}$ is a oblivious samplable public key, and both $\text{Gen,Samp}$ is identically distributed, it means Sender’s view is identical with respect to a simulator that samples a public private key pair for $p{k}_{1-b}$.

Prove sender's security for computationally bounded semi-honest receiver.

Since CPA secure PKE is used to encrypt both messages, a receiver on getting $c_0,c_1$ is able to know both $m_0,m_1$ with probability $\frac{1}{2}+\text{negl}(n)$, where $n$ is the security parameter. To prove this, run a reduction proof with adversary ${\mathcal{A}}^{\prime }$ that is able to break CPA security of ElGamal PKE, by running adversary $\mathcal{A}$ as a subroutine and simulating honest OT sender. Note that if receiver is malicious than it could generate $p{k}_{1-b}$ such that it knows the secret key, and then, can decrypt $c_{1-b}$.

Above construction is secure in the Ideal-world model, if no malicious adversary exists. So, let’s consider a protocol secure in real-world model.

• RSA
• Bellare-Micali OT
• Naor-Pinkas OT

1-N OT: sender has N messages, $m_1,\dots ,m_n$, and receiver receives 1 out of N message of its choice. Mainly used in PIR.

k-N OT: sender has N messages $m_1,\dots ,m_N$, and receiver wants to receive k out of N message of its choice. Mainly used in PSI.

OT Extensions

Generally, OT is performed in batches with multiple $m$ OTs for $l-$bit strings represented as $O{T}_m^l$. Extension protocols were developed analogous to Hybrid protocols in PK cryptography. So, less OTs have to be performed and keys shared are extended using symmetric cryptographic primitives.

• random OT (ROT): functionality samples two strings for sender: $r_0,r_1\in \{0,1{\}}^l$, with receiver bit as $b$. after the protocol, sender receives $r_0,r_1$ while receiver gets $r_b$.
  • With ROT, $RO{T}_l^m\to O{T}_l^m$ by $\mathcal{S}$ sending $x_0^i\oplus r_0^i,x_1^i\oplus r_1^i$ to receiver
  • Same can be done, if receiver chooses another bit for message.
• correlated OT (COT): Let’s say the difference between both messages is $x_0\oplus x_1=\Delta$.
  • $S\to COT:\Delta$ while $R\to COT:r_b$
  • $COT\to S:(r,r\oplus \Delta );COT\to R:(r\oplus b\Delta )$.
  • Using this, $RO{T}_l^m\to CO{T}_k^m$, i.e. output of COT can be extended to $l-$bit strings using random oracle.

Practical Protocols

Let’s review CO15 protocol that uses 1-N $O{T}_l^m$ using $RO{T}_l^m$ extension:

• Work in set $S$, and group $G:(\mathbb{G},B,p,+)$
• Use a hash function: $H:(\mathbb{G}\times \mathbb{G})\times \mathbb{G}\to \{0,1{\}}^k$ to derive a k bit key from group element.
• want to implement m $$\begin{gathered} (\text{array}n \\ 1)-OT \end{gathered}$$ for $l-$bit messages.
• Receiver $\mathcal{R}$ has indices $(c^1,\dots ,c^m)\in [n{]}^m$, i.e. vector of length $m$ with each value in $[0,n-1]$
• Sender $\mathcal{S}$ has n-length vector of l-bit messages $\{(M_0^i,M_1^i,\dots ,M_{n-1}^i){\}}_{i\in [m]}$.
• At the end, $\mathcal{R}$ receives m-length vector of l-bit strings $(z^1,\dots ,z^m)$ such that $z^i=M_{c^i}^i$.
• first they use Random OT to share keys between sender and receiver.
  • Setup: $y\leftarrow {\mathbb{Z}}_p$, calculate $S=y\cdot g,T=y\cdot S$, send $S$ to $\mathcal{R}$.
  • Choose: Receiver samples $\forall i\in [m]:x^i\leftarrow {\mathbb{Z}}_p$, compute $R^i=c^{i}S+x^{i}B$, and send $R^i$ to $\mathcal{S}$.
  • Key Derivation:
    • $\mathcal{S}$ computes $\forall i\in [m],\forall j\in [n]k_i^j=H_{(S,R^i)}(y{R}^i-jT)$
    • $\mathcal{R}$ computes $\forall i\in [m],\forall j\in [n]:H_{(S,R^i)}(x^{i}S)$
  • at the end of the protocol, $k_R^i=k_{c^i}^i$, i.e. both $\mathcal{S},\mathcal{R}$ has same keys for required indices, and it’s impossible for any ${\mathcal{S}}^{\ast }$ to guess $c^i$.
• ROT -> SOT: add a transfer phase to the protocol. $\mathcal{S}$ sends encryption of messages to receiver
• Transfer: $\mathcal{S}$ compute encryption for all messages: $\forall i\in [m],\forall j\in [n]:e_j^i=E(k_j^i,M_j^i)$ and sends to $\mathcal{R}$
• Retrieve: $\mathcal{R}$ decrypts chosen messages: $\forall i\in [m]:z^i=D(k^i,e_{c^i}^i)$

Questions:

• how to realise H?
• how to realise symmetric encryption E?

Let’s review Naor-Pinkas OT:

• introduced 1-out-of-N protocol using Pseudorandom functions and 1-2 OT. Provides security against semi-honest receiver.

IKNP03:

SFE

Let’s look at how to evaluate functions securely using OT. Since, OT is a complete protocol, it can be used to do secure 2PC for any function.

XOR

our aim is to evaluate $a\oplus b$.

• any participating party will know about the contents of the other party, thus, it’s possible to just share the bits between the two to compute xor.

flowchart LR
Alice-..->Sim["Simulator"]-..->Alice-.(x0).->Sim-.F(x0,x1).->Alice
Sim-.x0.->F--F(x0,x1)-->Sim
B-.x1.->F--F(x0,x1)-->B

• To prove that protocol is secure, then there should exists simulator for both parties that simulates real world for semi-honest adversary in ideal-world model $\widehat{Alice},\widehat{Bob}$.

$\hat{P}$ is used to denote semi-honest adversary, and $P$ is an honest adversary.

• So, the simulator will do bogus communication with adversary to satisfy the transcript, then it’ll extract bit $x_0$ from the transcript, and send to $F$ functionality, which computes $F(x_0,x_1)$ and sends to simulator.
• Simulator forwards this to adversary.
• The protocol is secure, if view of adversary is indistinguishable from real world protocol.

$$\exists {\text{S s.t. (View}}_{{\hat{P}}_{1_{real}}},{\text{Selection}}_{P_{2_{real}}})\approx ({\text{View}}_{{\hat{P}}_{2_{ideal}}},{\text{Selection}}_{P_{1_{ideal}}})$$

• To prove that computation of XOR is secure, consider real world protocol, where A sends $a$ to B, and B sends $b$ to A.
• Now, in real world, let’s consider a simulator for $A$, that extracts $a$ from transcript, sends to $F_{\text{XOR}}$, gets back $a\oplus b$, computes $a\oplus a\oplus b$, sends $b$ to $A$.
• Observe that view of ${\hat{A}}_{ideal}$ with $S$ is indistinguishable from ${\hat{A}}_{real}$, and ${\text{output}}_{B_{ideal}}\sim {\text{output}}_{B_{real}}$.

AND: $a\wedge b$

• For AND, it’s not possible to just share the bits, as the other party can’t compute $b$ from $a,a\wedge b$.
• Let’s first create the ideal world $F_{AND}$ functionality:
  • gets $a$ from $A$, and $b$ from B.
  • compute $a\wedge b$, sends to $A,B$.
• Real world functionality:
  • Alice calculates $a\wedge 0,a\wedge 1$, sends to ideal-world $$\begin{gathered} F_{\text{array}1 \\ 2OT} \end{gathered}$$.
  • gets $b$ from $B$, sends $a\wedge b$ to $B$.
  • B sends $a\wedge b$ to A.
• Let’s consider a simulator $S_1$ for A in ideal world.
  • $S_1$ can extract $a$ from $a\wedge 0,a\wedge 1$ in the transcript.
  • sends to $F_{AND}$, gets $a\wedge b$.
  • sends back to $A$. $B$’s simulator acts similarly.
• from $A$‘s perspective, ${\hat{A}}_{real}\sim {\hat{A}}_{ideal}$ and ${\text{output}}_{B_{real}}\sim {\text{output}}_{B_{ideal}}$.

Composability: Use of 1-2 ideal world OT in previous protocol for real-world protocol is called Composability, where an already 2PC secure protocol can be substituted.

Arbitrary Computation

For doing any arbitrary computation on boolean circuits, 2-2 secret sharing is used to split the shares of boolean bit, so that no intermediate value of a gate can be used to infer input values.²

• To split a bit $b$, choose a random $r$, send $r\oplus b$ to $A$, $r$ to B.

Suppose $A$ has $a_1,a_2$, and $B$ has $b_1,b_2$

• XOR: compute $(a_1\oplus b_1)\oplus (a_2\oplus b_2)$
  • take individual shares and compute xor, i..e $a_1\oplus a_2$, $b_1\oplus b_2$
  • share the results with other party.
• AND: compute $(a_1\oplus b_1)\wedge (a_2\oplus b_2)$,
  • distribute
  • perform $F_{AND}$ on $a_1\wedge b_2,a_2\wedge b_1$

References

• CS598DK: Special Topics in Cryptography
• Don’t overextend your Oblivious Transfer
• Secure Computation Lecture Series
• Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection
• A simple generic construction to build oblivious transfer protocols from homomorphic encryption schemes
• Efficient Batched Oblivious PRF with Applications to Private Set Intersection
• EMP-OT
• Ferret: Fast Extension for coRRElated oT with small communication
• Actively Secure OT Extension with Optimal Overhead
• Supersonic OT: Fast Unconditionally Secure Oblivious Transfer
• A Survey of Oblivious Transfer Protocol
• Post Quantum OT:
  • Endemic Oblivious Transfer
• sdiehl: OT
• OSU-Crypto: libOTe

Footnotes

1. https://www.cs.jhu.edu/~susan/600.641/scribes/lecture13.pdf ↩

2. https://web.cs.ucla.edu/~rafail/Lecture10.pdf ↩