Correctness of signle-point Oblivious PRF

Question

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)]$?

Answer 1

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

Let's start with a case-distinction on the first bit of the OTs:

• $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.