證明一個函式是不可逆的（單向函式）
我在證明單向函式（https://crypto.stackexchange.com/tags/one-way-function/info）是否難以反轉時遇到問題。
$ 2^\sqrt {m} $ 單向函式 $ f: {0, 1}^{2m} \to {0,1}^{2m} $
和 $ g(x) = f(0…0^m || x_1, x_2, \ldots, x_m) $ $ g: {0, 1}^{m} \to {0,1}^{2m} $ （|| 在這裡表示連接）。函式 g 是單向的嗎？關於它的安全性可以說些什麼？
我想你可以證明 $ g $ 下面的反例不保證是單向的。先讓 $ S $ 是所有字元串的集合 $ {0,1}^{2m} $ 開始於 $ m $ 零。參加任何 OWF $ f $ 你描述的類型。考慮函式 $ f’ $ 這與 $ f $ 除了所有輸入 $ x \in S $ 它充當身份功能。即所有人 $ x \in S $ 我們有 $ f’(x) = x $ . 現在如果你使用 $ f’ $ 構造 $ g $ 然後 $ g $ 顯然不會是單向的（因為這意味著 $ g $ 只是恆等函式）。所以你需要證明的是 $ f’ $ 仍然是OWF。
現在我草擬一個論點 $ f’ $ 實際上是一個OWF。自從 $ f’ $ 只改變輸出 $ f $ 在可忽略不計的投入量上，產出的分佈 $ f’ $ 和 $ f $ 在均勻隨機輸入上應該在統計上無法區分。但是，如果存在對手 $ A $ 這表明 $ f’ $ 不是 OWF，那麼該對手將作為兩個輸出分佈之間的區分器。因此， $ ~f’ $ 必須是 OWF。
我不確定這是否 100% 防水，因此您可能需要自己完成證明 :)。
作業就是這樣。基本上，要求 OP 做的是表明 $ g: {0, 1}^{m} \to {0,1}^{2m} $ 是或不是 $ 2^\sqrt {m} $ -單向功能。
或者換句話說 adversary 反相函式的時間成功率 $ g $ 好於/差於 $ 2^\sqrt {m} $
E：所以我們基本上有兩個任務。首先，我們必須確定對手破壞原始的平均成功機率有多大。其次，我們必須確定最壞情況的時間界限。
對我來說，最壞情況的時間限制似乎是 $ O(m) $ ， 因為 $ g $ 連接零 $ m $ 次到 $ x $ . 因此，如果對手破壞原語的成功機率為 1 ( $ A $ 總是反轉 $ g $ 在某個時間），那麼時間成功率肯定小於 $ 2^\sqrt {m} $ .
如我錯了請糾正我..…