Let $x$ be a random element from $QR_n$, the quadratic residue group over Blum integer n (where $n=p*q$ and $p$ and $q$ are safe primes), and $g$ a generator of $QR_n$. Are the following computationally indistinguishable?

$$(x^2 \mod n, g^x) (r^2 \mod n, g^x)$$

The intuition is that it's hard to compute $x$ from $x^2$ and $g^x$. Could this be reduced to some standard assumptions?

  • $\begingroup$ Does it miss a $\mod$ ? $\endgroup$
    – Ievgeni
    Commented Jul 1, 2021 at 8:08
  • $\begingroup$ That is right. I've made the corrections. $\endgroup$
    – Sean
    Commented Jul 1, 2021 at 12:29
  • 2
    $\begingroup$ How is $x \in QR_n$ is represented? E.g. If it is sampled uniformly from $[0; n\cdot ord(g))$, then these are indistinguishable since $x^2$ and $g^x$ are independent (because $x \mod n$ and $x \mod ord(g)$ are independent). $\endgroup$
    – Fractalice
    Commented Jul 1, 2021 at 12:48
  • $\begingroup$ Thanks very much for the insights? What about x^2 \mod \totient(n) is given. Then I guess the argument wouldn't apply? $\endgroup$
    – Sean
    Commented Jul 1, 2021 at 19:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.