Software-Obfuscation
是否存在可逆的黑盒混淆器？
我們將說一個混淆器 $ \mathcal{O} $ 是一個可逆的黑盒混淆器，如果對於每個可逆程序 $ P $ 被混淆的程序 $ \mathcal{O}(P) $ 仍然是可逆的，但不會比計算的預言機透露更多資訊 $ x\mapsto P(x) $ 連同一個計算 $ x\mapsto P^{-1}(x) $ . 眾所周知，不存在黑盒混淆器。是否存在可逆的黑盒混淆器？
通過“可逆程序”，我假設您的意思是單射函式。
您的問題的答案是否定的，單射函式集沒有黑盒混淆器。
這個想法是使用 Feistel 技巧使不可混淆的函式可逆。更正式地說，如果 $ g: {0,1}^n \to {0,1}^n $ 定義 $ Feistel_g : {0,1}^{2n} \to {0,1}^{2n} $ 作為
$$ Feistel_g(x,y) = (x, g(x) \oplus y). $$ $ Feistel_g $ 是可逆的，不管 $ g $ （當輸入/輸出長度為 $ g $ 是不同的）。
讓 $ \mathcal{G} $ 是 Barak 等人論文中不可混淆的函式族。然後定義
$$ Feistel_\mathcal{G} = { Feistel_g \mid g \in \mathcal{G} } $$ 那麼這個族只包含可逆函式。此外，它是不可混淆的黑盒，因為黑盒訪問 $ g $ 可以模擬給定的黑盒訪問 $ Feistel_g $ （反之亦然）。和oracle訪問 $ (Feistel_g)^{-1} $ 是多餘的，因為 $ Feistel_g $ 是它自己的逆。