1
$\begingroup$

I am looking into various one way functions and I stumbled upon a Rabin function, which is squaring modulo an RSA modulus $N=pq$, where $p,q$ are prime: $R_N(x) = x^2 \mod N$.

Would it lose the one-way property if $N$ is prime and not a product of two primes?

UPD: Also, is Rabin function still one-way if factorization of $N=pq$ is known?

$\endgroup$
3
  • 1
    $\begingroup$ Yes, it's the Tonelli-Shanks algorithm (special cases here). (Checking right now whether somebody asked about this here before). $\endgroup$ – SEJPM Jan 6 at 9:48
  • $\begingroup$ @SEJPM "Yes" is confusing here, because the questions in the title and body of the question are opposites of each other. $\endgroup$ – Maeher Jan 6 at 9:54
  • $\begingroup$ Let me update the question $\endgroup$ – bazzilic Jan 6 at 9:54
3
$\begingroup$

Would [$f_N(x)=x^2\bmod N$] lose the one-way property if $N$ is prime and not a product of two primes?

Yes, thanks to the Tonelli-Shanks algorithm (special cases here).

[Is] Rabin function still one-way if factorization of $N=pq$ is known?

No, because the main ("only") information advantage the private key holder has in the Rabin cryptosystem over the public key holder is the factorization of $N$. If the one-wayness was preserved even under known factorization the system wouldn't allow decryption in its normal form.

The way to see how factorizing allows square roots in this scenario is to remember that the chinese remainder theorem establishes a ring isomorphism between $\mathbb Z_N$ and $\mathbb Z_p \times \mathbb Z_q$ ... and as established above we know how to compute square roots in $\mathbb Z_p$.

$\endgroup$

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.