One-Way-Function
恆等函式是單向函式嗎?
單向函式的定義說:
- 它必須在多項式時間內是可驗證的
- 反轉它的機率小於或等於可忽略不計
現在,我不確定我是否完全理解一種方式的功能。
- 我能這麼說嗎 $ f(x) = x $ 是單向功能嗎?
- 我們是否假設我們知道如何 $ f $ 被定義為?
- 如果 $ x $ 有長度 $ l $ ,那麼猜到的機率為: $ (1/2)^l $ 這是微不足道的。
我很確定我的推理是錯誤的,有什麼提示嗎?
它不是單向的,因為有一種有效的算法可以用機率反轉它 $ 1 $ ; 即一種簡單地輸出其輸入的算法。
我們“知道函式”這一事實是隱含的,因為對如何“設計”算法沒有任何限制,只要求存在這樣的算法。