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, 2020 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, 2020 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, 2020 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, 2020 at 17:47

1 Answer 1

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, 2020 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, 2020 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, 2020 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, 2020 at 15:46
  • $\begingroup$ Makes sense. Thank you! $\endgroup$
    – Fiono
    Oct 25, 2020 at 15:57

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.