如何證明單向函式是不可逆的？
假設我們在單向函式的定義中以不同的方式定義“難以反轉”的部分：
一個函式 $ \ f : {0,1}^* \to {0,1}^* $ 如果易於計算，則稱為不可逆 $ f $ 但不存在 PPT（多項式時間）算法 $ \ A $ 這樣，對於每個字元串 $ x $ , 在輸入 $ \ (1^k; f(x)) $ , $ \ A $ 輸出 $ x’ $ 這樣 $ \ f(x) = f(x’) $ .
如何證明如果 $ \ f $ 是單向函式，則它是不可逆函式。
我知道如果 $ \ f(a,b) = a\land b $ ， 然後讓 $ x $ 輸出 $ \ f $ . 所以不能有唯一的值 $ a,b $ 使得這是可逆的。所以基本上這是不可逆的。我沒有得到 PPT 算法和不可逆函式之間的聯繫。
您的 $ f $ 在您的定義中不是不可逆的**。**如果 $ f(a,b) = 0 $ 只輸出 $ x’ = (0,0) $ 而如果 $ f(a,b) = 1 $ 輸出 $ x’=(1,1) $ . 這是一個非常有效的算法，它輸出一個 $ x’ $ 這樣 $ f(a,b) = f(x’) $ .
關鍵是數學中有一個可逆函式的概念，一般來說：這意味著對於任何圖像 $ f $ 有一個獨特的點映射到它。單向函式就是這樣一個函式，加上額外的內容，您無法有效地計算這個唯一的原像。您的 $ f(a,b) = a \land b $ 也不是單向的，因為有 3 對映射到 $ 0 $ .
$ f $ 不是不可逆的並不意味著它在這個意義上是可逆的。
具體來說：密碼學家希望/假設密碼散列函式是不可逆的（這就是我們儲存密碼散列的原因）。此外，RSA 是單向的：加密具有唯一的解密，但沒有私鑰（所謂的陷門）就無法有效計算。
從定義中可以清楚地看出單向函式是不可逆的（寫下您對單向函式的定義：它應該是立即的；如果不是，請編輯您的問題並添加該定義）。