# Correctness of signle-point Oblivious PRF

In the paper Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF, Chase et al. shows that a PSI scheme can be achieved by using an oblivious PRF (OPRF). They summarized a single point OPRF protocol between a sender $$S$$ and a receiver $$R$$ that can be used to check if an element $$y_R\in Y_R$$ has an equivalent in the set $$X_S$$ as follows:

• Let $$F(\cdot)$$ pseudo-random code that produce a pseudorandom string, and $$H$$ be a Hash function
• Let $$a\cdot b$$ denotes the bitwise AND operation between $$a$$ and $$b$$, and $$a \oplus b$$ denotes the bitwise XOR operation
Sender $$S$$ Receiver $$R$$
• Sample $$s \xleftarrow{} \{0,1\}^\lambda$$
• Select and input $$y_R\in Y_R$$
• Sample $$r_0 \xleftarrow{} \{0,1\}^\lambda$$ and compute $$r_1 = F(y_R)\oplus r_0$$
• $$S$$ and $$R$$ engage in $$\lambda$$-times OT protocol in which $$S$$ is the receiver and $$R$$ is the sender. At each step $$i\in \{1,\dots,\lambda\}$$, $$S$$ sends the choice bit $$s[i]$$ to the OT, and $$R$$ sends $$r_0[i], r_1[i]$$ as inputs to the OT. The OT returns $$r_{s[i]}[i]$$ to $$S$$.

• Once the $$\lambda$$-time OT is terminated, $$S$$ sets $$q$$ as the ordered concatenation of $$r_{s[i]}[i]$$ received, i.e., $$q=r_{s[1]}[1]\mid\mid \dots \mid\mid r_{s[\lambda]}[\lambda]$$.

• $$S$$ sets $$k=(q,s)$$ and define the OPRF as: $$OPRF_k(x)=H(q\oplus[F(x).s])$$

In the video presentation of this paper, the authors said that, after the OT exchange, $$q$$ is in fact equal to: $$q=r_0 \oplus[s\cdot F(y_R)]$$. So if the input $$x$$ given to the $$OPRF$$ function is equal to $$y_R$$, we have: $$OPRF_k(y_R)=H(q\oplus[F(y_R).s]) = H(r_0\oplus[s\cdot F(y_R)] \oplus [F(y_R).s]) = H(r_0)$$

My question is the following: why after the OT protocol, $$q=r_0 \oplus[s\cdot F(y_R)]$$?

My question is the following: why after the OT protocol, $$q=r_0 \oplus[s\cdot F(y_R)]$$?
• $$s[0]=0$$: In this case the sender gets $$r_0[0]$$ back. Written differently we actually get $$r_0[0] \oplus 0\cdot F(y_R)[0]$$ (because a XOR with a zero doesn't change anything). However we're in the case of $$s[0]=0$$ so we might as well write $$r_0[0] \oplus s[0]\cdot F(y_R)[0]$$.
• $$s[0]=1$$: In this case the sender gets $$r_0[0]\oplus F(y_R)[0]$$ back. Also written differently we get $$r_0\oplus 1\cdot F(y_R)[0]$$. However we're in the case of $$s[0]=1$$ so we might as well write $$r_0[0] \oplus s[0]\cdot F(y_R)[0]$$.
As you can see in both cases we end up with $$r_0[0] \oplus s[0]\cdot F(y_R)[0]$$ on S's end. All that is left is to apply the exact same logic to the remaining bits of the OTs.