# Is this an instance of a Diffie-Hellman problem?

Let $$\mathbb{G}$$ be a cyclic group of order $$p$$ with generator $$g$$, and let $$m\in\mathbb{G}$$.

Problem: Given $$c=m.g^{k.a}$$ and $$v=g^a$$, where $$k,a \in \mathbb{Z}^*_p$$, output $$k$$.

Is this an instance of a Diffie-Hellman problem? Because the only way I see to solve this is to try $$v^i, i\in \mathbb{Z}^*_p$$ until we stumble on $$i=k$$, but since $$g^{k.a}$$ is also hidden by $$m$$, I do not think searching for $$i$$ is a viable method.

As stated the problem is insoluble as zero-knowledge of $$k$$ is provided (unless we know something about $$m$$).
To see this, let $$x$$ be any integer $$0\le x\le p-1$$ and let $$m':= m\cdot v^{-x}$$ then we see that $$c=m'\cdot g^{(k+x)a}$$ and we see that $$k+x\pmod p$$ is an equally valid output unless we have some reason to choose $$m$$ over $$m'$$.
• So, If I understood correctly, using your approach, we can get $k$ if we are able to deduce m. Thank you – vxek Mar 25 at 0:42
• More precisely we have enough information to get $k$ if we are able to deduce $m$. From $c/m=g^{ka}=v^k$ we are able to recover $k$ if we can solve the discrete logarithm problem in $G$. This may or may not be computationally feasible. – Daniel Shiu Mar 25 at 6:46