2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Does it miss a $\mod$ ? $\endgroup$
    – Ievgeni
    Jul 1, 2021 at 8:08
  • $\begingroup$ That is right. I've made the corrections. $\endgroup$
    – Sean
    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
    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
    Jul 1, 2021 at 19:55

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.