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