我們如何驗證函式是否確實是單向函式？
我們如何證明加法函式 f (x, y) = x + y（其中 |x| = |y| 並且 x 和 y 被解釋為自然數）不是單向的？
我可以看到這個想法是找到任何對 x 和 y 加起來 x+y。但是我們如何確保長度相同，即 |x| = |y| ?
首先我們需要精確定義這個函式是什麼。你沒有提供足夠的細節，所以我將繼續這樣做。
功能 $ f $ 將一個偶數長度的字元串作為輸入 $ n = 2m $ . 它將每一半解釋為無符號 $ m $ 位整數，計算它們的總和，並將其作為無符號輸出 $ m+1 $ 位整數。
因此該函式僅在偶數長度的輸入上定義；但這不是問題，因為如果我們需要在所有輸入上定義一個函式，我們可以在輸入長度為奇數時刪除最後一位。
單向遊戲如下，關於安全參數 $ n = 2m $ :
- 一個字元串 $ x $ 長度 $ n $ 是統一選擇的。
- $ y = f(x) $ 被計算。
- 通過輸入呼叫對手 $ (y,1^n) $ , 並輸出一個字元串 $ x’ $ .
如果對手獲勝 $ f(x’) = y $ . 為了表明 $ f $ 不是單向的，我們必須證明有一個對手 $ A $ 和一個多項式 $ p $ 這樣對於無限多 $ n $ , $ A $ 至少有機率獲勝 $ 1/p(n) $ . 我們將建構一個對手 $ A $ 以機率獲勝 $ 1 $ 對所有人 $ n $ .
自從 $ y = f(x) $ 對於一個統一選擇的 $ x $ 長度 $ n $ ，它是兩個統一整數的和 $ {0,\dots,2^m-1} $ . 因此 $ y $ 將是一個整數 $ {0,\dots,2^{m+1}-2} $ . $ y $ 不會是均勻分佈的（想想兩個骰子的和如何更有可能是 7 而不是12），但這不是問題，因為我們的 $ A $ 將有機率獲勝 $ 1 $ 對於所有值 $ y $ .
$ A $ 工作如下。如果 $ y $ 是偶數，它輸出 $ x’ = (y/2,y/2) $ ，否則輸出 $ x’ = ((y+1)/2,(y-1)/2) $ . 在這兩種情況下，它都會對每一半進行零填充，使其具有長度 $ m $ . 很明顯，我們在每種情況下都有 $ f(x’) = y $ ，所以對手總是贏。