Semi-Honest Oblivious Transfer (OT) Primitives

This page describes a few basic protocols for oblivious transfer (OT) schemes and some theoretical results related to them. The next post will consider OT extensions — which are needed when performing a large number of oblivious transfers.

Semi-Honest Base OT: Syntax and Semantics

Semi-honest Alice (𝔸) has two single-bit messages 𝑚0 and 𝑚1. Semi-honest Bob (𝔹) has a single choice bit 𝑏. Alice wants to send one — and only one — of her two messages to Bob. Bob, depending upon his choice bit 𝑏, wants to access 𝑚𝑏 but does not want Alice to know which message he picked. This interaction is summarized in the following diagram:

Generalization

The definition for 1-out-of-2 oblivious transfer can be extended to 𝑘-out-of-𝑛 oblivious transfer in a natural way: Sender has 𝑛 messages {𝑚0,⋯,𝑚𝑛−1} out of which the receiver can choose any 𝑘 of them but must remain oblivious to the rest of 𝑛−𝑘 messages. Furthermore, the sender should remain oblivious to the messages that the receiver selected.

We use the notation (21) to mean 1-out-of-2 oblivious transfer, and (𝑛𝑘) to mean 𝑘-out-of-𝑛 oblivious transfer.

NOTE: The ordering of 𝑚0 and 𝑚1 is arbitrary and nothing prevents a malicious sender from swapping 𝑚0 with 𝑚1. This, and other potential deviations from the prescribed protocol, need to be handled using a maliciously secure oblivious transfer scheme which is not covered in this document. This document only considers semi-honest adversary, which never deviates from the prescribed protocol. (Of course, a semi-honest adversary is not much of an adversary, but it’s a useful building block for almost all maliciously secure OT schemes.)

The correctness requirements for an OT protocol are obvious: If Bob’s choice bit is 𝑏, then ∀𝑚0,𝑚1∈{0,1}, with high probability, Bob should receive 𝑚𝑏. The privacy requirements are stated after introducing some notation.

Notation

Let 𝑓(𝑥1,⋯,𝑥𝑛) be a function that 𝑛 parties P1,⋯,P𝑛 wish to compute jointly, where each party wants to keep its input 𝑥𝑖 secret. Let 𝜋𝑖 be the protocol executed by party P𝑖 to jointly evaluate 𝑓(𝑥1,⋯,𝑥𝑛). Abusing notation, we will use 𝜋 to mean the overall protocol (an interactive Turing machine) that produces all the necessary outputs that are exchanged between parties.

Given the protocol 𝜋, the following notation is used throughout this document:

• As always, the inputs to 𝜋 from the same party are listed consecutively and separated by a semicolon ‘;’. In particular, OT as a (co-operatively evaluated) function is represented as:

  OT(𝑚0,𝑚1;𝑏)→𝑚𝑏

  As a boolean function, OT can be expressed as:

  OT(𝑚0,𝑚1;𝑏)=(𝑚0∧¬𝑏)⊕(𝑚1∧𝑏)

  Similarly, OT can also be expressed as an arithmetic function over a finite field {0,1}⊆𝔽 as

  OT(𝑚0,𝑚1;𝑏)=𝑚0⋅(1−𝑏)+𝑚1⋅𝑏

• Alice’s view while interacting with Bob is denoted by

  View𝔸(𝑚0,𝑚1,𝑟𝔸;𝑏)

  where 𝑟𝔸 is Alice’s private randomness used during that particular execution of the protocol. View𝔸(𝑚0,𝑚1,𝑟𝔸;𝑏) consists of all of Alice’s local inputs (𝑚0,𝑚1,𝑟𝔸) as well as all the messages she has received from Bob. Note that at any point in time, Alice’s view contains all the information she needs to deterministically generate all outgoing messages from Alice to Bob.

• Similarly Bob’s view is denoted by

  View𝔹(𝑏,𝑟𝔹;𝑚0,𝑚1)

  which includes Bob’s local inputs (𝑏,𝑟𝔹) as well as all messages received from Alice.

