3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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