沒有核心位的 OWF 中的機率放大
我們知道OWF $ f $ 這樣它的所有位都不是核心存在。我們還知道，給定一個以不可忽略的機率解決問題的算法，我們可以重複多次並獲得大部分答案。現在，預測 $ x $ 給定 $ f(x) $ ，我們定義預測變數 $ P_i $ 為了 $ i $ ∈ $ [1..n] $ ， 在哪裡 $ P_i $ 預測 $ i $ 第一點 $ x $ 以不可忽略的機率。我們想通過執行來猜測所有 n 位 $ P_1…..P_n $ 每次幾次，並為每一位佔多數。
我想知道這是否與定義相矛盾 $ f $ ?
不，它沒有。
如果你正式寫下你的建議，你建議的方法就會出現問題：你想重複每個預測變數很多次，並評估他們的預測中的大多數。但是，隨機性必須取代輸入的隨機選擇。當對所有輸入進行平均時，您的預測器給出了大約好的答案 $ f $ . 這意味著無法實施您為固定輸入建議的策略 $ x $ .
本質上，您可以想像一個 OWF，其中每個 $ i $ th 位預測器將為不可忽略的輸入部分（例如，某個子集）給出一個很好的答案 $ S_i $ 的領域 $ f $ )，但這並不意味著來自 $ S_i $ 是其他預測變數將給出良好結果的輸入。
這是一個快速反例：假設我們有一個保持長度的 OWF $ g $ , 帶域 $ {0,1}^n $ ，其輸出是均勻分佈的。您可以使用 PRG 輕鬆建構這樣的函式，而 PRG 又可以基於任何 OWF。現在，讓 $ f $ 定義如下：考慮位串的自然排序 $ {0,1}^n $ , 並將域劃分為 $ n $ 塊 $ (B_1, \ldots, B_n) $ , 每個包含 $ 2^n/n $ 字元串。輸入時 $ x $ ，我們定義 $ f(x) $ 是通過替換獲得的值 $ i $ 第一點 $ g(x) $ 經過 $ 0 $ 如果 $ i $ 第一點 $ x $ 是 $ 0 $ ， 在哪裡 $ i $ 是塊的索引 $ B_i $ 那 $ x $ 屬於。
我聲稱 $ f $ 是單向的，如果 $ g $ 是。原因如下：在挑戰中 $ y $ ，給定對算法的訪問權 $ A $ 反轉 $ g $ 以不可忽略的機率，呼叫 $ A $ 在所有價值觀上 $ (y_0,\ldots,y_n) $ ， 在哪裡 $ y_i $ 是通過替換獲得 $ i $ 第一點 $ y $ 經過 $ 1 $ （和 $ y_0 $ 只是 $ y $ ）。收貨時 $ A $ 第一個答案 $ (x_0,\ldots,x_n) $ ， 評估 $ f $ 上 $ (x_0,\ldots,x_n) $ ; 如果其中一項評估（例如，在 $ x_i $ ) 返回 $ y $ , 停止並返回 $ x_i $ ; 否則，返回 $ \bot $ . 作為其中之一 $ y_i $ 正是正確的輸出 $ g $ 在原像上 $ y $ 經過 $ f $ ，不難看出，成功反演的機率就是 $ A $ .
我聲稱有預測器 $ P_i $ 預測 $ i $ 第一點 $ x $ 以不可忽略的機率。 $ P_i $ 簡單地工作如下：在輸入 $ y $ ，返回 $ i $ 第一點 $ y $ . 為什麼它有效？因為一個隨機輸入屬於 $ B_i $ 並且有他的 $ i $ 位等於 $ 0 $ 有機率 $ 1/2n $ , 在這種情況下 $ i $ 輸出的第 th 位是 $ 0 $ 並且預測器總是成功的。否則，該 $ i $ 第 th 位是均勻分佈的，並且預測器以機率成功 $ 1/2 $ ，因此它總體上具有不可忽略的成功機率。