Can someone explain how OPRF (Oblivious pseudo-Random Function) is based on OT (Oblivious Transfer)? 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?
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 $&lt;g&gt;$ 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].