CDH 問題變體的硬度

給定 $ g $ ，乘法群的生成器（在某些有限域或橢圓曲線上），以及群元素 $ \left( g^x, g^a, g^b, g^c, g^{x(a+b)}, g^{x(b+c)} \right) $ , 可以有效地找到 $ g^{x(a+b+c)} $ （不知道值 $ x, a, b, c $ )?

我相信手頭的問題與CDH問題密切相關（鑑於 $ \left (g, g^a, g^b \right) $ ， 尋找 $ g^{ab} $ ）。CDH 的有效算法立即導致上述問題的有效算法。所以上面的問題至少不比CDH難。然而，我既沒有找到一種方法來使用額外的資訊來獲得一個有效的解決方案，也無法證明它實際上和 CDH 一樣難。因此，非常感謝任何幫助。

假設 $ \mathcal{B} $ 知道如何計算 $ g^{x(a+b+c)} $ , 我想解決 cdh 挑戰 $ (g,X,Y) $ , (我們將解釋 $ X $ 作為 $ g^x $ 和 $ Y $ 作為 $ g^b $ ) 我們選擇標量 $ d,e $ 對應於 $ (a+b) $ 和 $ (b+c) $ 我們計算 $ Z=\mathcal{B}(X, g^d\cdot Y^{-1}, Y, g^e\cdot Y^{-1},X^d, X^e ) $ .

我們返回 $ \frac{X^{d+e}}{Z} $ .

證明： $ DLog \left(\frac{X^{d+e}}{Z}\right) = DLog \left(X^{d+e}\right) - DLog \left(Z\right) = x(d+e)- x\left( d-b + b + e-b\right) = xb $ .

引用自：https://crypto.stackexchange.com/questions/97969