P 中的 Diffie Hellman 問題的後果是什麼？
計算 Diffie Hellman 問題想知道 $ g^{ab} $ 給定 $ g^a $ , $ g^b $ 和 $ g $ 而離散對數問題想知道 $ x $ 從 $ g^x $ 和 $ g $ .
後者在多項式時間內可解決也意味著前者，但相反的結果尚不清楚。
如果 Diffie-Hellman 是可破解的，但離散對數算法尚不清楚，那麼密碼學的後果是什麼？
您的問題背後有一個大問題（Meir Maor 暗示），即：
該算法必須適用於固定組還是任何組？
請注意，存在 DLOG（以及簡化為 DLOG 的事物）很容易的組，最基本的範例是組 $ (\mathbb{Z}/n\mathbb{Z}, +) $ . 即使在密碼學中使用的組中，有些組的 DLOG（以及簡化為 DLOG 的東西）現在比我們以前認為的要容易得多——特別是組 $ (\mathbb{F}{p^n}^\times, \times) $ 為了 $ p = O(1) $ 承認准多項式時間 DLOG 算法 —本文顯示了預期時間 $ (pn)^{2\log_2(n) + O(1)} $ . 這個弱點不僅僅是理論上的，到目前為止最大的DLOG 計算在 $ \mathbb{F}{2^{30750}}^\times $ .
當然，這都是關於離散對數問題的。還有（在我看來）另外兩個自然問題：
- 如果 CDH 在任意組中怎麼辦 $ P $ , 但 DLOG 不在 $ P $ ?
- 如果對於特定的加密興趣組，CDH 在 $ P $ , 但 DLOG 不在 $ P $ ?
對於第一個問題，這不太可能發生。這是因為在代數群模型中問題是等價的。該模型在一定程度上限制了計算（DLOG 算法 $ \mathbb{F}_{2^{30750}}^\times $ 無法在其中表達），但限制有點自然——計算被視為（線性）步驟序列，步驟中使用的任何組元素 $ i $ 必須從前面步驟中使用的組元素顯式計算。這裡有一些我不完全熟悉的細微差別
$$ 1 $$，但模型的重點是擷取僅使用組的“公共 API”的算法，而不是有關組結構的具體細節。 這意味著如果 DLOG 和 CDH 對於一般組不等效，則該模型在擷取組理論計算的“公共 API”部分方面存在很大缺陷，這在檢查模型時可能並不明顯（至少對我而言）。
對於第二個問題，這也不太可能發生（但出於其他原因）。具體而言，已知這兩個問題在任意循環群上不均勻地等價於彼此。有關詳細資訊，請參閱我之前的答案。
這兩點都沒有絕對排除 CDH 和 DLOG 之間的分離，但兩者都提供了一些正式證據表明這種分離不太可能發生。
$$ 1 $$具體來說，您從哪些組元素開始？組標識看起來很自然，但第 7 頁底部的討論聽起來你也得到了隨機的 oracle 查詢。還有別的事嗎？
後果很少。事實上，離散對數很可能在 P 中，或者至少它不太可能是 NP 難的。離散對數是隨機自約的，這也是我們喜歡它的原因之一。隨機實例與最壞情況一樣困難。
可悲的是，NP-Hard 隨機自約問題的存在意味著多項式層次結構的崩潰，而事實並非如此。
因此，儘管有令人信服的論點，Diffi Helman 並不“硬”，但我們仍然使用它。由於我們知道沒有有效的算法來破解它，而且我們一直在努力尋找一段時間，這真的和你在密碼學中得到的一樣好。
請注意，我們可以對可能的事件進行排名：
- 證明 DH 在 P
- 展示 DH 的多項式時間算法
- 一種能夠打破常見方案的高效算法。
第一個將在學術界引起轟動，但實際上不會讓任何人感到驚訝。第二個可能會導致無處不在的基於 DH 的算法的瘋狂替換。第三個將打破網際網路。
對於任何場/環上的通用解決方案或僅對 Zp 的影響也將有所不同。