簡化為難題的意義在哪裡？
給定一個協議，如果我們可以將破壞協議簡化為一個難題，例如 DLP 或 CDH，我們可以說這個協議是安全的。
從理論上講，約簡是證明協議安全性的好方法。對於密鑰交換協議，如果縮減方法使用對手作為子程序，模擬器將構造一個算法。如果對手可以在某個模型下破壞協議，那麼模擬器可以解決一個難題，比如 CDH。
但是，在實踐中，模擬器的算法可以用電腦程序來實現嗎？此外，它有效嗎？
描述模擬的算法確實可以“實現”——本質上就是模擬器遵循的證明策略。
然而，實現對手（模擬器與之通信）的算法是另一回事。由於您希望（通常）對任何 PPT 對手保持減少，因此您不知道對手是如何工作的。
減少只是說你可以很好地給對手一個問題實例（對手沒有意識到這一點，即從對手的角度來看，模擬與真實環境沒有區別）然後當對手停止時輸出，您解決了相應的問題（機率不可忽略）。但是，您不知道對手是如何做到這一點的——因為對手可能有不同的策略。儘管如此，您並不真正關心這一點，因為如果您的歸約很嚴格（並且安全模型是有意義的），那麼您就擁有了證明歸約安全性所需的東西。
**備註：**實際上，有一些類型的縮減假設可以訪問對手的內部結構（對手的程式碼）。這些是非黑盒縮減。在密碼方案的證明中最常遇到的是黑盒縮減，這意味著模擬器只能將對手用作黑盒，而無需了解對手的內部運作（這也是我上面描述的）。
還原論證明中使用的另一種技術是倒帶（例如，在零知識協議中），即模擬器在遇到“壞”狀態時將對手倒回到某個狀態，然後再次從該步驟啟動對手，希望這樣的“ bad" 狀態這次不會遇到。但是，應謹慎使用這種倒帶技術。
有時還會遇到模擬控制對手的隨機性（隨機輸入磁帶）。
**簡單減少的範例（作為對您評論的回答）：**讓我們假設 Pedersen 承諾方案在一個小組中工作 $ G $ 素數的 $ p $ . 然後我們有兩個生成器 $ g, h $ 和 $ \log_g h $ 未知且系統參數為 $ pp=(G,p,g,h) $ （讓我們寫 $ pp\leftarrow Setup(1^k) $ 和 $ k $ 是安全參數）。承諾一個價值 $ m\in Z_p $ 一個選擇 $ r\in_R Z_p $ 並將承諾計算為 $ c=g^mh^r $ （讓我們把它寫成 $ (c,d)\leftarrow Commit(m) $ ， 在哪裡 $ d $ 是取消承諾值，這裡 $ (m,r) $ ）。打開承諾就是放棄 $ d=(m,r) $ 並檢查是否 $ c\stackrel{?}{=}g^mh^r $ 持有（讓我們把它寫成 $ b\leftarrow Open(c,d) $ 和 $ b=true $ ).
現在，如果對於任何 PPT 對手，承諾的綁定屬性都成立 $ A $ 我們有：
$ Pr[m\neq m’ \land b’=b=true
|pp\leftarrow (1^k), (c,d,d’)\leftarrow A(pp), b\leftarrow Open(c,d), b’\leftarrow Open(c,d’)] \leq negl(k) $在哪裡 $ negl(\cdot) $ 是一個可以忽略的函式。本質上，在我們的 Pedersen 設置中，對手需要做出承諾 $ c $ 使得開口接受 $ (m,r) $ 和 $ (m’,r’) $ 和 $ m\neq m’ $ . 然而，這意味著我們有 $ g^mh^r=g^{m’}h^{r’} $ . 我們稍後會回到這個事實：
現在我們減少離散對數問題 $ G $ 到 Pedersen 承諾方案的綁定屬性，即如果有一個對手以不可忽略的機率打破 Pedersen 承諾的綁定屬性，那麼我們可以解決 DLP $ G $ 以相同的機率。這種減少非常容易，因為模擬器不必模擬任何查詢（而只是向對手提供與真實攻擊中的參數無法區分的參數）。
模擬器：給定一個實例 $ y $ 離散對數問題的 $ G $ 關於發電機 $ g $ .
現在模擬器設置 $ pp=(p,G,g,y) $ 從而將 DL 實例嵌入到公共參數中。請注意，對於對手來說，這些參數是絕對完美的。
執行對手 $ A $ ：現在模擬器執行 $ A(pp) $ 而如果 $ A $ 管理它輸出 $ (c,d,d’)=(c,(m,r),(m’,r’)) $ 和 $ m\neq m’ $ ，則減少適用（注意，我們不做任何假設 $ A $ 管理它產生輸出）。
計算解決方案：現在模擬器已經從 $ A $ 價值觀 $ (c,(m,r),(m’,r’)) $ 並且知道 $ c=g^my^r=g^{m’}y^{r’} $ （我們已經在上面看到了這個，現在回到那個）。這也意味著 $ r\neq r’ $ . 此外，服用時 $ \log_g c $ 我們有 $ m+r\alpha \equiv m’+r’\alpha \pmod{p} $ . 這在做一些算術時給出 $ \alpha\equiv (m-m’)(r’-r) \pmod{p} $ . 既然模擬器知道 $ m,m’,r’,r’ $ 它可以計算 $ \alpha \in Z_p $ . 現在，它必須持有 $ y=g^\alpha $ 和模擬器輸出 $ \alpha $ 作為 DLP 實例的解決方案 $ y $ .
那麼這意味著什麼：如果存在一個有效的對手 $ A $ 它能夠以不可忽略的機率打破 Pedersen 承諾的綁定屬性，那麼我們可以為 DLP 建構一個求解器，它使用 $ A $ 作為一個黑盒，具有相同的成功機率並且需要更多的執行時間（本質上是計算 $ \alpha $ 從 $ m,m’,r,r’ $ ).