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$?
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$– kelalakaOct 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$– FionoOct 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$– kelalakaOct 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$– FionoOct 24, 2020 at 17:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
-
$\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$– FionoOct 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$– ponchoOct 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$– FionoOct 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$– ponchoOct 25, 2020 at 15:46
-