# 1 out of n oblivious transfer

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?

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

• 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.) ​ ​ ​ ​
– user991
Oct 21 '16 at 12:17
• @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. Oct 23 '16 at 12:45
• 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.) ​ ​ ​ ​
– user991
Oct 23 '16 at 12:59
• 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. Oct 24 '16 at 17:40