Are there any Oblivious Transfer (OT) protocols that don’t rely on asymmetrical encryption, public-key encryption or key-exchange?

I’m starting to wonder, as all the OT protocols I know of (and can understand how it works), rely on such an encryption layer. Are there any out there which is somewhat-standalone and does not depend on the security of the scheme/protocol it uses underneath?

up vote 6 down vote accepted

The term "stand alone" in secure computation typically refers to the case of a protocol being run once, and not to assumptions. In any case, what I assume you are really asking is what assumptions are needed for OT. You are indeed correct that OT is built from asymmetric assumptions, and this is actually inherent for black-box constructions. This was studied in The Relationship Between Public Key Encryption and Oblivious Transfer.

  • Thank you, it was also thinking in the same direction. This is a great confirmation (and expression) of what I have been thinking. – zetaprime Nov 14 at 8:54

Are there any Oblivious Transfer (OT) protocols that don’t rely on asymmetrical encryption, public-key encryption or key-exchange?

Surprisingly, there are indeed OT protocols which don't rely on public-key encryption. In Precomputing Oblivious Transfer, Beaver showed that if Alice and Bob are each given some correlated randomness by a trusted third party Ted, they are able to compute ${2 \choose 1}$OT without requiring any public-key operations.

In the offline phase, Ted generates a random instance of ${2 \choose 1}$OT:

  1. Ted samples $(r_0, r_1, d) \in \mathbb{F}^3$
  2. Ted sends $(r_0, r_1)$ to Alice
  3. Ted sends $(d, r_d)$ to Bob

Later, in the online phase, Alice has two inputs $(b_0, b_1)$ and Bob has his choice $c$. The players consume the $(r_0, r_1)$ and $(d, r_d)$ as follows:

  1. Bob sends $e = c \oplus d$ to Alice
  2. Alice replies with $(x_0, x_1) = (b_0 \oplus r_e, b_1 \oplus r_\bar{e})$
  3. Bob then outputs $b_c = x_c \oplus r_d$

Note how Ted can play his part in the protocol long before Alice and Bob know their input to the protocol, and his presence is no longer required once he has sent the random OT to Alice and Bob.

In fact, this protocol is information-theoretic secure because even a computationally unbounded Bob cannot determine Alice's other input $b_\bar{c}$, nor can a computationally unbounded Alice learn Bob's choice $c$.

The construction works because Alice has no information on whether Bob knows $r_0$ or $r_1$, while Bob only knows one of $r_0$ or $r_1$. This asymmetry of knowledge is the assumption that allows us to do OT without resorting to public-key cryptography.

This technique is now known as the correlated randomness model, which was studied by Ishai et al in On the Power of Correlated Randomness in Secure Computation. Beaver's multiplication triples (another type of correlated randomness) now feature prominently in state-of-the-art multiparty computation protocols such as SPDZ and BDOZ. These protocols use homomorphic encryption to simulate Ted during an expensive preprocessing phase, which allows them to use efficient information-theoretic operations during the online phase.

  • 1
    I guess this sort of complements the previous answer - but you should really insist of the fact that this only gives OT from weaker assumptions (such as OWF) in a model where the parties are initially given some fixed amount of correlated randomness - in the plain model, the black-box impossibility mentioned by prof. Lindell holds. Also, in alternative models, we could also mention the unconditional constructions of OTs given access to any noisy channel. – Geoffroy Couteau Nov 14 at 23:39
  • Yes, that's a good point, I will emphasize that this isn't in the standard model. I really like how this approach is being used by e.g. SPDZ/BDOZ to split things into an expensive (public key) offline phase that's independent of input followed by a cheap (information theoretic) online phase. It's yet anther example of how clever thinking lets one "work around" impossibility results... – kiwidrew Nov 15 at 0:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.