Discrete-Logarithm
這種計算會導致解決深度學習問題嗎？
想像我們有 $ g^x $ , $ a $ 和 $ g^b \in \mathbb{Z}_p $ . 計算是否現實 $ g^{(a+x)b} $ 不知道 $ x $ 和 $ b $ ? 還是相當於解決離散對數問題？
不。
假設均勻隨機抽樣 $ x,b $ 應用時，這（我們稱之為 E-CDH）實際上（就硬度而言）等價於計算 Diffie-Hellman 問題(CDH)。其中指出：給定一個有限群 $ G $ ， 樣本 $ a,b\in G $ 均勻隨機並提供 $ g^a,g^b $ . 如果能找到問題就解決了 $ g^{ab} $ .
證明：
CDH 最多和 E-CDH 一樣難（ $ \Rightarrow $ ）。假設我們有一個預言機 $ \mathcal O(g^b,a,g^x) $ 返回 $ g^{(a+x)b} $ （即解決 E-CDH 的預言機）。我們現在可以解決任何給定的 CDH 實例 $ g^a,g^b $ 由於 $ \mathcal O(g^a,0,g^b)=g^{(a+0)b}=g^{ab} $ .
E-CDH 最多和 CDH 一樣難（ $ \Leftarrow $ ）。假設我們有一個預言機 $ \mathcal O(g^a,g^b) $ 返回 $ g^{ab} $ ，即解決了CDH問題。現在假設我們得到了實例 $ g^x,a,g^b $ ，我們現在計算 $ g^a $ 和 $ g^x\cdot g^a=g^{x+a} $ . 最後我們返回 $ \mathcal O(g^{x+a},g^b)=g^{(x+a)b} $ 從而解決實例。
小假設：我們實際上需要知道 $ g $ 和相關組。