Score:4

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

in flag

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?

Daniel avatar
ru flag
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
Ivan avatar
in flag
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.
Daniel avatar
ru flag
I think the lower bound is for communication as well (see e.g. Lemma 5 in https://ia.cr/2019/220). I'm not sure what you mean about the database having certain structure like in OT.
Ivan avatar
in flag
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).
Ivan avatar
in flag
Your link is about unconditionally secure MPC, its lower bounds do not apply to computationally secure OT (which I'm talking about) and PIR.
Score:1
us flag

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.

Score:1
cn flag

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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.