比較單向函式的兩種定義
我正在閱讀 Rafael Pass 關於單向函式的講義，遇到了兩個定義。
- 第一個是：一個函式 $ f $ 是單向的，如果 $ f $ 可以在 PPT 中計算，不存在不均勻的 PPT $ A $ 這樣
$ \forall x \in {0,1}^*, Pr[A(f(x)) \in f^{-1}(f(x))]=1 $
然而，這個定義被認為是不完美的，因為（例如）在這個定義下 $ f(x)=|x| $ 會很難，因為“這需要 $ 2^c $ 是時候給這樣的東西寫一個有效的逆了 $ f(x) = c $ . “（引自註釋）。
- 然後它給出了第二個定義， $ \forall $ 核顯 $ A $ , $ \exists \epsilon $ 這樣 $ \forall n \in N $
$ Pr[x \leftarrow {0,1}^n; y \leftarrow f(x): f(A(1^n, y)) =y] \le \epsilon(n) $
似乎我無法欣賞這裡的微妙之處，我有兩個問題：
- 為什麼 $ f(x)=|x| $ 拿 $ 2^c $ 是時候寫一個倒數了。
- 為什麼 $ 1^n $ 在定義 2 中是必要的。
有人可以闡明一下嗎？
我假設 $ |x| $ 在練習中表示位串的長度 $ x $ .
如果是這樣，答案很簡單：多項式時間算法需要在多個步驟中完成，這些步驟由輸入長度的多項式函式限定。
有多長 $ |x| $ ，表示為位串？嗯，需要 $ k $ 位來表示之間的數字 $ 2^{k-1} $ 和 $ 2^k-1 $ ，所以輸入的長度 $ n = |x| $ 是關於 $ \log_2 n $ 位。
因此，為了 $ A $ 為多項式時間算法， $ A(|x|) $ 最多必須完成 $ p(\log_2 |x|) $ 步驟，在哪裡 $ p $ 是一些多項式函式。但是寫出一個包含 $ |x| $ 位顯然至少需要 $ |x| = 2^{\log_2 |x|} $ 步驟，它不受任何多項式函式的限制 $ \log_2 |x| $ .
本質上，問題在於輸入 $ |x| $ 給予 $ A $ 與預期輸出相比“太短” $ x $ . 我們“解決”這個問題的方法就是給予 $ A $ 額外的輸入 $ 1^n $ 其長度與預期輸出的長度匹配。這樣，通過“填充”的輸入 $ A $ 至少與它的輸出一樣長，我們有效地允許執行時間 $ A $ 成為其輸入和（預期）輸出長度的多項式函式，同時仍遵守多項式時間算法的標准定義。
在程式中，我們稱其為 hack，或者可能是 kluge。但這是一個方便的組合，因為它使我們不必重新定義加密中的“多項式時間”，不同於通常在復雜性理論中定義的方式，因此避免了促進這兩個相關領域之間的通信。
唉，這種符號統一的代價是額外的 $ 1^n $ 這個論點有時會讓加密領域的新學生感到困惑——尤其是一些作者，也許是出於某種錯位的職業尷尬感，似乎不太願意解釋它實際上本質上只是一個符號黑客來製定“多項式時間”的標准定義“符合我們對加密貨幣的需求。