Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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:
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:
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.
