在證明弱 OWF 意味著強 OWF 的過程中，為什麼必須將是是y隨機？
當證明弱 OWF 意味著強 OWF 的存在時，標準構造通過連接弱 OWF 的幾個應用程序來進行（例如，參見此處）。也就是說，給定一個弱 OWF $ f $ ，下面是強OWF： $$ F(x_1, \dots, x_t) = (f(x_1), \dots, f(x_t)) $$ 在哪裡 $ |x_i| = n $ , $ t = n p(n) $ ， 和 $ p \in \text{poly}(n) $ 這樣 $$ \text{P}_{x \in {0,1}^n}(A(f(x), 1^n) \in f^{-1}(f(x))) < 1 - \frac{1}{p(n)} $$ 每張PPT $ A $ .
證明是通過一個可還原性論證，其中假設有一個 PPT $ B $ 哪個反轉 $ F $ 具有不可忽略的機率（即， $ F $ 單向不強）然後構造一個PPT $ A $ 反轉弱 OWF $ f $ 機率大於 $ 1 - \frac{1}{p(n)} $ .
我見過的大多數版本的構造（*）如下： $ A $ 接收輸入 $ y = f(x) $ 和 $ 1^n $ ， 在哪裡 $ x \in {0,1}^n $ 被統一採摘（但不透露給 $ A $ ). $ A $ 然後挑選 $ i \in {1, \dots, t } $ 和 $ x_j \in {0,1}^n $ 均勻地為 $ j \neq i $ 並執行 $ B $ 上 $ Y = (f(x_1), \dots, f(x_{i-1}), y, f(x_{i+1}), \dots, f(x_t)) $ ，因此（具有不可忽略的機率）反轉 $ y $ . 如果 $ B $ 不產生原像，該過程重複一定次數。
我的問題是：為什麼必須 $ y $ 處於隨機位置 $ Y $ ? 為什麼不能，例如， $ i = 1 $ 修復？畢竟， $ y = f(x) $ 和 $ x $ 保證被統一採摘（就像其他 $ x_j $ ).
這裡的這些講義暗示這是為了“平衡機率”，不幸的是，這對我來說太模糊了，無法理解。
(*) 我還在 Oded Goldreich 的“Computational Complexity: A Conceptual Perspective”中找到了另一種結構，其中 $ A $ 不挑 $ i $ 隨機; 相反，它迭代每個可能的值 $ i $ . 但是，我可以看到兩者是如何等價的。
正如你所寫，證明是通過減少任何對手 $ B $ 反轉 $ F $ 具有不可忽略的機率 $ \varepsilon(n) $ 變成對手 $ A $ 反轉 $ f $ 至少有機率 $ 1-1/p(n) \approx 1 $ .
為簡單起見假設 $ f $ 是一個單射函式。考慮潛在的對手 $ B $ 內部工作如下：給定 $ Y=(y_1, \ldots, y_t) $ ，它檢查是否 $ y_1 $ 屬於某個“特殊” $ \varepsilon(n) $ - 圖像的一部分 $ f({0,1}^n) $ . 如果是，它計算並輸出原像 $ X = F^{-1}(Y) $ . 否則，它什麼也不輸出，即它不能反轉這個 $ Y $ . 顯然，這 $ B $ 滿足上述假設，因為 $ y_1 $ 有一個 $ \varepsilon(n) $ 進入“特殊”集合的機率。（如何 $ B $ 支票 $ y_1 $ 和反轉 $ F $ 不重要，因為減少處理 $ B $ 作為“方塊盒”。所以我們可以想到 $ B $ 就像使用無界計算來執行這些步驟一樣。）
現在，考慮減少 $ A $ 按照您的建議工作，始終“插入”其外部挑戰 $ y=f(x) $ 在第一個位置，讓 $ y_1=y $ ，並選擇其餘的 $ Y $ 本身。清楚地， $ B $ 輸出原像 $ F^{-1}(Y) $ 當且僅當 $ y $ 屬於“特殊”集合，機率發生 $ \varepsilon(n) $ . 所以， $ A $ 成功輸出原像 $ f^{-1}(y) $ 以相同的機率 $ \varepsilon(n) $ . 但這還不夠：我們需要 $ A $ 以更大的機率成功 $ 1-1/p(n) $ .
如果 $ A $ 多次重複它的過程，總是讓 $ y_1=y $ 但改變另一個 $ y_i $ ，成功的機率不會提高：是否 $ B $ 倒置 $ Y $ 與否僅取決於 $ y_1=y $ ，這不會改變。（記住， $ A $ 僅獲得一個挑戰值 $ y $ 並且需要以高機率反轉它。）
正確的歸約和證明通過證明必須存在某個位置來規避這個問題 $ i $ 有很大的 $ 1-1/p(n) $ 的分數 $ y_i $ 這樣，如果我們選擇另一個 $ y_j = f(x_j) $ 如所描述的那樣隨機，然後 $ B $ 倒置 $ Y $ 具有不可忽略的機率（在選擇 $ y_j $ 獨自的）。通過這樣的猜測 $ i $ 隨機（或列舉所有）並多次重複核心過程，我們可以確保高機率 $ B $ 實際上倒置其中之一 $ Y $ 我們提供它，從而告訴 $ A $ 的原像 $ y $ . （實際證明不依賴於 $ f $ 是內射的。）