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??


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


Best,
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)