The constructions of 1-out-of-$n$ OT for $l$-bit strings I've seen had communication complexity proportional to $nl$. I wonder, is it possible to do OT with active security and transfer less than $O(nl)$ bits (I'm ignoring the security parameter in $O$-notation here)? The important part for me here is making it cheaper than just transfering sender's input to the receiver.

Is there some inherent limitation that doesn't allow this kind of OT to transfer less bits than the sender's input? Are there any communication lower bounds for this?

  • $\begingroup$ I don't think so. There is a lower bound on PIR which says you can't get below the input size in terms of communication (basically, the sender's messages have to have as much entropy as the full input due to security), and I would expect this to work for 1-out-of-$n$ OT as well $\endgroup$
    – Daniel
    Dec 5, 2021 at 21:40
  • $\begingroup$ The PIR lower bound says that the sender's computation must “touch” all the bits of the database, but I don't think (correct me if I'm wrong) it requires the sender's response to be as big. Also, PIR lower bound holds for a generic case when you want compute any function (database), but it doesn't prohibit improving the bound in some special cases like OT where the database has a lot of structure. $\endgroup$
    – Ivan
    Dec 5, 2021 at 21:52
  • $\begingroup$ I think the lower bound is for communication as well (see e.g. Lemma 5 in ia.cr/2019/220). I'm not sure what you mean about the database having certain structure like in OT. $\endgroup$
    – Daniel
    Dec 5, 2021 at 22:15
  • $\begingroup$ About structure in PIR: imagine that my database of n bits contains 0 in every position. Clearly, the queries to it can be evaluated using less than n bits of communication (0 bits, in fact). This demonstrates that for some specific databases you can do PIR in less than n bits (and the lower bound you mentioned does not prohibit this, because it's stated for the general case). $\endgroup$
    – Ivan
    Dec 5, 2021 at 23:07
  • $\begingroup$ Your link is about unconditionally secure MPC, its lower bounds do not apply to computationally secure OT (which I'm talking about) and PIR. $\endgroup$
    – Ivan
    Dec 5, 2021 at 23:12

2 Answers 2


Suppose the sender has strings $x_1, \ldots, x_n$, each of length $\ell$. The receiver has a choice $y \in \{1, \ldots, n\}$ and wants to learn (only) $x_y$. The protocol can proceed as follows:

  • Receiver generates a key $k$ for a symmetric-key fully homomorphic encryption scheme.
  • Receiver sends $c = \textsf{Enc}(k,y)$.
  • Sender imagines a boolean circuit $f$ for the function $y \mapsto x_y$ -- this circuit has all of the $x_i$ values built in.
  • Sender uses the homomorphic evaluation feature to locally compute $c' = \textsf{Enc}(k,f(y))$.
  • Sender sends $c'$.
  • Receiver decrypts to obtain $f(y) = x_y$.

Only two ciphertexts (each encrypting an $\ell$-bit string) are sent, so this can cost $O(\kappa)+2\ell$ bits for a suitable FHE scheme. Note: you need an encryption scheme that is circuit-private -- i.e., $c'$ should reveal no more than $f(y)$, even to the key holder.

This protocol is secure against semi-honest adversaries, but there are ways to extend it to malicious security as well.


To complement Mikero's answer:

  • If you want 1-out-of-$N$ OT on chosen input bits, known methods to get $o(N)$ communication build upon the work on sublinear private information retrieval. Most solutions rely on fully homomorphic encryption, as in Mikero's answer. However, there exists also various alternative constructions under other cryptographic assumptions, such as DCR (through the Damgård-Jurik cryptosystem), or DDH and QR (using trapdoor hash functions).
  • If you want 1-out-of-$N$ pseudorandom OT (i.e. the $N$ sender inputs are the output of some pseudorandom function), then there are alternative, more efficient solutions under variants of the LPN assumption, see e.g. this work.
  • There exists (many) constructions of zero-knowledge proofs of knowledge with sublinear communication in the witness size. If you want them non-interactive, you need strong assumptions (the random oracle model, or SNARGs) but if you are fine with interactions, they exist from assumptions as simple as the existence of collision resistant hash functions (e.g. here). You can use any such proof system in a generic way to transform a semi-honest OT (such as the one in Mikero's answer) into a scheme with active security.
  • If you only want to do 1-out-of-$N$ with communication less than the database size, this is known to be possible (albeit the communication will be only slightly less) under generic assumptions: the existence of trapdoor permutations (see here). For active security, you'll need CRHFs on top of that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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