Discrete-Logarithm
有沒有 CDH 容易但 DLog 很難的組？
問題很簡單：
是否有一個小組可以證明解決 CDH 問題很容易，但假設解決離散對數問題很難？
複習問題：
- **CDH：**讓 $ \mathbb G=(G,+,0,p) $ 是一個公共循環有序群 $ p $ . 鑑於任何 $ g\in G $ 和 $ g^a,g^b $ 和 $ a,b\stackrel{$}{\gets}{0,\ldots,p-1} $ ，即具有均勻隨機指數，找到 $ g^{ab} $ .
- **DLog：**讓 $ \mathbb G=(G,+,0,p) $ 是一個公共循環有序群 $ p $ . 鑑於任何 $ g\in G $ 和 $ g^a $ 和 $ a\stackrel{$}{\gets}{0,\ldots,p-1} $ ，即具有均勻隨機指數，找到 $ a $ .
有一些已知的組，其中計算 Diffie-Hellman假設等價於離散對數問題。此外，已經表明，“當根據組順序提供少量額外資訊時”等價成立。此外，這些額外資訊已針對實際密碼應用中使用的某些橢圓曲線組進行了計算。後來減持又收緊了。
整個研究進展表明，雖然沒有完全的等價性證明，但有一些證據導致人們相信可能不存在任何群，其中計算 Diffie-Hellman 很容易，但離散對數問題很難。
這是接近但不完全符合您要求的東西。但這對於您的想法可能就足夠了。
本文利用不可區分性混淆構造一個具有自雙線性映射的群——即映射 $ e : G \times G \to G $ （相同的來源和目標群體）。
Yamakawa 等人，來自不可區分性混淆的未知順序組的自雙線性映射及其應用，CRYPTO 2014。
儘管我不完全理解他們的硬度假設，並且他們沒有明確談論離散對數，但 Diffie-Hellman 的“明顯”概括給出了安全的多方非互動式密鑰協議這一事實表明離散對數必須是難的。
不幸的是，有一個自雙線性映射 $ e : G \times G \to G $ 與CDH解決方案不太一樣！事實上，它們的建築用途 $ e(g^x, g^y) = g^{2xy} $ 這是雙線性的，但它們在 RSA 組的（子組）中 $ \mathbb{Z}_{pq} $ 計算平方根很困難。他們明確地仍然希望CDH在小組中努力！