• For a given execution of a protocol, all messages sent between Alice and Bob is collectively called the (communication) transcript and is denoted by

  𝜏(𝑚0,𝑚1,𝑏;𝑟𝔸,𝑟𝔹):=⟨𝔸,𝔹⟩(𝑚0,𝑚1,𝑏)

  where 𝑟𝔸 and 𝑟𝔹 is the specific choice of randomness that was used during that particular execution of the protocol, and ⟨𝔸,𝔹⟩(⋯) denotes the messages that were seen on the wire. When the role of 𝑚0,𝑚1,𝑏,𝑟𝔸 and 𝑟𝔹 is understood from context, we simply use 𝜏 to denote 𝜏(𝑚0,𝑚1,𝑏;𝑟𝔸,𝑟𝔹).

  Since each execution of the protocol uses fresh randomness, 𝜏(𝑟𝔸,𝑟𝔹) is a random variable across different runs the protocol even for the same value of (𝑚0,𝑚1,𝑏). Furthermore, since the protocol is required to terminate after a finite number of steps, the maximum number of random bits used in any execution of the protocol is finite. We use the notation

  𝕋(𝑚0,𝑚1,𝑏):={𝜏(𝑚0,𝑚1,𝑏;𝑟𝔸,𝑟𝔹)∣𝑟𝔸,𝑟𝔹$←{0,1}∗}

  to denote the set of all possible transcripts that the protocol can generate by varying 𝑟𝔸 and 𝑟𝔹. Since the set of values for 𝑟𝔸 and 𝑟𝔹 is finite, the size of the set 𝕋(𝑚0,𝑚1,𝑏) is finite.

Note that:

1. Given the views of Alice and Bob, the transcript can be generated deterministically.
2. While the views of Alice and Bob are private, the transcript is public and known to both Alice and Bob.

The privacy requirements for Alice and Bob can be summarized as:

Privacy Requirements

1. Alice’s Privacy: Let Bob’s choice bit be 𝑏 and let D be a polynomial time algorithm (called a distinguisher) that a corrupt Bob is trying to use to glean extra information about 𝑚1−𝑏 from its message transcript

   𝜏:=⟨𝔸,𝔹⟩(𝑚0,𝑚1,𝑏)

   An OT scheme preserves Alice’s privacy if, given

   • the transcript 𝜏,
   • Bob’s input bit 𝑏, and
   • the result 𝑚𝑏

   the probability with which D can distinguish 𝑚1−𝑏 from 1 (or, for that matter, 0) with probability significantly greater than 12 is negligible, i.e.,

   ∀D∈p.p.t∧∀𝜏:𝐏𝐫[D(𝑏,𝑚𝑏,𝜏)=1]<12+negl

   where the probability is taken over the private random choices of Alice and Bob (i.e., 𝑟𝔸 and 𝑟𝔹) as well as the internal randomness of D.

2. Bob’s Privacy: Let D′ be a polynomial time distinguisher that corrupt Alice is trying to use to find information about 𝑏 from her message transcript 𝜏. An OT scheme preserves Bob’s privacy if, given 𝜏, the probability that D′ can guess the value of 𝑏 with probability significantly greater than 12 is negligible, i.e.,

   ∀D′∈p.p.t∧∀𝜏:𝐏𝐫[D′(𝑚1,𝑚0,𝜏)=𝑏]<12+negl

   where the probability is taken over the private random choices of Alice and Bob as well as the internal randomness of D′.

OT Theoretical Results

This section lists some well known theoretical results related to Oblivious Transfer.

Theorem

Information theoretically secure oblivious transfer schemes don’t exist.

We will prove this theorem in two stages: First we will show that given any oblivious transfer scheme

one can use it as a black box to construct a two party MPC protocol 2pc∧ that computes the boolean `and` (∧) of two bits 𝑎 and 𝑏, i.e.,

Second, we will prove that there does not exist any information theoretically secure 2pc∧(𝑎;𝑏) and conclude the contrapositive that there does not exist any information-theoretically secure OT scheme.

Proof [ OT⟹2pc∧ ] :

Suppose Alice has bit 𝑎 and Bob has bit 𝑏 and Alice and Bob want to jointly compute 2pc∧(𝑎;𝑏) using OT(𝑚0,𝑚1;𝑏) as a black box.

Here’s how the two parties proceed (See figure above for pictorial representation of these steps):

