計算問題到決策的簡化證明
它們是攻擊者的任何還原論證明嗎 $ \mathcal{I} $ 對於一個完善的計算“困難”問題 $ \mathsf{Π} $ 正在僱用攻擊者 $ \mathcal{A} $ 我們假設誰能夠解決決策問題 $ \mathsf{Γ} $ （即：語義安全->猜測是否 $ b=1 $ 或者 $ b=0 $ ） 為了 $ \mathcal{I} $ 打破 $ \mathsf{Π} $ 如果是這樣，可以得出結論 $ \mathsf{Γ} $ 安全 $ \mathsf{Π} $ , 表示如果存在 $ \mathcal{A} $ ，我們可以建立 $ \mathcal{I} $ ?
進一步解釋：
通常，當減少決策性難題時，那麼在您的構造中，您要麼使用對手對您的安全性建模，即破壞系統意味著攻擊者應該計算某些東西，或者它必須區分某些東西（不可區分性遊戲按順序排列） $ \mathcal{A} $ 猜測 $ b $ 從加密 $ x_b $ ）。並且這個攻擊者被成熟的問題攻擊者用作子程序，以破壞他的計劃。
假設我們模型中的攻擊者能夠區分加密 $ x_0 $ 從加密 $ x_1 $ . 這並不意味著攻擊者正在洩露底層密鑰，也不意味著它必須計算一些東西。這意味著它只能區分。我很難理解如何將此類攻擊者用作攻擊者已建立的計算問題的子程序 $ \mathcal{B} $ 必須計算一些東西而不是區分（或決定）。而且我想知道這種減少是否存在，或者從理論上講，您是否永遠無法從決策減少到計算。即：CDH不能使用DDH攻擊者計算 $ g^{ab} $ 但情況恰恰相反。
這類事情的一個典型例子是用於任意單向函式的 Goldreich-Levin 核心位。
Goldreich-Levin 結構的安全性證明涉及表明，如果 Mallory 可以預測這個單比特值（即使機率略高於 $ 1/2 $ )，則可以反轉單向函式。因此，這是子程序僅具有區分能力（預測單個位值）的簡化。減少顯示瞭如何使用它來解決計算問題（反轉單向函式）。算法的核心表明，如果 Mallory 能夠區分 $ (r_i, x \cdot r_i) $ 從 $ (r_i, b_i) $ （在哪裡 $ b_i $ 是一個隨機位， $ r_i $ 是隨機的 $ n $ -位值，和 $ x_i $ 是個秘密 $ n $ -bit 值），那麼我們可以使用 Mallory 作為子程序來學習秘密值 $ x $ .
有關 Goldreich-Levin 構造的更多詳細資訊，我推薦 Luca Trevisan 的講義：https ://lucatrevisan.wordpress.com/2009/03/09/cs-276-lecture-11-one-way-functions/和https： //lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/。特別注意後一頁的定理 1，它是您要求的形式的簡化。或者，您可以閱讀Mihir Bellare 對 Goldreich-Levin 構造的介紹和相關的正確性證明，以查看對相同結果的不同闡述。