弱單向函式的組合不是強單向函式
給定 $ f(x) $ ，一個弱單向置換，如何證明 $ f^T(x) $ 是不是很強的單向功能？這裡 $ f^T $ 表示 $ T $ 次自作文 $ f $ 和 $ T $ 是輸入長度的多項式。
顯然，作曲 $ T $ -弱 OWP可以產生強 OWF：只需考慮以下情況 $ f $ 已經是強 OWP（因此特別是弱 OWP）。現在，您想要表明情況並非如此；即，你想要一個功能 $ f $ 這是一個弱 OWP，但是這樣 $ f^T $ 不是一個強大的 OWF（即，安全性不會“通過組合放大”的範例）。
我會給你這樣一個候選人；我讓你證明它滿足你的要求，這是一個非常簡單的練習。讓 $ g: I \mapsto I $ 是任意（強或弱）OWP，並讓 $ J $ 是一些任意的集合，使得 $ |J| = |I| $ ， 和 $ I $ 與 $ J $ . 考慮以下函式 $ f $ :
$ f:I \cup J \mapsto I \cup J $ 定義如下： $ f(x) = g(x) $ 如果 $ x \in I $ ， 和 $ f(x) = x $ 如果 $ x\in J $ .
宣稱： $ f $ 是一個排列（這很明顯），也是一個弱 OWP（你應該能夠輕鬆檢查）。然而， $ f^T $ 仍然是弱OWP，但不是強OWF。你能看出為什麼嗎？
（如果您在分析中遇到困難，請在評論部分尋求更多提示）
你如何定義弱與強？我們需要考慮某種額外的構造。根據定義，排列是可逆的。您可能是指它與隨機排列的區別。
對於一個結構良好的，比如 Keccak- $ f $ , 逆計算的成本可能要高得多。無論如何，應用 Keccak- $ f $ 如果我們只給 24 次是安全的 $ r $ 應用此功能後的數據位（讓我們聲稱 (1600 - r)/2 位安全性）。如果我們要訪問整個狀態，那麼它顯然是不安全的。
不過作為重要說明，因為您正在談論應用完全相同的排列 $ T $ 次，那麼你不能有不同的輪常數。因此，如果你想要一個“強”的結果，初始排列不可能完全容易受到旋轉攻擊。但這是一個相當低的標準，因為您可以通過在您的域中包含一個“寬”添加操作來實現這一點，然後 $ T $ 線性的長度 $ x $ 足以解決這個問題。當然，有許多不同類型的攻擊。例如，你不能有一個容易受到滑動攻擊的結構，因為它的輪數可能變得無關緊要（這類似於不添加任何對抗旋轉攻擊的排列）。