Problem related to the discrete logarithm problem

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$$?

• Usually one can prove this by reducing the problem into Dlog. What is the source of this problem? What did you try? – kelalaka Oct 24 '20 at 17:10
• 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 – Fiono Oct 24 '20 at 17:30
• Where did you see this problem, homework, exercise, article, while doing research, etc? You should indicate it, right? – kelalaka Oct 24 '20 at 17:32
• 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. – Fiono Oct 24 '20 at 17:47

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

• 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... – Fiono Oct 24 '20 at 19:39
• @Fiono: actually, if you can solve the CDH problem without solving the DLog problem, you can compute $J$ without knowing $x$ – poncho Oct 24 '20 at 21:25
• 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? – Fiono Oct 25 '20 at 12:01
• @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... – poncho Oct 25 '20 at 15:46
• Makes sense. Thank you! – Fiono Oct 25 '20 at 15:57