OWF的存在與OWP的關係
OWP 是雙射 OWF，因此每個 OWP 都是 OWF，但反之則不然。
但是，我想知道這兩種函式的*存在之間的關係是什麼。*顯然，如果假設 OWP 存在，那麼 OWF 也將存在。
但是：OWF的存在是否意味著OWP的存在？
簡短的回答：“不”。
建立原語形式語句的標準方法 $ B $ 存在然後另一個原語 $ A $ 也存在是通過一個黑盒還原。這包括兩個步驟：
- 構造實例 $ \alpha $ 的 $ A $ 給定對實例的黑盒訪問 $ \beta $ 的 $ B $ — 這表示為 $ \alpha^\beta $ ， 在哪裡 $ \beta $ 中的上標指 $ \alpha $ 只有 oracle 訪問 $ \beta $ ; 和
- 表明 $ \alpha^\beta $ 很難打破假設 $ \beta $ 是 — 這又是通過約簡算法完成的 $ \mathcal{B} $ 打破 $ \beta $ 給定一個對手 $ \mathcal{A} $ 打破 $ \alpha $ . ( $ \mathcal{B} $ 只能黑盒訪問 $ \mathcal{A} $ .)
原始 $ A $ 據說是黑盒簡化為原始的 $ B $ . （此後，減少，我們的意思是減少黑盒。）
魯迪奇展示了 $ ^* $ 在他的博士論文中，單向排列（ $ OWPs $ )不能簡化為單向函式 ( $ OWFs $ ) — 即，給定一個 $ OWF $ $ f $ , 不能構造一個 $ OWP $ $ \pi $ 以上述方式。特別是，他表明第 2 步是不可能的：即，不存在約簡算法 $ \mathcal{B} $ 打破 $ f $ 給定一個對手 $ \mathcal{A} $ 打破 $ \pi^f $ .
請注意，以上是一個非常強烈的聲明：我們正在排除所有歸約算法 $ \mathcal{B} $ . 一種方法是通過“oracle 分離”。Rudich 表明存在一個神諭 $ \mathcal{O} $ 相對於哪個 $ OWFs $ 存在，但 OWP 的任何構造 $ \pi $ 使用 $ \mathcal{O} $ 可以使用算法破解 $ \mathcal{A}^* $ 只進行“少數”（多項式多）查詢 $ \mathcal{O} $ . 神諭 $ \mathcal{O} $ 被 Rudich 選為隨機預言機，這是一種高機率的單向預言機——特別是，它需要對隨機預言機進行任何算法“許多”（近乎指數的）查詢來反轉它。的工作原理 $ \mathcal{A}^* $ 有點涉及，但高級的想法是它迭代查詢 $ \mathcal{O} $ 在“幾個”點上，它在每次迭代中都能學到新的東西。自實施以來 $ \pi $ 有效率， $ \mathcal{A}^* $ 可以成功反轉 $ \pi $ 僅使用多項式查詢 $ \mathcal{O} $ . 注意 $ \mathcal{A}^* $ 只有查詢效率高，並且只有當它可以訪問 $ \mathsf{PSPACE} $ 甲骨文。但是沒有辦法減少 $ B $ 可能會破壞 OWF ( $ \mathcal{O} $ ，即）使用 $ \mathcal{A}^* $ 因為後者只對 $ \mathcal{O} $ .
Matsuda 和 Matsuura強化了上述結果，表明 $ OWP $ 甚至不能歸約為單射 $ OWFs $ （可以說是最接近的原語 $ OWPs $ ）。該論文中的第 1.2 節包含對 Rudich 分離的更詳細（儘管仍然直覺）的解釋。
PS Oracle 分離已廣泛用於密碼學。其他一些例子是：
- 公鑰密碼學不能基於 OWF：Impagliazzo 和 Rudich
- 抗碰撞雜湊函式也不能基於 OWF：Simon
其他排除縮減的方法是所謂的“元縮減”技術和雙預言技術。 Fischlin對這些技術有很好的闡述：這應該是進一步閱讀的一個很好的起點。您可以在Trevisan、Reingold 和 Vadhan的這篇論文中閱讀有關黑盒縮減的更多資訊。
$ ^* $ Rudich 的結果是模一個猜想，後來被Kahn 等人證明。.