單向函式定義
我不明白為什麼單向函式 $ f $ 是這樣定義的
$ \text{Pr}(f(A(f(x))) = f(x)) < \frac{1}{p(n)} $
並不是
$ \text{Pr}(A(f(x)) = x) < \frac{1}{p(n)} $
在哪裡 $ A $ 是一種隨機算法。
區別在哪裡？第二個更弱嗎？
這兩個條件確實代表了不同的東西。考慮一個函式，給定一個 $ n $ -位輸入，返回 $ n $ 零。這顯然符合第二個定義（如果你有 $ n $ 零，隨機算法只有一個 $ 1/2^n $ 猜測輸入的機會，因為任何 $ n $ -bit 輸入返回該輸出），但它也顯然失敗了第一個（ $ A $ 只是“返回 $ 0^n $ “)。所以第一個條件並不比第二個弱；事實上，任何失敗的第二個顯然都失敗了第一個（你只需使用相同的算法 $ A $ , 並使用 $ A(f(x))=x $ 所以 $ f(A(f(x)))=f(x) $ ）。所以第一個實際上比第二個強。
兩者之間的主要區別在於，第二個只是找到我們輸入函式的確切輸入。如果一個函式滿足這個條件，那麼這意味著知道輸出的攻擊者不會弄清楚我們的實際輸入。但這通常不是我們所關心的。在許多方案中，如果攻擊者可以找到任何輸入來獲得給定的輸出，無論它是否是我們使用的實際輸入，都是一個問題。條件 2 要求相反*；條件 1 只要求求逆，如果函式不是一對一的，則兩者之間存在差異。在加密貨幣中，單向函式往往用於求逆存在問題的地方。*
以密碼散列為例，假設我的密碼是
swordfish，它散列到ABCDE1234，並且散列函式滿足條件 2 但不滿足條件 1。由於 (2) 您無法有效地確定我的密碼是swordfish，但因為它失敗（1）你可以找到散列到（比如）的東西。當然，你沒有得到我的密碼，但是你發現了一些的倒數，而且你沒有得到我的密碼對我沒有幫助 -也適用於你的目的。ABCDE1234``letmein12``ABCDE1234``letmein12