Is it possible to construct a 1-out-of-N OT with communication complexity smaller than the sender's whole input?

Question

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?

Answer 1

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.

Answer 2

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.