0
$\begingroup$

Let $G$ be a generator of a cyclic group in which the discrete logarithm problem is hard and $x$ and $u$ be scalars of the group such that $X = xG$ and $U = uG$, respectively. We want to compute $J = x^{-1}U$. Is it possible to calculate it without knowing $x$, even if we know $u$?

$\endgroup$
4
  • $\begingroup$ Usually one can prove this by reducing the problem into Dlog. What is the source of this problem? What did you try? $\endgroup$ – kelalaka Oct 24 '20 at 17:10
  • $\begingroup$ Which one, $U$ or $X$? It is used as a linking tag in a linkable ring signature, for example. Do you want a reference? I tried many things, thats why I am asking here :p $\endgroup$ – Fiono Oct 24 '20 at 17:30
  • $\begingroup$ Where did you see this problem, homework, exercise, article, while doing research, etc? You should indicate it, right? $\endgroup$ – kelalaka Oct 24 '20 at 17:32
  • $\begingroup$ I saw it here: eprint.iacr.org/2020/018. Basically, I need to forge $J$ without knowing the secret key $x$ for a security proof. $\endgroup$ – Fiono Oct 24 '20 at 17:47
3
$\begingroup$

This problem is equivalent to the Computational Diffie Hellman problem; this remains true even if we know $u$.

See this paper for details; in summary:

  • Suppose we have an oracle that, given $G$, $X = xG$ and either (depending on the oracle type) $U = uG$ or $u$, gives us the value $J = x^{-1}uG$. Then, we can use this Oracle to construct a second Oracle that, given $H, aH$, computes $a^2H$ (by passing $G = aH$, $X = H = a^{-1}G$, $U=G$ (or $u=1$), and recovering $J = (a^{-1})^{-1} \cdot 1 \cdot aH = a^2H$. We can then use this second Oracle to solve the CDH problem (given $G, aG, bG$, we compute $(2ab)G = (a+b)^2G - a^2G - b^G$, and then do a point halving.

  • Suppose we have an oracle that solves the CDH problem, that is, given $H, aH, bH$, gives us the value $abH$. Then, given $G$, $xG$, we can compute $x^{-1}G$ by setting $H = xG$, $aH = bH = G = x^{-1}H$ and $bH = H$. We give this to the Oracle which gives us the value $(x^{-1} \cdot x^{-1}) H = x^{-1}G$. Then, we can convert that value into $J$ by either multiplying it by $u$ (if we know it), or invoking our CDH Oracle one more time with the inputs $G, x^{-1}G, uG$.

$\endgroup$
5
  • $\begingroup$ Thank you, @poncho! So there is no way to construct an oracle that computes $J$ without knowing $x$, right? I needed that for a security proof... $\endgroup$ – Fiono Oct 24 '20 at 19:39
  • 1
    $\begingroup$ @Fiono: actually, if you can solve the CDH problem without solving the DLog problem, you can compute $J$ without knowing $x$ $\endgroup$ – poncho Oct 24 '20 at 21:25
  • $\begingroup$ but can you? I mean, aren't the two considered equally hard problems? If you can solve one, can't you solve the other by some kind of reduction? $\endgroup$ – Fiono Oct 25 '20 at 12:01
  • 2
    $\begingroup$ @Fiono: there is no known generic reduction from the DLog problem to the CDH problem. Of course, we can reduce the CDH problem to the DLog problem; if you have a DLog oracle, you can solve CDH in the fairly obvious way... $\endgroup$ – poncho Oct 25 '20 at 15:46
  • $\begingroup$ Makes sense. Thank you! $\endgroup$ – Fiono Oct 25 '20 at 15:57

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.