單點不經意PRF的正確性
在論文Private Set Intersection in Internet Setting From Lightweight Oblivious PRF中，Chase*等人。*表明可以通過使用不經意的 PRF (OPRF) 來實現 PSI 方案。他們總結了發送者之間的單點 OPRF 協議 $ S $ 和一個接收器 $ R $ 可用於檢查元素是否 $ y_R\in Y_R $ 在集合中有一個等價物 $ X_S $ 如下：
讓 $ F(\cdot) $ 產生偽隨機字元串的偽隨機程式碼，以及 $ H $ 是一個雜湊函式
讓 $ a\cdot b $ 表示之間的按位與運算 $ a $ 和 $ b $ ， 和 $ a \oplus b $ 表示按位異或運算
$ S $ 和 $ R $ 加入，參與 $ \lambda $ -times OT 協議，其中 $ S $ 是接收者並且 $ R $ 是發件人。在每一步 $ i\in {1,\dots,\lambda} $ , $ S $ 發送選擇位 $ s[i] $ 到舊約，和 $ R $ 發送 $ r_0[i], r_1[i] $ 作為 OT 的輸入。舊約回歸 $ r_{s[i]}[i] $ 至 $ S $ .
一旦 $ \lambda $ -時間 OT 終止， $ S $ 套 $ q $ 作為的有序連接 $ r_{s[i]}[i] $ 收到，即 $ q=r_{s[1]}[1]\mid\mid \dots \mid\mid r_{s[\lambda]}[\lambda] $ .
$ S $ 套 $ k=(q,s) $ 並將 OPRF 定義為：$$ OPRF_k(x)=H(q\oplus[F(x).s]) $$
在本文的影片展示中，作者表示，在 OT 交流之後， $ q $ 實際上等於： $ q=r_0 \oplus[s\cdot F(y_R)] $ . 所以如果輸入 $ x $ 給予 $ OPRF $ 函式等於 $ y_R $ ， 我們有：$$ 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) $$
我的問題如下：為什麼在 OT 協議之後， $ q=r_0 \oplus[s\cdot F(y_R)] $ ?
我的問題如下：為什麼在 OT 協議之後， $ q=r_0 \oplus[s\cdot F(y_R)] $ ?
讓我們從 OT 的第一位的區分開始：
- $ s[0]=0 $ ：在這種情況下，發件人得到 $ r_0[0] $ 背部。寫得不同，我們實際上得到 $ r_0[0] \oplus 0\cdot F(y_R)[0] $ （因為帶零的 XOR 不會改變任何東西）。但是，我們的情況是 $ s[0]=0 $ 所以我們不妨寫 $ r_0[0] \oplus s[0]\cdot F(y_R)[0] $ .
- $ s[0]=1 $ ：在這種情況下，發件人得到 $ r_0[0]\oplus F(y_R)[0] $ 背部。我們也得到了不同的寫法 $ r_0\oplus 1\cdot F(y_R)[0] $ . 但是，我們的情況是 $ s[0]=1 $ 所以我們不妨寫 $ r_0[0] \oplus s[0]\cdot F(y_R)[0] $ .
正如你在這兩種情況下看到的，我們最終得到 $ r_0[0] \oplus s[0]\cdot F(y_R)[0] $ 在S端。剩下的就是對 OT 的剩餘位應用完全相同的邏輯。