證明函式是單向函式

我試圖證明一個函式是一個單向函式。

我正在研究的功能是 $ f’(x,y)=f(x)||f(x \oplus y) $ .

對於我所了解的類似解決方案（例如1c），策略如下：

1. 認為 $ f’ $ 不是一種方式，所以存在一個 $ A’ $ 可以反轉 $ f’ $ 具有不可忽略的機率
2. 利用 $ A’ $ 建構 $ A $ 可以反轉 $ f $ .
3. 顯示 $ A $ 倒置 $ A $ 具有不可忽略的機率
4. 矛盾。

基於這些知識，我試圖證明給定的

$$ f’(x,y)=f(x)||f(x \oplus y) $$

---

所以，這是我的嘗試：

1. 認為 $ f’(x,y) $ 不是單向功能
2. 所以，存在一個 $ A’ $ 可以反轉 $ f’ $ 可能性
3. 構造

$ A(z) $ :

• 選一個 $ w \in f(x) $ （對於任何 $ x $ )
• $ x,y <- A’(f(z, y)) = A’(f(x) || f(x \oplus w)) $
• 我們現在已經顛倒了上半場
• …
• 返回 $ x,y $

但是，儘管我了解該方法，但我找不到任何有效的構造方法：

• 你怎麼能建造這樣的建築？
• 有什麼我做錯了嗎？還是我在正確的方向？

構造機率的最簡單方法 $ A $ 很簡單，給定 $ z $ :

• 隨機選擇 $ w $
• 計算 $ A’(z || f(w)) $ .
• 如果 $ A’ $ 成功，然後它會評估為 $ (x, y) $ 配對 $ z = f(x) $ 和 $ f(w) = f(x \oplus y) $ .
• 丟棄 $ y $ , 並返回 $ x $ 作為 $ A(z) $ .

我們隨機選擇 $ f(w) $ ，而不僅僅是插入另一個副本 $ z $ , 因為有可能 $ A’ $ 在表單的輸入上總是會失敗 $ (z || z) $ . 正如我所寫，如果 $ A’ $ 在其輸入的一個重要部分上成功，然後 $ A $ 將在其輸入的相同重要部分上成功。

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