了解 Lindell 的（半誠實的）遺忘轉移證明
在 Lindell 的教程“如何模擬它”[ 2016/046 ]，第 4.3 節中，他基於增強的陷門排列和相應的硬核謂詞，給出了一種用於不經意傳輸的半誠實協議。我不明白證明中的一些細節，希望有人能向我解釋。
他給出了以下定義： $ B $ 是陷門排列的核心謂詞 $ f_\alpha $ 如果：
對於每個非均勻 PPT 對手 $ A $ 存在一個可忽略的函式 $ \mu(n) $ 這樣對於所有人 $ n $ : $$ \Pr[A(1^n, \alpha, r) = B(\alpha, f_\alpha^{-1}(S(\alpha; r)))] \leq \frac{1}{2} + \mu(n), $$
在哪裡 $ \alpha $ 是函式集合中的索引 $ {f_ \alpha} $ 和 $ S $ 樣本（幾乎均勻地）在範圍/域中 $ f_\alpha $ .
協議 4.2 計算 OT 功能 $ ((b_0,b_1), \sigma) \mapsto (\lambda, b_\sigma) $ 如下：
- $ P_1 $ 發送索引 $ \alpha $ 活板門函式 $ f_\alpha $ ， 在哪裡 $ P_1 $ 知道活板門，但 $ P_2 $ 才不是。
- $ P_2 $ 隨機樣本 $ x_\sigma $ 和 $ y_{1-\sigma} $ , 計算 $ y_\sigma=f_\alpha(x_\sigma) $ , 並發送 $ (y_0, y_1) $ .
- $ P_1 $ 使用陷門計算 $ x_0 $ 和 $ x_1 $ ，然後發送 $ B(\alpha, x_0) \oplus b_0 $ 和 $ B(\alpha, x_1) \oplus b_1 $ .
- $ P_2 $ 計算 $ B(\alpha, x_\sigma) $ 因此可以輸出 $ b_\sigma $ .
部分安全性證明（定理 4.3）構造了一個模擬器 $ S_2 $ 為貪污黨 $ P_2 $ （收件人），通過表明如果你能區分輸出 $ S_2 $ 從那個 $ P_2 $ , 你可以用它來構造一個算法 $ A $ 這打破了假設 $ B $ 是一個硬核謂詞，總結如下：
算法 $ A $
$$ … $$收到 $ (1^n, \alpha, r) $ 用於輸入。 $ A $ 的目的是猜測 $ B(\alpha, S(\alpha; r)) $ .
但是，沒有猜測，因為您可以簡單地計算 $ B(\alpha, S(\alpha; r)) $ ， 正確的？
證明的最終方程計算 $ \Pr[A(1^n, \alpha, r) = B(\alpha, x)] $ ，但我不清楚這裡是什麼 $ x $ 在這個表達式中（前一段只提到瞭如何採樣 $ x_\sigma $ ）。鑑於核心謂詞的定義，我本來希望看到 $ f_\alpha^{-1} $ 在這部分證明中。
答案是我，不是你。證明中有錯字，確實 $ x $ 這裡提到的是 $ f^{-1}_\alpha(S(\alpha,r)) $ . 我已更改校樣並更新了 ePrint 論文。感謝您指出錯字。