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:
- Ted samples $(r_0, r_1, d) \in \mathbb{F}^3$
- Ted sends $(r_0, r_1)$ to Alice
- 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:
- Bob sends $e = c \oplus d$ to Alice
- Alice replies with $(x_0, x_1) = (b_0 \oplus r_e, b_1 \oplus r_\bar{e})$
- 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.