Computational cryptography › Public-key encryption and key exchange › Classical number theory › Elliptic-curve discrete log
SECURE COMPUTATIONPrimitive

Oblivious transfer

In plain words

A sender has two messages. You get exactly one of your choice. The sender doesn't learn which, and you learn nothing about the other.

The idea: Picture a machine holding two sealed envelopes: you may open exactly one, and the machine never learns which. That is enough to compute anything privately. For example, to evaluate a step of a computation on a secret bit of yours, the other party puts the answer for "bit = 0" in one envelope and the answer for "bit = 1" in the other, and you take the one matching your bit. You learn only your answer, and they don't learn your bit. Chain steps like this and you can run any program on two people's combined secrets.

Why it matters: Sounds small, but it's the building block for computing together on secret data.

The details

On the map: DDH-based base OTs

A sender holds two messages. The receiver gets exactly the one they choose. The sender doesn't learn which, and the receiver learns nothing about the other[1, 2].

It sounds modest, but oblivious transfer is complete for secure computation: with it, parties can compute anything securely[3]. It needs public-key-level assumptions (here DDH)[4]. "OT extension" then turns a few such base OTs into millions using only symmetric cryptography[5].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. How To Exchange Secrets with Oblivious Transfer. IACR Cryptology ePrint Archive, Paper 2005/187. eprint.iacr.org/2005/187
  2. S. Even, O. Goldreich and A. Lempel. A Randomized Protocol for Signing Contracts. Advances in Cryptology, 1983. doi:10.1007/978-1-4757-0602-4_19
  3. Joe Kilian. Founding cryptography on oblivious transfer. Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88, 1988. doi:10.1145/62212.62215
  4. Mihir Bellare and Silvio Micali. Non-Interactive Oblivious Transfer and Applications. Advances in Cryptology — CRYPTO’ 89 Proceedings, 1989. doi:10.1007/0-387-34805-0_48
  5. Yuval Ishai, Joe Kilian, Kobbi Nissim and Erez Petrank. Extending Oblivious Transfers Efficiently. Advances in Cryptology - CRYPTO 2003. doi:10.1007/978-3-540-45146-4_9