是不是很難計算gabgabg^{ab}給予時(g,ga,gb,ab)(g,ga,gb,ab)(g, g^a, g^b, frac{a}{b})?
我們知道 CDH 問題，計算 $ g^{ab} $ 從給定 $ (g, g^a, g^b)\in\mathbb Z_p^3 $ ， 很難。有輔助資訊還難嗎 $ \frac{a}{b}\bmod q $ （其中兩者 $ p $ 和 $ q $ 是大素數 $ q|p-1 $ ， 和 $ g $ 是一個有順序的生成器 $ q $ ) ?
這確實是一個難題——事實上，它至少和平方 Diffie-Hellman 問題(SDH) 一樣難，它指出給定 $ (g,g^a) $ , 無法計算 $ g^{a^2} $ . 這是一個標準且經過充分研究的假設，它可以簡化為 CDH（更正此答案的先前版本，我說它沒有 - 我對不知道這種減少的決策版本感到困惑）。
直覺：直覺上，SDH 就是一個 CDH 實例加上約束 $ a/b=1 $ . 因此，這是您考慮的問題的一個特例，其中 $ a/b $ 是已知的。
減少：給定一個算法 $ A $ 解決您的問題，以下是您解決 SDH 實例的方法： $ g,g^a $ ，選擇一個隨機指數 $ \lambda $ , 併計算 $ g^{\lambda^{-1}a^2} \gets A(g,g^a,g^{\lambda^{-1}a},\lambda) $ . 我讓你檢查輸入 $ A $ 確實是作為您問題的隨機實例分發的。然後，計算 $ (g^{\lambda^{-1}a^2})^{\lambda} = g^{a^2} $ .
對於從SDH到CDH的縮減，這是標準的；訣竅是使用身份 $ (x+y)\cdot (x-y) = x^2-y^2 $ . 環境 $ x = (a+b)/2 $ 和 $ y = (a-b)/2 $ 給 $ ab = ((a+b)^2-(a-b)^2)/4 $ ，從中簡化為 CDH 很簡單，只需兩次呼叫 SDH 預言機。