1
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Mikero Apr 16 at 18:24
  • $\begingroup$ Sorry for the confusion. I was assuming $m$ independent instances of 1-out-of-k OT $\endgroup$ – mallea Apr 16 at 18:27
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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