單向函式——如何證明？
功能 $ f $ 是一個長度縮短函式。它減少到輸入大小的日誌，即 $ |f(x)|/\log(|x|) \leq $ $ a\ positive\ constant $ . 這是單向功能嗎？
編輯： $ f $ 是任何函式。未知的定義，只有對比率的約束對所有人都是恆定的 $ x $
雖然您的問題的目前答案在技術上是正確的，但它並沒有真正回答您的問題，並且其作者添加的評論是不正確的：事實上，可以證明任何功能 $ f $ 滿足你給出的要求不可能是單向的。
讓 $ f $ 是一個函式，使得所有人 $ x $ 在其領域內， $ |f(x)|/\log(|x|) \leq c $ ， 在哪裡 $ c $ 是一些固定常數。考慮以下簡單的反演算法 $ f $ : 在任何輸入上 $ y $ , 它返回 $ x’ $ ， 在哪裡 $ x’ $ 是一個固定輸入 $ f $ ，最初是從域中隨機均勻繪製的 $ f $ .
我聲稱該算法反轉 $ f $ 在具有不可忽略機率的隨機輸入上。這是證明的草圖：讓 $ D $ 成為的領域 $ f $ ， 和 $ I $ 成為它的形象。很容易看出，隨機選擇一對輸入 $ (x_0,x_1) $ 從 $ D^2 $ , 的機率 $ f(x_0) = f(x_1) $ 下界為 $ 1/|I| $ （即，元素數量的 1 $ I $ ).
考慮一個隨機選擇的挑戰者 $ x\in D $ , 計算 $ y\gets f(x) $ , 並發送 $ y $ ; 目標是找到一個有效的原像 $ y $ 以不可忽略的機率。根據我之前的評論，如 $ x’ $ 被隨意挑選 $ D $ , 的機率 $ f(x’) = y $ 至少是 $ 1/|I| $ . 讓 $ n $ 是元素的最大尺寸 $ D $ （我們可以想到 $ n $ 作為安全參數）；然後，所有元素 $ I $ 大小為 $ c\cdot\log n $ . 因此，元素的數量 $ I $ 上界為 $ 2^{c\log n} = n^c $ ，這意味著 $ 1/|I| = 1/n^c $ 是不可忽略的，因此我們的逆變器以不可忽略的機率成功，這意味著 $ f $ 不能單向。
編輯：讓我詳細說明以下陳述：擁有的機率 $ f(x) = f(x’) $ , 繪製時 $ (x,x’) $ 隨機從域 $ f $ , 上界為 $ 1/|I| $ . 讓 $ t = |I| $ ; 讓我們考慮一個列舉 $ {y_1, \ldots, y_t} $ 的元素 $ I $ 以任何固定的順序。讓 $ p_i $ 是機率 $ f(x)=y_i $ 在隨機選擇 $ x $ . 然後，通過隨機獨立選擇 $ (x,x’) $ 從 $ D $ ， 我們有
$ \mathsf{Pr}[f(x)=f(x’)] = \sum_{i=1}^t \mathsf{Pr}[f(x)=y_i]\cdot \mathsf{Pr}[f(x’)=y_i\text{ }|\text{ } f(x)=y_i] $
$ = \sum_{i=1}^t \mathsf{Pr}[f(x)=y_i]\cdot \mathsf{Pr}[f(x’)=y_i] $ 因為事件是獨立的
$ = \sum_{i=1}^t p_i^2 $ . 我們現在得到的平方和 $ p_i $ , 受約束 $ \sum_i p_i = 1 $ , 被最小化時 $ p_i $ 都是平等的，id est $ \forall i, p_i = 1/t $ . 所以，
$ \sum_{i=1}^t p_i^2 \leq \sum_{i=1}^t 1/t^2 = 1/t $ ，這給出了所需的界限。