有人能解釋一下 OPRF（Oblivious 偽隨機函式）是如何基於 OT（Oblivious Transfer）的嗎？
有人可以向我解釋一下 OPRF 是如何基於 OT 擴展的嗎？我目前正在閱讀有關使用基於 OPRF 的高效 OT 協議的私有集合交集問題的論文，論文的連結在這裡：https ://eprint.iacr.org/2016/930.pdf 。
我了解基於 OT 的 PSI 是如何工作的，以及如何將 OPRF 用於 PSI，但我對如何在基於 OT 的 PSI 中隱式使用 OPRF 感到困惑。而且在論文提出的協議中，如果我們僅將 OPRF 用於 PSI 和通過 OT 評估 OPRF，我看不出差異（計算成本）。
根據我在他們的協議 (s+b) 中的理解，將使用 OPRFS，並且根據我的理解，如果我們只是將 OPRF 用於 PSI，我們將使用幾乎相同數量的 OPRFs 實例，這取決於輸入的數量。那麼有什麼區別呢？
從 Oblivious Transfer 建構“Oblivious Pseudo-Random Generator”
我將嘗試解釋您參考的論文的第 4.3 節 [ 1 ]。就個人而言，另一篇論文 [ 2 ] 建立在 [ 1 ] 的協議之上，對我幫助很大。
這是基本思想：
- 發送者和接收者就雜湊函式達成一致 $ h_i $
- 發件人創建一個數組 $ G $ 填充隨機值
- 對於每個元素 $ x $ 它的集合 $ X $ , 發送者 XOR 在一起的項目 $ G $ 哪個索引是通過散列得到的 $ y $ 使用雜湊函式：
$$ m_{P_1}[j] = \bigoplus_i G[h_i(x_j)] $$
- 發送方將這些值（在 [ 2 ]中稱為*“匯總值” ）發送給接收方*
- 接收器，對於每個元素 $ y $ 在它的集合中 $ Y $ , 將使用 OT 來檢索 $ G $ 對應於 $ x $ ，以便他能夠為自己的元素計算“匯總值”：
$$ m_{P_2}[j] = \bigoplus_i G[h_i(y_j)] $$
- 接收者將他得到的匯總值與他收到的匯總值進行比較以找出交集，即 $ y_i \in X $ 當且僅當 $ \exists j, ~ m_{P_1}[j] = m_{P_2}[i] $ .
使用 OT擴展只是一種優化，因為 $ G $ 相當大，“標準OT”很貴。他們還使用了另一種優化，因為 $ G $ 充滿隨機性，簡單地說就是讓你不用為物品買單 $ G $ 你不使用。
現在不經意的偽隨機生成器在哪裡？首先請注意，這不是 Oblivious Pseudo-Random Function，而是Generator。OPRF 必須計算一個定義明確、可高效計算的函式。例如在本文 [ 3 ] 建構一個OPRF中，該函式是 Dodis-Yampolskiy Pseudo-Random Function：
$$ f_k(x) = g^{1/(k+x)} \text{in group $<g>$ of composite order $n$} $$ 在 [ 1 ] 和 [ 2 ] 的情況下，我們不是在評估“函式”本身，而只是“吐出”隨機值，這與“OPRG”的 [1 ] 中給出的定義相匹配。實際上，我第一次看到術語“Oblivious Pseudo-Random Generator”是在 [ 1 ] 中，他們定義它的方式（第 4.3 節的第二個文本塊）讓我認為他們是第一個使用這個概念的人。
也許這就是讓你困惑的地方？[因為您也可以使用 OPRF（參見 4 ]）建構 PSI 協議，但這不是他們在 [ 1 ] 的第 4.3 節中所做的。