3
$\begingroup$

It is well known that both $g^x$ and $x^2$ are computational hardness problems in certain rings. But I wonder if the composition of them is still hard? Namely, given $(g, g^x, x^2)$ in a ring $Z_n$ where $n$ is a composite number of secret factorization, is it hard to get $x$?

$\endgroup$
  • $\begingroup$ You have to be careful, $x^2$ is 'hard' only in certain rings (such as $\mathbb{Z}_n$, where $n$ is a composite of secret factorization). $\endgroup$ – poncho Mar 13 '18 at 14:14
  • $\begingroup$ Thanks for the reminder. I have modified the description of the problem. $\endgroup$ – Colin Lee Mar 13 '18 at 14:21
1
$\begingroup$

This is essentially equivalent to factoring $n$.

From the composition you have given it is obvious that this is at most as hard as the easier of the two instances of the hard problems. So let's look at both of them.

Computing square roots over composite rings. This one is known to be equivalent to factoring the ring modulus.

Computing discrete logarithms over composite rings. This one is more intriguing. It is known that if you can compute prime-based discrete logarithm (for all the prime factors) and factor, then you can compute the discrete logarithm over the composite ring. It is also known that if you can compute the discrete logarithm over composite rings, then you can factor the modulus.

If you wanted the composition to be more like "you need to break both instances", then you should formulate it as, "given $(g,g^y,x^2)$ with $x,y\in\mathbb Z_n$ with $n$ having a secret semi-prime factorization, find $(x,y)$".

$\endgroup$
  • $\begingroup$ Thank you. But I think that you do not really answer my question. What I mean is that whether $x^2$ can give more information for solving $g^x$, or whether $g^x$ can make solving $x^2$ easier. Namely, I want to know of if we reveal both $g^x$ and $x^2$ at the same time, will $x$ be revealed? $\endgroup$ – Colin Lee Mar 15 '18 at 12:31
  • $\begingroup$ Even though we can prove that solving $x^2$ is equivalent to factoring $n$, and that solving $g^x$ is equivalent to factoring $n$, to claim that $(x^2, g^x)$ is equivalent to factoring $n$ still needs formal proof. After all, we cannot ensure $g^x$ will not give more information for solving $x^2$. $\endgroup$ – Colin Lee Mar 15 '18 at 12:35
  • $\begingroup$ @ColinLee so what you actually want is an argument for the statement "(factoring is hard) -> (recovering $x$ given $x^2$ and $g^x$ is hard)" or "((recovering $x$ from $x^2$ is hard) /\ (recovering $x$ from $g^x$ is hard)) -> (recovering $x$ from $x^2$ and $g^x$ is hard)" (with the AND in the second one being essentially the same as "factoring is hard")? $\endgroup$ – SEJPM Mar 15 '18 at 17:39
  • $\begingroup$ Yeah. My original question is "((recovering x from $x^2$ is hard) /\ (recovering x from $g^x$ is hard)) -> (recovering x from $x^2$ and$ g^x$ is hard)", but I think a formal proof for "(factoring is hard) -> (recovering x given $x^2$ and $g^x$ is hard)" can also answer my question. $\endgroup$ – Colin Lee Mar 16 '18 at 3:19
  • $\begingroup$ @ColinLee I thought about this and the proof should go using contraposition, that is assuming you have an oracle that returns you $x$ from $(g^x,x^2)$ find an efficient way to factor $n$. However when writing the proof down I noticed I don't actually know how to construct an arbitrary $(g^x,x^2)$ without picking $x$ first, which is needed to turn this into the required DLP or SQRT oracle... $\endgroup$ – SEJPM Mar 16 '18 at 20:21

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.