One-Way-Function
兩個單向函式的串聯是單向函式嗎？
假設我們有兩個單向函式 $ f $ 和 $ g $ . 我們定義了一個新函式 h，它是 f 和 g 的串聯。那是， $ h(x)=f(x), g(x) $ ，其中逗號表示連接。我們想弄清楚這是否是單向函式。我的老師告訴我這通常不是真的。我知道這是真的，如果 $ f=g $ ，但除此之外我一無所知。我很想得到一些幫助。
但是 h 或多或少是可逆的嗎？我就是這樣被問到這個問題的。
當數學家說“這個陳述通常不正確”（或類似的措辭）時，他們的意思是“存在該陳述為假的情況”。所以你的老師在談論“為了所有人 $ f $ 和 $ g $ 這是單向函式 $ h(x)=f(x),g(x) $ 也是一個單向函式”，並說這個一般性陳述是錯誤的，即使它對於某些選擇可能是正確的 $ f $ 和 $ g $ .
看看這個具體的說法：
- 有選擇的地方是真的。你已經找到了瑣碎的 $ f=g $ .
- 有錯誤的選擇。什麼時候 $ g(x)=f(x)\oplus x $ , $ h $ 從來都不是單向函式，因為你可以恢復 $ x=f(x) \oplus g(x) $ 從 $ h(x) $ （從技術上講，您仍然必須證明存在 $ f $ 和 $ g $ 與這種關係都是單向函式）。
- 實際上，如果您不選擇 $ f $ 和 $ g $ 故意製造弱 $ h $ , $ h $ 通常也會是 OWF，但數學家會避免這種模糊且難以形式化的聲明。