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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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'$.

Improve this answer
$\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
    Commented Mar 25, 2021 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 S
    Commented Mar 25, 2021 at 6:46

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.