組合兩個單向函式，使得結果不是單向函式

是否有可能有兩個不同的單向函式（例如，稱為 $ h $ 和 $ g $ ) 使得它們的組成 $ h \circ g = [, x \mapsto h(g(x)) ,] $ 不是單向嗎？

功能 $ f $ Maeher在這個對相關問題的回答中介紹的也應該在這裡完成工作（因為兩者 $ g $ 和 $ h $ ）。為方便起見，讓我在這裡引用這個答案：

假設一個單向函式 $ h $ 存在於輸入和輸出長度相同的地方。我們稱這個長度 $ n/2 $ . 即我們有一個單向函式$$ h : {0,1}^{n/2} \to {0,1}^{n/2}. $$

從這個函式，我們現在構造一個新函式 $$ f : {0,1}^{n} \to {0,1}^{n} $$如下： $$ f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1), $$ 在哪裡 $ |x_1|=|x_2|=n/2 $ .

如 Maeher 的回答所示， $ f $ 是單向的，如果 $ h $ 是。然而， $ f(f(x)) = 0^{n/2}\Vert h(0^{n/2}) $ 是常數，獨立於 $ x $ （除了它的長度 $ n $ )，因此找到原像是微不足道的。

引用自：https://crypto.stackexchange.com/questions/24348