1. Alice acts as the OT sender and Bob acts as the OT receiver.
2. As an OT sender, Alice feeds her two inputs as 𝑚0:=0 and 𝑚1:=𝑎 to the OT black box.
3. As an OT receiver, Bob feeds his choice bit 𝑏:=𝑏 into the OT black box.
4. Bob broadcasts the final result of OT back to Alice.

Claim: The output of above oblivious transfer setup securely computes 𝑎∧𝑏. Reason:

1. Correctness holds because OT(0,𝑎;𝑏)=[0∧(¬𝑏)]⊕[𝑎∧𝑏]=𝑎∧𝑏.

2. Alice’s privacy holds because of OT sender’s privacy guarantee: Namely, if 𝑏=0 then the receiver always gets 0 as its output — regardless of the value of 𝑎! Note that when 𝑏=1, then any 2-party MPC and protocol will reveal the value of 𝑎, but that’s not a privacy breach because even an ideal world implementation of and function will leak this information. Furthermore, if OT is maliciously secure or semi-honestly secure, then so is 2pc∧.

3. Bob’s privacy holds because of OT receiver’s privacy guarantees. In particular, OT guarantees that the sender will never learn the value of 𝑏 with non-negligible probability.

We now prove that its impossible to have an information theoretically secure two party ∧ gate computation.

Lemma

There is no information theoretically secure 2pc∧ MPC scheme with (a) perfect correctness and (b) perfect privacy.

Suppose there exists such an information theoretically secure 2pc∧(𝑎;𝑏) MPC protocol and suppose one of the parties Alice (whose input is 𝑎) is malicious. We will show that if Alice is computationally unbounded, then just based on the protocol transcript 𝜏(𝑎,𝑏;𝑟Alice,𝑟Bob), she can breach Bob’s privacy (whose input is 𝑏). Note that breaching Bob’s privacy is only meaningful when Alice’s own input 𝑎 is 0. This is because when 𝑎=1, the value of 𝑏 is readily available to Alice (as the final result of the computation) and there’s no expectation of privacy in that case. In short, Alice’s concrete goal is to find the value of 𝑏 given that her own input 𝑎=0.

Proof:

The high level idea of the proof is to build a distinguisher for 𝑏 by exploiting the properties of the transcript set

𝕋(𝑎,𝑏):={𝜏(𝑎,𝑏;𝑟Alice,𝑟Bob)∣𝑟Alice,𝑟Bob$←{0,1}∗}

for different values of 𝑎 and 𝑏. In particular, it’s based on the observation that the transcript set of any 2pc∧(𝑎;𝑏) MPC protocol with perfect correctness and perfect privacy must be identical when either 𝑎=0 or 𝑏=0, i.e.,

𝕋(0,0)=𝕋(1,0)=𝕋(0,1)

but very distinct when 𝑎=1 and 𝑏=1, namely, 𝕋(0,1)∩𝕋(1,1)=𝜙

A computationally unbounded Alice will use these facts (which are proved later in this section), to build a distinguisher to decide if the protocol transcript 𝜏(0,𝑏) is an element of 𝕋(0,0) or 𝕋(0,1) and breach Bob’s privacy.

Here’s the concrete strategy Alice can use:

• Since Alice is computationally unbounded, she can enumerate all possible random values (i.e., 𝑟Alice and 𝑟Bob) used by the protocol to build a table corresponding to the transcript set

  𝕋(1,0)={𝜏(1,0;𝑟Alice,𝑟Bob)∣𝑟Alice,𝑟Bob$←{0,1}∗}

  in her spare time.

• After this table is built, Alice runs her protocol 2pc∧(𝑎;𝑏) with input 𝑎=0 to obtain the transcript 𝜏(0,𝑏). Notice that the table Alice has built is for 𝑎=1 and 𝑏=0, but the actual protocol runs over the values 𝑎=0 and 𝑏 unknown to Alice.

