I have been studying Oblivious Transfer for my bachelor's thesis and have been surprised at the number of variations of OT.
From what I've read so far, the constructions proposed by Naor and Pinkas in "Efficient Oblivious Transfer Protocols" and "Oblivious Transfer and Polynomial Evaluation", as well as Tung Chou and Claudio Orlandi's construction proposed in "The Simplest Protocol for Oblivious Transfer", but I am not sure.
I will continue to research this topic and any feedback is appreciated.


It depends if you want many instances (like 1 million) of OT, or just a few. For a small number of OTs, I would recommend looking at our very recent paper:

McQuoid, Rosulek, Roy: Minimal Symmetric PAKE and 1-out-of-N OT from Programmable-Once Public Functions, CCS 2020.

We're not aware of other protocols whose communication is independent of $N$.

For a large number of OTs, you would use some kind of OT extension approach. The leading OT extension protocol for 1-out-of-N is:

Orrù, Orsini, Scholl: Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection, CT-RSA 2017.

  • $\begingroup$ If I reading this right, the CCS paper only gives you Random OT? In that case it depends on the application whether that's helpful, doesn't it? If i need (non-random) OT, the transformation from Random OT to OT will reintroduce a dependence on N. $\endgroup$
    – Maeher
    Oct 22 '20 at 15:36
  • $\begingroup$ Yes, you have to use the classic Beaver derandomization to get chosen-message OT. See eprint.iacr.org/2019/706 for details. Dependence on $N$ is inevitable in that case because the simulator must extract $N$ messages worth of information from the protocol transcript. $\endgroup$
    – Mikero
    Oct 22 '20 at 16:18
  • $\begingroup$ Thank you very much for your input! I really appreciate it and I will take the time to read what you've sent me! (also, the main application of OT that I will be diving into will probably be Private Set Intersection so this really helps a lot) $\endgroup$
    – robbyyt
    Oct 22 '20 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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