為什麼需要減少證明（例如，對於 Elgamal 的安全證明）？
Elgamal 加密的教科書證明基本上簡化為決策 Diffie-Hellman 假設 (DDH)。
埃爾加馬爾： $ Gen(.): x \xleftarrow{R} \mathbb{Z}_p $ ; $ Enc(m,g^x): r \xleftarrow{R} \mathbb{Z}_p, U= m.(g^x)^r, V = g^r $ ; $ Dec(U,V,x): m = U/V^x $ .
假設我證明 Elgamal 的安全性（在 CPA 安全模型中）如下：
自從 $ r $ 是均勻隨機的， $ (g^x)^r $ 也是均勻隨機的。因此， $ m.(g^x)^r $ 服從均勻分佈。給出兩條消息 $ m_0, m_1 $ 在挑戰階段，對應的密文 $ c_0 $ 和 $ c_1 $ 遵循同樣的均勻分佈。因此，敵手的優勢與區分兩個相同的分佈相同，即為 0。
有人能告訴我上面的證明有什麼問題嗎？為什麼（或不是）足以表明密文遵循均勻分佈，即與真正的隨機值無法區分？
為什麼需要減少證明？
一般來說，約簡證明在電腦科學中是很常見的事情。特別是在密碼學中，推理是這樣的：
一般密碼學界認為這個問題 $ X $ 很難解決。我設計了一個新密碼 $ Y $ 並希望讓社區相信它很難打破。所以，我假設有人可以有效地打破 $ Y $ ，然後我證明使用有效的中斷 $ Y $ , 也有人能解決問題 $ X $ . 因此，我們可以得出結論，打破 $ Y $ 至少和解決一樣難 $ X $ . 由於普遍的共識是 $ X $ 真的很難解決 $ Y $ 必須是安全密碼。
這不是證明密碼安全性的唯一方法。如果我沒記錯的話，one-time-pad 的安全證明並不遵循這種範式。然而，隨著時間的推移，它已被證明是證明密碼安全性的一種非常好的方法，並且在實踐中執行良好。
有人能告訴我上面的證明有什麼問題嗎？為什麼（或不是）足以表明密文遵循均勻分佈，即與真正的隨機值無法區分？
見 Maeher 的評論。
除了 mikeazo 的回答之外，您要做的是將 DDH 問題替換為“均勻分佈問題”。這似乎是合法的，但並不令人信服，因為證明不是基於一個經過充分研究的問題。例如，也許方式 $ Gen(\cdot) $ 操作不確認均勻分佈。但是，將方案連結到 DDH，這意味著使用 DDH-secure $ Gen(\cdot) $ 功能，只要 DDH 沒有被破壞，該方案是安全的。