Diffie-Hellman
將決策 Diffie-Hellman、離散對數和指數假設知識聯繫起來
我很好奇離散對數和決策 Diffie-Hellman 之間的關係。有如下假設將兩者聯繫起來是否安全？
給定統一且獨立選擇的 g^x 和 g^y，如果有一個有效的算法可以以不可忽略的機率區分 g^(xy) 和隨機 g^r，那麼就有一個提取器可以提取 x 或 y不可忽略的機率？
這看起來像是指數知識假設，但是，我希望它能夠解決決策問題。眾所周知，一些橢圓曲線群可以使用配對來破壞 DDH，在這種情況下，我們將討論限制在諸如 Blum 整數上的二次殘差群之類的群。
我認為建立這個連結根本不常見。
一個很好的理由是，例如具有對稱配對的雙線性群（類型 1）對於離散對數假設可以被認為是安全的，但對於 DDH 假設永遠不會如此。
如果您收到 $ (g,x,y,z) $ ，您可以輕鬆檢查是否 $ e(g,z)=e(x,y) $ , 這個等式足以決定它是否是一個 Diffie-Hellman 元組。
要了解更多理論上的原因，您可以查看 Gap-DH 假設（在此問題中，對手必須使用 DDH 預言機解決 CDH 實例）：因此已經證明，如果對於任何代數對手，如果 DLog 成立，那麼Gap-DH 也是一個難題（因此，如果您將 CDH 實例替換為 DLog 實例，它會變得更加困難）。
您可以查看此 phd 第 136 頁了解更多詳細資訊
https://www.iacr.org/phds/index.php?p=detail&entry=1476
而且因為考慮代數對手在我看來等同於指數知識假設，因此建立這樣的聯繫真的很奇怪（據我了解，這意味著 Dlog 很容易，但我不完全確定那）。