6
$\begingroup$

Can someone explain to me how OPRF is based on OT extensions? I'm currently reading papers about private set intersection problem that uses efficient OT-based protocols based on OPRF, the link of the paper is here: https://eprint.iacr.org/2016/930.pdf.

I understand how the OT-based PSI works, and how the OPRF is used for PSI, but I’m confused in understanding how the OPRF is implicitly used in the OT-based PSI. And also in the paper's proposed protocol, I can’t see the difference (in the computational cost) in case we use only OPRF for the PSI and in case of evaluating OPRF via OT.

From what I understand in their protocol (s+b) OPRFS will be used, and from my understanding if we just used OPRF for PSI we will use almost the same number of OPRFs instances, it’ll be depending on the number of inputs. So what’s the difference?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

Construction of an "Oblivious Pseudo-Random Generator" from Oblivious Transfer

I will try to explain Section 4.3 of the paper you refer to [1]. Personally this other paper [2], which builds upon the protocol of [1], helped me a lot.

Here is the basic idea:

  • the sender and the receiver agree on hash functions $ h_i $
  • the sender creates an array $ G $ filled with random values
  • for each element $ x $ of its set $ X $, the sender XOR together the items of $ G $ which index are obtained by hashing $ y $ with the hash functions:

$$ m_{P_1}[j] = \bigoplus_i G[h_i(x_j)] $$

  • the sender sends these values (called "summary values" in [2]) to the receiver
  • The receiver, for each element $ y $ in its set $ Y $, will use OT to retrieve the cells of $ G $ corresponding to $ x $, so that he is able to compute the "summary values" for his own elements:

$$ m_{P_2}[j] = \bigoplus_i G[h_i(y_j)] $$

  • the receiver compares the summary values he got with the summary values he received to find out the intersection, that is $ y_i \in X $ if and only if $ \exists j, ~ m_{P_1}[j] = m_{P_2}[i] $.

The use of OT extensions is simply an optimization because $ G $ is quite large and "standard OT" is expensive. They also use another optimization made possible by the fact that $ G $ is filled with random, which simply put allows you not to pay for items of $ G $ you do not use.

Now where is the Oblivious Pseudo-Random Generator here? First note that this is not an Oblivious Pseudo-Random Function, it's a Generator. An OPRF must compute a well-defined, efficiently computable function. For instance in this paper [3] building an OPRF, the function is the Dodis-Yampolskiy Pseudo-Random Function:

$$ f_k(x) = g^{1/(k+x)} \text{in group $<g>$ of composite order $n$} $$

In the case of [1] and [2] we are not evaluating a "function" per se but just "spitting out" random values, which matches the definition given in [1] of a "OPRG". Actually the first time I saw the term "Oblivious Pseudo-Random Generator" was in [1] and the way they define it (second text block of Section 4.3) makes me think that they are the first to use this notion.

Maybe this is what confused you ? Because you can also build a PSI protocol using an OPRF (see [4]), but it is not what they are doing in Section 4.3 of [1].

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the plug to my paper. I would also recommend (to the original poster) to look at this one. There, we explicitly cast the OT extension tricks as an oblivious PRF. This might help identify where the OPRF is. $\endgroup$
    – Mikero
    Apr 13, 2018 at 14:18
  • $\begingroup$ @Mikero You're welcome, but now I'm confused: it seems that your definition of an OPRF in your CCS 2016 paper is different from the one of my reference [3] (Jarecki and Liu, TCC 2009). Actually your definition of "OPRF" is like the "OPRG" definition of Pinkas et al (ref [1]), am I right? $\endgroup$
    – Cédric Van Rompay
    Apr 13, 2018 at 14:38
  • 1
    $\begingroup$ It is certainly different than that of [3] for various technical reasons: functionality (not sender) determines key; keys are related between instances; receiver learns slightly more than function output. I'm not familiar with this term OPRG (which I don't see in [1]). What you call G[x] is something the sender can compute for any x, while the receiver can compute just a single G[y] . For the sender, G[x] is a function of x & its OT extension protocol view. So you can call G a PRF whose key is the sender's OT extension view. This is what we do in KKRT16 too, and yes very similar to PSZ [1]. $\endgroup$
    – Mikero
    Apr 13, 2018 at 18:36
  • $\begingroup$ @Mikero Thanks for the explanations. About "OPRG" in [1]: second text block at the beginning of Section 4.3 in the full eprint version: "We denote [...] an oblivious pseudo-random generator (OPRG), which takes as input bits b1, b2, [...]". $\endgroup$
    – Cédric Van Rompay
    Apr 16, 2018 at 9:16
  • $\begingroup$ "in this paper we consider only the case where the receiver can evaluate the PRF on a single input." Is there a way to build an OPRF out of OT in a way that allows the receiver to make many queries? $\endgroup$
    – Paul Crowley
    Aug 25, 2019 at 23:11

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.