CDH问题变体的硬度

Question

给定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一样困难。所以任何帮助都是非常感谢的。

Answer 1

假设\mathcal{B}知道如何计算g^{x(a+b+c)}，并且我想解决cdh挑战(g,X,Y) (我们将X解释为g^x，Y将解释为g^b)，我们选择与(a+b)和(b+c)对应的标量d,e，然后计算

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.