I am thinking about this problem:

The server has a two-column table $T=\{c_1,c_2\}$. A user has a query $q$ that is sent to server. The server find an item $x$ in the first column satisfying $x=q$ and return the item $y$ in the second column to the user ($x$ and $y$ are in the same row).

The requirements are that:

  1. server should not learn $q$.

  2. user should not learn other items besides $y$.

The above scenario is quite similar to those in Oblivious Transfer or Private Information Retrieval. However, there is a slight difference (to my understanding). The user does not know which item he wants to retrieve in advance. The index of the item to be retrieved is obtained by comparison with the items in the first column.

So, my questions are

  1. how to modify OT or PIR protocols to fit with this situation?

  2. What's the most efficient OT or PIR protocol (in terms of communication efficiency) to deal with this situation?

  3. Are there any other ideas besides OT or PIR?



1 Answer 1


Kolesnikov & Kumaresan defined a primitive called "string select OT" which basically covers your setting but with a database of 2 items. Sender has $x^1, y^1, x^2, y^2$. Receiver has $x^*$. If $x^* = x^i$ then the receiver learns the corresponding $y^i$.

I think a generalization of their protocol would work, at the cost of $n$ 1-out-of-2 string OTs where $n$ is the number of bits in the $x$ values.

  • Parties do $n$ instances of string OTs on random strings $(m_0^1, m_1^1), (m_0^2, m_0^2), \ldots$ The receiver uses the bits of $x^*$ as his choice bits.

  • For an $n$-bit value $x$, sender defines $K_x = H( \bigoplus_i m_{x[i]}^i )$ where $H$ is a random oracle. The thing inside $H$ is the XOR of the things that the receiver would get if his choice bits were $x$. (the hash is there to kill the correlations among the different $K_x$ values)

  • For every $(x^i, y^i)$ in the database, sender sends gives $\textsf{Enc}(K_{x^i}, y^i)$. (assume it is an authenticated encryption, so you know when you have successfully decrypted)

  • Receiver can decrypt exactly one of these ciphertexts, and learn $y^i$.

Vladimir Kolesnikov, Ranjit Kumaresan: Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. SCN 2012: 205-221

edit: Here is another approach, using ideas from one of my papers. The paper only needs this functionality for database of size 2, but I think it would generalize as well. (we refer to this subprotocol as PFE of a universal hash function).

  • Parties do an MPC where receiver inputs $x^*$, sender inputs randomly chosen $a$ and $b$ from a large field. Receiver learns $ax^* + b$. Think of this as evaluating a private a 2-universal hash function. It has the property that even given $ax^*+b$, any other $ax'+b$ value is uniformly distributed.

  • Sender sends $\textsf{Enc}( H(ax^i+b), y_i)$ for each $(x^i, y^i)$ pair in the database. Receiver can decrypt exactly one of them.

Zhangxiang Hu, Payman Mohassel, Mike Rosulek: Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost. CRYPTO (2) 2015: 150-169

  • $\begingroup$ Thanks for your answer. I just briefly read the article you mentioned. It seems that it utilized each bit in the selection string as an index for each share . Then repeat 1-out-of-2 OT $k^\prime$ times ( $k^\prime$ is the bit length of the selection string). In this way, the communication overhead should be very high. Do you have some other references for "string selection OT"? $\endgroup$
    – Paradox
    Commented Sep 27, 2015 at 20:32
  • $\begingroup$ There is a paper of mine that uses something like SSOT, again for just 2 items but it seems like it might generalize. These are the only two papers I know that have done anything with this SSOT primitive. I have updated my response accordingly. These papers are aiming for simulation-based security against active or covert adversaries, so the communication can never be sublinear (the simulator has to extract the database/input of a corrupt sender). I'm afraid I don't know the PIR literature well enough to comment about using PIR techniques here. $\endgroup$
    – Mikero
    Commented Sep 27, 2015 at 22:24

Your Answer

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

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