如何顯示不是單向函式？
可以這麼說 $ f:{0,1}^* \to {0,1}^* $ 是一個強大的單向功能。
讓 $ h(x)=f(x)||x_n $ 在哪裡 $ x_n $ 是個 $ n $ 第一點 $ x $ .
我明白那個 $ h $ 不會是強大的單向功能。但是，我希望直覺地理解為什麼會這樣。
其實證明 $ h $ 是單向的並不是那麼微不足道…首先，關於定義的提醒。一個函式 $ f $ 如果對於所有機率多項式時間對手，則（強烈）是單向的 $ A $ , 所有多項式 $ p $ 並且都足夠大 $ n $ ， 我們有
$$ \mathrm{Pr}[A(f(U_n),1^n) \in f^{-1}(U_n)] < \frac{1}{p(n)} $$ （在哪裡 $ U_n $ 表示在所有長度字元串上均勻分佈的隨機變數 $ n $ ）。換句話說，我們統一選擇一個字元串 $ x $ 長度 $ n $ , 我們計算 $ y = f(x) $ 我們跑 $ A $ 在輸入 $ (y,1^n) $ ，注意它的輸出 $ x’ $ . 然後定義表明機率 $ f(x’) = y $ 小於 $ 1/p(n) $ . 我們證明 $ h $ 是單向的矛盾。也就是說，假設 $ h $ 不是單向的，我們證明 $ f $ 不是單向的，與我們的假設相矛盾。 那麼這樣說是什麼意思 $ h $ 不是單向的。很容易看出，“所有足夠大”等價於“除了有限數之外的所有”，因此我們得到以下內容。有一個機率多項式時間算法 $ A_h $ 和一個多項式 $ p_h $ 這樣對於無限多 $ n $ 我們有
$$ \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \ge \frac{1}{p_h(n)}. $$ 我們限制對此類的關注 $ n $ . 我們將證明存在一個機率多項式時間算法 $ A_f $ 和一個多項式 $ p_f $ 這樣對於所有這樣的（無限多） $ n $ ， 我們有 $$ \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)] \ge \frac{1}{p_f(n)}. $$ $ A_f $ 工作方式如下，輸入 $ (f(U_n), 1^n) $ （也就是說，在輸入 $ (y,1^n) $ 在哪裡 $ y = f(x) $ 對於一個統一選擇的 $ x $ 長度 $ n $ ).
- 跑 $ s \gets A_h(y||0,1^n) $ . 如果 $ f(s) = y $ ， 輸出 $ s $ 並停下來。
- 跑 $ t \gets A_h(y||1,1^n) $ . 如果 $ f(t) = y $ ， 輸出 $ t $ 並停下來。
- 輸出 $ 0^n $ 並停下來。
$ A_f $ 顯然在機率多項式時間內執行，我們分析其成功機率。我們觀察到，如果最後一位 $ U_n $ 是 $ 0 $ 並呼籲 $ A_h $ 在步驟 1 中成功，然後 $ A_f $ 將會成功。同樣，如果最後一位 $ U_n $ 是 $ 1 $ 並呼籲 $ A_h $ 在第 2 步成功， $ A_f $ 成功。因此（讓 $ \mathrm{last}(X) $ 成為最後一點 $ X $ )
$$ \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0] $$ 和 $$ \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1] \ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]. $$ 現在，
$$ \begin{align*} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n)] &= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \ &\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \ &= \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \ &\quad {}+{} \mathrm{Pr}[A_f(f(U_n),1^n) \in f^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \ &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 0]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 0] \ &\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \mid \mathrm{last}(U_n) = 1]\cdot \mathrm{Pr}[\mathrm{last}(U_n) = 1] \ &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 0] \ &\quad {}+{} \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n) \wedge \mathrm{last}(U_n) = 1] \ &\ge \mathrm{Pr}[A_h(h(U_n),1^n) \in h^{-1}(U_n)] \ &\ge \frac{1}{p_h(n)}. \end{align*} $$
實際上， $ h(x) $ 是單向的。可能讓你的直覺感到困惑的是，單向函式的定義是對由下式索引的整個函式族的漸近陳述 $ n $ .
證明（scetch）：
假設 $ h(x) $ 不是單向的。這意味著，存在一個算法 $ A $ ，對於統一選擇 $ x $ 計算原像 $ x_0 $ 至 $ h(x) = y | x_n $ 以不可忽略的機率。
自從 $ f(x_0) = y $ , 算法 $ A $ 還計算原像 $ f(x) $ 以不可忽略的機率。這與以下假設相矛盾 $ f $ 是單向的。這反過來說，非單向假設 $ h $ 是錯的。
qed。