是F(f(x))F(F(X))f(f(x))單向功能？
我從一本書中找到了以下證明。
雖然我了解最初的構造，但我不明白證明該陳述的最後一句話。
- 為什麼 $ f(f(x)) $ , 在論文中 $ h(h(x)) $ , 總是等於 $ 0^{2n} $
- 這就是他們所說的嗎？
- 為什麼它顯然不是單向功能？
注意：在寫這個答案時，我發現在引用的講義中給出的證明似乎存在差距。因此，我將在下面展示一個稍微修改過的證明版本，並在最後討論一下差異。
讓我們先快速回顧一下，因為您對講義的引用和摘要遺漏了一些重要的部分。
單向函式的正式定義，從您的講義中的定義 5 略微擴展，是：
一個函式（家族） $ f: {0,1}^n \to {0,1}^m $ 是單向的當且僅當它可以通過多項式時間算法計算，並且如果沒有機率多項式時間算法能夠以不可忽略的機率為其找到原像。
換句話說，對於 $ f $ 單向，不可能有機率算法 $ A $ 可以，給定輸出 $ y = f(x) $ 對於一些隨機選擇的輸入 $ x \in {0,1}^n $ 和最大執行時多項式 $ n+m $ , 找到一個輸入 $ x’ $ （可能但不一定等於原始輸入 $ x $ ) 使得 $ f(x’) = y $ 機率大於可忽略的函式 $ n $ .
撇開漸近複雜性理論的所有形式主義，對此的非正式總結就是： $ f $ 如果沒有實際的方法是單向的，給定一個隨機輸出 $ f $ , 找到當給定時產生該輸出的輸入 $ f $ .
基於這個定義，我們可以證明：
- 填充輸出 $ f $ 比如說，一堆零不會影響它是否是單向的。（根據定義，攻擊者總是會收到一個有效的輸出，所以他們可以去掉零，然後像攻擊原始的、未填充的函式一樣繼續進行。）
- 此外，將一堆額外的虛擬位添加到 $ f $ ，不影響輸出，不改變是否 $ f $ 是單向的。（由於虛擬輸入位不會影響輸出，因此攻擊者可以隨意選擇這些虛擬位；但是為其他非虛擬輸入位找到正確的值仍然與為原始的，未修改的功能。）
（這些在技術上僅在添加的填充/忽略位的數量是原始輸入 + 輸出長度的多項式函式時才成立，但這對於我們的目的來說已經足夠了： $ n \mapsto 2n $ 肯定是多項式函式。）
所以，給定一個（任意）單向函式 $ f $ 和 $ n $ -位輸入和輸出，我們可以構造另一個單向函式 $ h $ 輸入和輸出長度是這樣的兩倍：
- 讓 $ x^* $ 成為第一個 $ n $ 輸入位 $ x $ 至 $ h $ . 忽略輸入的其餘部分。
- 計算 $ y^* = f(x^*) $ .
- 前置任意常數 $ n $ -位串 $ c $ （例如 $ c = 000…0 $ ） 至 $ y^* $ ，並輸出結果 $ 2n $ -位串 $ y = c ,|, y^* $ 作為 $ h(x) $ .
現在，通過構造，這個函式 $ h $ 是單向的，因為找到它的原像至少和找到它的原像一樣難 $ f $ . （當然，安全參數為 $ f $ 和 $ h $ 相差2倍，但漸近沒有區別；的多項式函式 $ 2n $ 是多項式函式 $ n $ .)
但也通過建設，第一個 $ n $ 的輸出位 $ h $ 總是恆定的，而剩餘的輸出位僅取決於第一個 $ n $ 位的輸入。因此， $ h(h(x)) = c ,|, f(c) $ 對所有人 $ x $ ，因此尋找原像 $ h(h(x)) $ 是微不足道的（因為實際上任何輸入都可以）。
現在，您引用的講義中給出的結構更進一步，明確定義 $ h $ 產生一個全零輸出，每當第一個 $ n $ 輸入位為零（並且始終設置第一個 $ n $ 否則輸出的位為零）。
雖然不是絕對必要的（我們將從 $ h(h(x)) $ 無論如何），這實際上並沒有損害單向性 $ h $ 任何一個。事實上，我們可以證明修改 $ h $ 所以它總是為總輸入空間的一小部分輸出一個常數值，這不會影響它的單向性（並且 $ 1/2^n $ 確實是一個可以忽略不計的小部分 $ n $ 趨於無窮）。
然而，講義出錯的地方是當他們試圖通過聲稱來證明這一點時：
“先前定理的推廣（在單向函式中固定值）表明 $ h $ 也是單向函式。（簡而言之，我們只是固定 $ \frac{2^n}{2^{2n}} = \frac1{2^n} $ 的所有可能值 $ x $ . 因為我們只修復了可能值的可忽略不計的一部分 $ x $ , 稍作修改的相同證明仍然適用。)"
事實上，這種說法是錯誤的。作為一個簡單的反例，考慮修改後的函式 $ h’ $ 定義為：
- 拆分 $ 2n $ 位輸入 $ x $ 一分為二 $ n $ -位字元串 $ x_1 $ 和 $ x_2 $ .
- 如果 $ x_1 = c $ ， 返回 $ h’(x) = c ,|, x_2 = x $ .
- 否則，返回 $ h’(x) = c ,|, f(x_1) $ .
清楚地， $ h’(x) = h(x) $ 對於除了可以忽略不計的一小部分輸入（即那些以 $ n $ -bit 常量字元串 $ c $ ）。然而 $ h’ $ 顯然不是單向函式，因為任何有效的輸出 $ y = h’(x) $ 總是以 $ c $ ，它自己的原像也是如此！
當然，這並不會使實際聲明無效，因為函式 $ h $ 實際上在註釋中構造的實際上是單向的（前提是 $ f $ 是單向的）。儘管如此，如果這些筆記來自您正在學習的課程，您可能想向您的老師提及證明中的這個差距。