Public-Key
為什麼二次殘差攻擊不能與具有決策差異 Hellman 假設的 Elgamal 加密一起使用？
我正在閱讀這篇筆記http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture4.pdf
鑑於離散對數假設不足以保證語義安全，我假設即使我們選擇 x 和 r 以使兩者都不均勻，也有可能獲得二次殘差。
但是，決策差異 Hellman 假設呢？不就是一樣嗎？對手不能同樣選擇一條二次剩餘的消息並進行相同的攻擊嗎？
不同之處在於我們認為該假設適用於哪些群體。
離散對數假設被認為適用於以下形式的組 $ \mathbb{Z}_p^* $ 和 $ p $ 總理等。正如鍊接的講義中所解釋的，存在多項式時間算法來確定是否 $ m_b $ 是二次餘數。這足以排除一半可能的明文，因為在以素數為模的組中，恰好有一半的元素是二次餘數。鑑於這個反例，離散對數假設因此不足以實現語義安全。
決策 Diffie-Hellman 假設不適用於組 $ \mathbb{Z}_p^* $ 和 $ p $ prime，但它被認為適用於其他組 - 通常用於 ElGamel 的組。DDH 假設是一個更強的假設，適用於離散對數假設成立的某些組。
特別是，如果 DDH 假設成立，我們可以證明不存在確定元素是否為二次餘數的多項式時間算法。這必然反駁了組的 DDH 假設 $ \mathbb{Z}_p^* $ 和 $ p $ 主要。
長話短說，如果DDH 假設成立，那麼攻擊者無法在多項式時間內使用二次殘差執行攻擊，甚至無法在多項式時間內區分選擇的明文。然而，DDH 假設並不適用於離散對數假設成立的所有組，並且對於其中一些 DDH 假設不成立的組，攻擊者可以在多項式時間內執行攻擊。