可以從單向函式構造單向排列嗎？
我們可以構造各種對稱密鑰原語，如 PRG、PRF、SPRP 等，假設存在單向排列或單向函式，前一種假設允許更簡單的構造。
但是，單向排列和單向函式之間的關係是什麼？顯然，單向排列的存在意味著單向函式的存在。反過來是真的嗎？如果不是，那麼假設單向排列比假設單向函式強。
Rudich 在他的博士論文中展示了這一點
$$ R $$在黑盒約簡的框架中，不可能從單向函式 (OWF) 構造單向排列 (OWP) 。 $ ^1 $ 後來松田和松浦加強了這一點$$ MM $$，他排除了單射 OWF（其結構比 OWF 更結構化）的 OWP 的黑盒構造，甚至擴展了一位。所以，是的，假設 OWP 比假設 OWF（或 iOWF）嚴格更強。 兩種結果中採用的技術稱為oracle 分離。這個想法是建構一個相對於 OWF（或 iOWF）存在的預言機，但是任何單向排列的黑盒構造都被打破了。可以在此執行緒上找到 Rudich 論點的概述。
但正如 Maeher 指出的那樣，仍然可能存在來自 OWF 的 OWP 的非黑盒結構。例如，我們知道在給定不可區分性混淆 (IO) 的情況下，可以從 OWF 建構（甚至是陷門）OWP
$$ BPW $$. $ ^2 $ 我相信沒有 IO 的建設仍然是開放的。 您可以在此處閱讀有關縮減的不同概念的更多資訊，在此處閱讀有關黑盒分離的資訊以及其中的參考資料。
$ ^1 $ 這是一個猜想，後來被卡恩等人證明。
$$ KSS $$. $ ^2 $ 已經嘗試從單向函式（例如，
$$ DS $$)，但我不確定它們中的任何一個是否擴展到 OWP。 $$ BPW $$Bitanksy、Paneth 和 Wichs，《混沌邊緣的完美結構》，TCC 2016 $$ DS $$Dachmann-Soled，走向公鑰加密和單向函式的非黑盒分離 $$ KSS $$Kahn、Saks 和 Smyth，Reimer 不等式的雙重版本和$$ enter link description here $$5 Rudich 猜想的證明，CoCo 2000 $$ MM $$Matsuda 和 Matsuura，關於內射單向函式之間的黑盒分離，TCC 2011 $$ R $$Rudich，單向函式可證明結果的限制，博士論文