0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ So, If I understood correctly, using your approach, we can get $k$ if we are able to deduce m. Thank you $\endgroup$ – vxek Mar 25 at 0:42
  • $\begingroup$ 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. $\endgroup$ – Daniel Shiu Mar 25 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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