Here I overconfident in myself state that I can show, that n has two factors.

This is not completely true, can possibly show $n$ is composite - prover generates RSA key with modulo $n$, and gives $e$ to verifier.

Verifier takes random number $x$, and checks if $x^{e*d}=x$, where $d*e=1$ (mod $n-1$). If it is, then $n$ is prime, if not $n$ is composite and has factors.

Verifier sends $x^e$ to prover, and if prover sends back $x$ we can be sure that prover has factors of $n$. This doesnt, however garanties that there is just two factors.

How to prove-verify that there is only two factors in $n$?

UPDATE: This is not zeroproof, it is interactive here as was pointed in comments. Well, then. Question becomes more broader - can (duh) show that $n$ is not a prime. How to show it has two factors, zero knowledge, without interactivity?

  • $\begingroup$ "This doesnt, however garanties that there is just two factors." It's also not zero knowledge: a simulator without access to the prover would be unable to compute $x$. $\endgroup$ – fkraiem Mar 27 '15 at 17:54
  • $\begingroup$ yea, had a feeling i miss interactivity here, thanks $\endgroup$ – Timo Junolainen Mar 27 '15 at 17:57
  • $\begingroup$ Actually, there is no need for a ZKP that $n$ is not prime; anyone can verify that directly in polynomial time. $\endgroup$ – poncho Mar 27 '15 at 18:01
  • $\begingroup$ yes, but to show that there is no more, no less than two factors? $\endgroup$ – Timo Junolainen Mar 27 '15 at 18:03
  1. Firstly, convince the verifier that $n$ is not a prime number. (Prime is in P)

  2. Use Zero-Knowledge Proof to make sure that $n$ has no square factor (no $p^2|n$)

    See this paper Practical zero-knowledge proofs: Giving hints and using deficiencies for details.

  3. Showing that $n$ has exactly two factors: if not, the number of quadratic residues is roughly less than $1/8*n$. Verifier just randomly chooses a value y and ask prover to prove whether y is quadratic residue.

    If the probability is roughly $1/4$, then accept. Verifier can't cheat since he can only compute the quadratic residue, and let the probability raise, but not decrease below $1/8$.

| improve this answer | |
  • $\begingroup$ How one does the 1. $\endgroup$ – kelalaka Nov 5 '18 at 11:45
  • $\begingroup$ Since it's in P, the simulator of zero-knowledge proof can perfectly simulate step 1. But step 3 is incorrect. Zero-knowledge proof requires if it's true, then verifier can accept it with probability 1, but in my proof, we can only do it with high probability. $\endgroup$ – mignonjia Nov 6 '18 at 12:13
  • $\begingroup$ this is not zero knowledge, verifier learns if y is quqdratic residue for many y $\endgroup$ – Meir Maor Nov 6 '18 at 19:43

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.