# Communication cost of Oblivious Transfer and OT Extension?

Suppose there exist fixed K set of N-bit strings. Here, sender and receiver perform 1-out-of-K OT either once or many times. In the latter case, we may use OT Extension.

What is the order of the communication cost of Single base-OT and OT Extension??

1. If we do a single 1-out-of-$$K$$ OT, is the communication cost $$O(N)$$ or $$O(KN)$$?

2. If we do OT extension to invoke $$m$$ independent 1-out-of-K OTs, is the communication cost $$O(mN)$$ or $$O(mKN)$$?

Best,

• What do you mean by "retrieve m messages?" One instance of m-out-of-k OT, or m independent instances of 1-out-of-k OT (or something else)? – Mikero Apr 16 '19 at 18:24
• Sorry for the confusion. I was assuming $m$ independent instances of 1-out-of-k OT – mallea Apr 16 '19 at 18:27

With the most standard approaches, the cost of performing $$m$$ $$1$$-out-of-$$n$$ oblivious transfers of strings of length $$\ell$$ with security parameter $$\lambda$$ is $$O(m(\lambda + n\ell))$$ (see e.g. this paper, Section 5.3). Use $$m=1$$ above to have the asymptotic cost for a singe OT. Note that this can be improved in various settings - e.g., it can be typically much less if all you need is are random OTs (where the selection bits and the transmitted strings are random). We can also get some savings when $$\ell$$ is very small (constant) and $$n$$ is not too big as well - for example, $$1$$-out-of-$$2$$ OT of length-$$1$$ secrets can be done with communication $$O(\lambda/\log \lambda)$$ with the same paper.

One can further improve this cost, at least in theory. Typically, it is theoretically feasible to perform $$m$$ $$1$$-out-of-$$n$$ oblivious transfers of strings of length $$\ell$$ with security parameter $$\lambda$$ using communication $$O(m n\ell)$$, under standard assumptions (e.g. under the DDH assumption, with a constant $$4+o(1)$$ in the $$O()$$ when $$m$$ is sufficiently large, using this paper - note although that this is not concretely practical)