• Given that particular run of the transcript 𝜏(0,𝑏;⋅,⋅), Alice searches through the table 𝕋(1,0) to find if 𝜏(0,𝑏;⋅,⋅) is present or not and concludes:

  𝜏(0,𝑏;⋅,⋅)∈𝕋(1,0)⟹{𝑏=0if true𝑏=1otherwise

The reason this strategy succeeds is because as sets 𝕋(0,0) and 𝕋(1,0) are identical. Concretely that means, if 𝜏(0,0;𝑟Alice,𝑟Bob) corresponds to random coin tosses (𝑟Alice,𝑟Bob) during protocol execution, then there must exist some other random choices (𝑟′Alice,𝑟′Bob) for which 𝜏(1,0;𝑟′Alice,𝑟′Bob) = 𝜏(0,0;𝑟Alice,𝑟Bob). Furthermore, since 𝕋(1,0)∩𝕋(1,1)=𝜙, presence of 𝜏(0,𝑏) in 𝕋(1,0), implies absence from 𝕋(1,1). Therefore, testing for set membership of 𝜏(0,𝑏) in 𝕋(1,0) is sufficient to conclude if 𝑏=0 or 𝑏=1.

The only thing left to prove is that 𝕋(0,0)=𝕋(1,0) and 𝕋(1,0)∩𝕋(1,1)=𝜙. We prove these as two claims separately:

Claim: 𝕋(0,0)=𝕋(1,0)

Proof: First note that the output of 2pc∧(𝑎;𝑏) is the same when either 𝑎=0 or 𝑏=0. We will show that if 𝕋(0,0)≠𝕋(1,0) then it will lead to the breach of perfect privacy assumption.

Let’s suppose that 𝕋(0,0)≠𝕋(1,0). That means, there must exist at least one transcript 𝛾 that is present in 𝕋(0,0) but not in 𝕋(1,0) (or vice versa). Let 𝑟𝛾:=(𝑟𝛾Alice,𝑟𝛾Bob) be the private randomness that was used to generate transcript 𝛾. Since the protocol must terminate in finite number of steps, the length of 𝑟𝛾 is finite. That means, a computationally unbounded adversary can enumerate all possible bit strings of length ∣𝑟𝛾∣ and run the protocol on (𝑎,𝑏):=(0,0) and (𝑎,𝑏):=(1,0) and find out whether 𝛾 corresponds to (𝑎=0)∧(𝑏=0) or (𝑎=1)∧(𝑏=0). In other words, based on 𝛾 alone, the adversary can find out if 𝑎=0 of 𝑎=1 with non-zero probability. This, however, is a breach of perfect privacy assumption, therefore 𝕋(0,0)=𝕋(1,0).

Claim: 𝕋(1,0)∩𝕋(1,1)=𝜙

Proof: This follows immediately from perfect correctness of 2pc∧(𝑎;𝑏). If 𝕋(1,0)∩𝕋(1,1)≠𝜙, that means there exists a transcript 𝛾′ such that 𝛾′∈𝕋(1,0) and 𝛾′∈𝕋(1,1). However the output of 2pc∧(𝑎;𝑏) is completely determined by (𝑎,𝑏) and the transcript 𝛾′. (Note that the internal coin tosses of the protocol implicitly gives rise to different transcripts of the protocol, so one only needs to consider the transcript, which acts as a proxy for the internal coin tosses of the protocol). But since the output of 2pc∧(1;0)=0 but 2pc∧(1;1)=1 it would be a breach of perfect correctness if the same 𝛾′ could output both 0 and 1 based on the internal coin tosses of the protocol. Therefore, under perfect correctness assumption 𝕋(1,0)∩𝕋(1,1)=𝜙

Together, these results prove that one cannot have information theoretically secure oblivious transfer scheme, with perfect privacy and perfect correctness.

Semi-honest OT Constructions

(21) OT from RSA Hardcore predicate

Let 𝑛=𝑝⋅𝑞 be the product of two primes 𝑝 and 𝑞. The group of units in the Ring ℤ/𝑛ℤ has order 𝜙(𝑛)=(𝑝−1)⋅(𝑞−1). Let 𝑒 be coprime to 𝜙(𝑛) and let 𝑑:=𝑒−1mod𝜙(𝑛). Let 𝑥∈(ℤ/𝑛ℤ)× be a unit, then the RSA trapdoor permutation is defined as 𝑓𝑛,𝑒(𝑥)=𝑥𝑒 where 𝑑 is the trapdoor information, i.e., given 𝑦∈(ℤ/𝑛ℤ)× such that 𝑦=𝑓𝑛,𝑒(𝑥) for some 𝑥, then 𝑥=𝑦𝑑mod𝑛.

A result by Alexi, Chor, Goldreich, and Schnorr states that give 𝑛,𝑒 and 𝑦∈(ℤ/𝑛ℤ)×, where 𝑦=𝑥𝑒 for some unknown 𝑥, then computing the exact value of 𝑥 from 𝑦 is at least as hard as computing the least significant bit of 𝑥 (i.e., lsb(𝑥)). In other words, the least significant bit of 𝑥 is the hard core predicate of the RSA trapdoor permutation.

Assuming semi-honest adversary, the following scheme uses RSA hardcore predicate to build a 1-out-of-2 OT protocol.

Setup:

Based on security parameter 𝜆 (say 𝜆=2048), the OT sender Alice (𝔸), generates two random primes 𝑝 and 𝑝 of size 𝜆/2 and computes 𝑛=𝑝⋅𝑞, 𝜙(𝑛), 𝑒 and 𝑑 as described before. This one time setup can be reused for different runs of the OT Protocol with potentially different receivers. After computing these values, 𝔸 sends (𝑛,𝑒) to the OT receiver Bob (𝔹) and keeps (𝑛,𝑒,𝑑) private.

Protocol Execution:

• 𝔹⟶𝔸: [𝔹’s choice bit is 𝑏∈{0,1}]

  • 𝔹 samples two random numbers as follows

    𝑠$←(ℤ/𝑛ℤ)×𝑇$←(ℤ/𝑛ℤ)×

    and computes

    𝑆:=𝑠𝑒mod𝑛

  • Depending upon the choice bit 𝑏, 𝔹 prepares a message Ω consisting of two Ring element from ℤ/𝑛ℤ as follows:

    Ω:={(𝑆,𝑇)if 𝑏=0(𝑇,𝑆)if 𝑏=1

    and sends Ω to 𝔸 in the left to right tuple order (i.e., sends 𝑆 then 𝑇 if 𝑏=0, otherwise, sends 𝑇 then 𝑆).

• 𝔸⟶𝔹: [𝔸’s input messages are 𝑚0,𝑚1∈{0,1}]

  • Suppose 𝔸 receives Ω=(𝑋,𝑌). Since 𝔸 has access to RSA trapdoor information 𝑑, it computes

    𝑥=𝑋𝑑mod𝑛𝑦=𝑌𝑑mod𝑛

    and extracts the hardcore bits directly as lsb(𝑥) and lsb(𝑦) and prepares the response message Δ as follows:

    𝑐0:=𝑚0⊕lsb(𝑥)𝑐1:=𝑚1⊕lsb(𝑦)Δ:=(𝑐0,𝑐1)

  • 𝔸 then sends Δ to 𝔹.

• 𝔹 Selection: Depending upon the choice bit 𝑏, 𝔹 computes 𝑚𝑏 as follows:

  𝑚𝑏=𝑐𝑏⊕lsb(𝑠)

Perfect Correctness

When both 𝔸 and 𝔹 are honest, the trapdoor information 𝑑 allows 𝔸 to compute the exact value of 𝑠 from (𝑋,𝑌). Given 𝑠, 𝑐𝑏 can be thought of one-time pad encryption of message 𝑚𝑏, which 𝔹 can correctly decrypt.

Perfect Privacy

• 𝔸’s privacy against computationally bounded semi-honest 𝔹: Since 𝔹 is semi-honest, it follows the protocol exactly as described. In particular, it only knows the value of 𝑠=𝑆𝑑mod𝑛 and not the value of 𝑡=𝑇𝑑mod𝑛. (By construction, 𝑇 was selected randomly and 𝔹 doesn’t know 𝑑 that it could use to compute 𝑡 with significant probability). Therefore, it can only decrypt one of 𝑐0 or 𝑐1 with high probability.

  More formally, assuming that lsb(⋅) hardcore predicate of the RSA function can be predicted with probability 1/2+𝜖, given 𝑐1−𝑏 and 𝑇, 𝔹 can predict the value of 𝑚1−𝑏 with probability 1/2+𝜖.

• 𝔹’s privacy against computationally unbounded malicious 𝔸: Since 𝑆 and 𝑇 are identically distributed 𝔸 cannot predict with probability greater than 1/2 which bit 𝔹 is interested in. Therefore, 𝔹’s privacy is information theoretically guaranteed. (NOTE: it’s important that 𝑇 is sampled uniformly from the group of units of ℤ/𝑛ℤ, otherwise a computationally unbounded 𝔸 will be able to breach 𝔹’s privacy.)

The figure below summarizes the protocol pictorially:

(21) String-OT from DDH Assumption [Naor and Pinkas, SODA ‘01]

In a String-OT protocol, the sender has two binary strings 𝑚0,𝑚1∈{0,1}ℓ (of agreed upon maximum length ℓ) instead of two bits to send to the receiver. The receiver still has a single bit choice 𝑏∈{0,1}. The sender wants to send only one of 𝑚0 or 𝑚1 to the receiver and the receiver wants to hide its choice bit 𝑏.

Let 𝔾 be a cyclic group of order ℓ. Let 𝑎,𝑏,𝑐$←ℤ/ℓℤ be three arbitrary random element from the Ring ℤ/ℓℤ. The group 𝔾 is said to satisfy Decisional Diffie Hellman (DDH) assumption, if for all generators 𝑔∈𝔾 of the group, a computationally bounded adversary cannot distinguish between the distribution of (𝑔𝑎,𝑔𝑏,𝑔𝑎𝑏) from (𝑔𝑎,𝑔𝑏,𝑔𝑐) with non negligible probability. (If the group is of prime order, then any generator 𝑔 with this property will suffice.)

Assuming semi-honest adversary, the following scheme use DDH assumption to build a (21) OT scheme where the two message can be arbitrary group elements.

Setup:

Based on the security parameter 𝜆 the OT sender Alice (𝔸) and Bob (𝔹) agree upon: 1. An appropriate cyclic group 𝔾 of prime order ℓ such that DDH assumption holds with 2−𝜆 distinguishing probability 2. A generator 𝑔∈𝔾 3. A message encoding scheme that encodes bit strings to group elements. From now on, we assume 𝑚0,𝑚1∈𝔾

String-OT Protocol:

• 𝔹⟶𝔸: [𝔹’s choice bit is 𝑏∈{0,1}]

  • 𝔹 samples three random numbers (𝑞,𝑟,𝑡) and computes 𝑠 as follows

    𝑞$←ℤ/ℓℤ𝑟$←ℤ/ℓℤ𝑠=𝑞×𝑟𝑡$←ℤ/ℓℤ

    and further computes

    𝑄=𝑔𝑞𝑅=𝑔𝑟𝑆=𝑔𝑠𝑇=𝑔𝑡

  • Depending upon the choice bit 𝑏, 𝔹 prepares a message Ω consisting of four group elements as follows:

    Ω:={(𝑄,𝑅,𝑆,𝑇)if 𝑏=0(𝑄,𝑅,𝑇,𝑆)if 𝑏=1

    and sends Ω to 𝔸.

• 𝔸⟶𝔹: [𝔸’s input messages are encoded as group elements 𝑚0,𝑚1∈𝔾]

  • Suppose 𝔸 receives Ω=(𝑄,𝑅,𝑋,𝑌). 𝔸 randomly samples

    𝑢0$←ℤ/ℓℤ𝑣0$←ℤ/ℓℤ𝑢1$←ℤ/ℓℤ𝑣1$←ℤ/ℓℤ

  • 𝔸 then computes encryption keys 𝑘0,𝑘1 as follows

    𝑊0=𝑄𝑢0𝑔𝑣0=𝑔𝑞⋅𝑢0+𝑣0𝑊1=𝑅𝑢1𝑔𝑣1=𝑔𝑟⋅𝑢1+𝑣1𝑘0=𝑋𝑢0𝑅𝑣0={𝑔(𝑞⋅𝑢0+𝑣0)⋅𝑟if 𝑏=0𝑔𝑡⋅𝑢0+𝑟⋅𝑣0if 𝑏=1𝑘1=𝑋𝑢1𝑅𝑣1={𝑔𝑡⋅𝑢1+𝑟⋅𝑣1if 𝑏=0𝑔(𝑞⋅𝑢1+𝑣1)⋅𝑟if 𝑏=1

    and encrypts it’s two messages 𝑚0,𝑚1∈𝔾 as

    𝐶0=𝑚0⋅𝑘0𝐶1=𝑚1⋅𝑘1

    and formats the response message as four group elements

    Δ:=(𝑊0,𝐶0,𝑊1,𝐶1)

  • 𝔸 then sends Δ to 𝔹.

• 𝔹 Selection: Depending upon the choice bit 𝑏, 𝔹 computes 𝑚𝑏 as follows:

  𝑚𝑏=𝐶𝑏⋅𝑊−𝑟𝑏

Perfect Correctness

When both 𝔸 and 𝔹 are honest, ∀𝑏∈{0,1}:𝐶𝑏⋅𝑊−𝑟𝑏=(𝑚𝑏⋅𝑔(𝑞⋅𝑢𝑏+𝑣𝑏)⋅𝑟)⋅(𝑔(𝑞⋅𝑢𝑏+𝑣𝑏))−𝑟=𝑚𝑏

Perfect Privacy

• 𝔸’s privacy against computationally bounded semi-honest 𝔹: We analyze the 𝔸’s privacy for different values of 𝑏 separately.

  • Case 𝑏=0: In this case, the information sent by 𝔸 is (𝑔𝑞⋅𝑢0+𝑣0,𝑚0⋅𝑔(𝑞⋅𝑢0+𝑣0)⋅𝑟,𝑔𝑞⋅𝑢1+𝑣1,𝑚1⋅𝑔(𝑡⋅𝑢1+𝑟⋅𝑣1)) Since 𝑢0 and 𝑣0 are sampled independently from 𝑢1,𝑣1, the entries corresponding 𝑊1,𝐶1 is independent from 𝑊0,𝐶0. Furthermore, 𝑊1=𝑔𝑞⋅𝑢1+𝑣1=(𝑔𝑞)𝑢1⋅𝑔𝑣1 and 𝐶1=𝑚1⋅(𝑔𝑡)𝑢1⋅(𝑔𝑟)𝑣1 Assuming semi-honest 𝔹, given that 𝔾 is a prime order group, 𝑔𝑞,𝑔𝑟, and 𝑔𝑡 are also generators of 𝔾. Furthermore since 𝑢1 and 𝑣1 were randomly selected by 𝔸, 𝑊1 and 𝐶1/𝑚1 are random elements of the group for a computationally bounded DDH-adversary 𝔹. Therefore, the probability with which 𝔹 can make inference about 𝑚1 is negligible.

  • Case 𝑏=1: This case is identical to 𝑏=0, except for 𝑢0 and 𝑣0 playing the role that 𝑢1 and 𝑣1.

• 𝔹’s privacy against computationally bounded semi-honest 𝔸: Since 𝔸 receives tuples either of the form (𝑔𝛼,𝑔𝛽,𝑔𝛼⋅𝛽,𝑔𝛾) when 𝑏=0 or of the form (𝑔𝛼,𝑔𝛽,𝑔𝛾,𝑔𝛼⋅𝛽), when 𝑏=1, by DDH assumption semi-honest 𝔸 cannot distinguish whether it’s in 𝑏=0 or 𝑏=1 case with non-negligible probability (this can he shown using hybrid argument). This guarantees 𝔹’s privacy.

The figure below summarizes the protocol pictorially:

(𝑛1)OT from (21) String-OT [Naor and Pinkas, STOC ‘99]

In an (𝑛1)OT scheme, semi-honest sender Alice (𝔸) has 𝑛 messages {𝑥0,⋯,𝑥𝑛−1}, where each 𝑥𝑖 is of length 𝑚 bits. Semi-honest receiver Bob (𝔹) has a choice index 𝑖 with 0≤𝑖<𝑛. Similar to (21)OT scheme, 𝔸 wants to send one — and only one — of 𝑥𝑗’s to 𝔹 but doesn’t want to reveal any additional additional information about other messages. 𝔹, on the other hand, doesn’t want 𝔸 to learn about his choice index 𝑖.

The scheme by Naor and Pinkas achieves (𝑛1)OT by making log⁡𝑛 blackbox invocations to (21)OT. The scheme also requires a PRF/PRP

where 𝜆 is the length of the PRF-key (also assumed to be the security parameter) and 𝑚≥log⁡𝑛.