1
$\begingroup$

Given $g$, a generator of a multiplicative group (over some finite field or elliptic curve), and the group elements $\left( g^x, g^a, g^b, g^c, g^{x(a+b)}, g^{x(b+c)} \right)$, is possible to efficiently find the value of $g^{x(a+b+c)}$ (without knowledge of the values $x, a, b, c$)?

I believe the problem at hand is closely related to the CDH problem (given $\left (g, g^a, g^b \right)$, find $g^{ab}$). An efficient algorithm of CDH immediately leads to an efficient algorithm for the above problem. So the above problem is at least not harder than CDH. However, I neither found a way to use additional information to arrive at an efficient solution nor was I able show that it is in fact as hard as CDH. So any help is highly appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let suppose $\mathcal{B}$ knows how to compute $g^{x(a+b+c)}$, and I want to solve the cdh challenge $(g,X,Y)$, (we will interpret $X$ as $g^x$ and $Y$ as $g^b$) we choose scalars $d,e$ which correspond to $(a+b)$ and $(b+c)$ and we compute $Z=\mathcal{B}(X, g^d\cdot Y^{-1}, Y, g^e\cdot Y^{-1},X^d, X^e )$.

We return $\frac{X^{d+e}}{Z}$.

Proof: $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$.

$\endgroup$
4
  • $\begingroup$ Sad to see the problem is actually not easier than CDH, there would have been some nice applications otherwise. It took me a while to work through your post. Fascinating how you came up with this so quickly. Thank you so much. $\endgroup$
    – raisyn
    Jan 5, 2022 at 13:47
  • $\begingroup$ @raisyn Why are you sad, if this problem is harder, it means you can use it as an hardness assumption for your applications. No? $\endgroup$
    – Ievgeni
    Jan 5, 2022 at 13:53
  • $\begingroup$ Well in the application I had in mind (related to aggregate signatures) I needed it the other way around. If is would be possible, there would be have been a nice way to aggregate signature efficiently in a specific setting. $\endgroup$
    – raisyn
    Jan 5, 2022 at 14:14
  • $\begingroup$ @raisyn I advise the reading of "The Uber-Assumption Family" (Boyen) to have an intuition to characterize the hard problems in a group context (even you do not find any reduction to standard assumption). $\endgroup$
    – Ievgeni
    Jan 5, 2022 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.