Join Log in
Score:1
avatar Crypto

Hardness of a variant of the CDH problem

us flag
raisyn

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.

78
0 + 0
Score:1
Ievgeni avatar Crypto
cn flag
Ievgeni

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

0 + 0
us flag
raisyn
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.
0
Reply
Ievgeni avatar
cn flag
Ievgeni
@raisyn Why are you sad, if this problem is harder, it means you can use it as an hardness assumption for your applications. No?
0
Reply
us flag
raisyn
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.
0
Reply
Ievgeni avatar
cn flag
Ievgeni
@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).
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.