So I read some stuff about oblivious transfer and came a ross that 1 out of 2 OT can be used as a black box to build 1 out of n OT. At first it seemed trivial just feeding in 4 messages and 2 chooser bits but then I realized it's not that trivial since it doesn't guarantee security. How is 1 out of 2 OT used to build 1 out of 4 OT if we can use 1 out of 2 OT as a black box?


1 Answer 1


The sender chooses log n pairs of secret keys (say, for encryption). Then, each number between 1 and n is naturally associated with a subset of exactly log n keys. The protocol then works by running log n 1-out-of-2 OTs where the receiver asks for the keys that are associated with its input (number between 1 and n). Finally, the sender encrypts each of the n messages with the subset of keys associated with the number (using encryption so that without all keys nothing is learned).

It is not difficult to formally prove the security of this using simulation (as long as the OT is secure for malicious adversaries, this is also secure for malicious adversaries).

This solution goes back to a paper by Benny Pinkas [1].

[1] Moni Naor and Benny Pinkas. 1999. Oblivious transfer and polynomial evaluation. In Proceedings of the thirty-first annual ACM symposium on Theory of Computing (STOC '99). Association for Computing Machinery, New York, NY, USA, 245–254. DOI:https://doi.org/10.1145/301250.301312

  • $\begingroup$ However, if L is the minimum length over the n messages, then it's significantly harder when the 1-out-of-2 OTs must be for strings of less than L$\cdot$n/2 bits. ​ (I don't know of any nice way of handling that restriction.) ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Oct 21, 2016 at 12:17
  • $\begingroup$ @RickyDemer Sorry; I didn't understand what problem you are referring to. The 1-out-of-2 OTs I am referring to are for strings of length $n$ where $n$ is the security parameter (for transferring keys). If you are asking what can be done with lower communication complexity, then I agree; this is an interesting problem. $\endgroup$ Commented Oct 23, 2016 at 12:45
  • $\begingroup$ I was referring to preserving whatever information-theoretic security the original OTs have, when the 1-out-of-2 OTs can only be used to transfer not-too-long strings. ​ (In fact, my previous comment also applies to just preserving information-theoretic privacy for the sender, with the same limitation on the 1-out-of-2 OTs.) ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Oct 23, 2016 at 12:59
  • 1
    $\begingroup$ Yes; the solution I gave is only computational. I don't know if there is an information-theoretic solution that is better than the naive you mentioned in the comment. $\endgroup$ Commented Oct 24, 2016 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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