4
$\begingroup$

Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form?

This is actually a homework problem with a hint that if a $n = p^a$$q^b$ then exactly half of the elements in $Z_n$ with jacobi symbol +1 are quadratic residues mod n and we assume that initially verifier knows a quadratic non-residue x with jacobi symbol +1.

I stuck there because it seems extremely difficult to convince Verifier that n is of given form. It is not simply like after Verfier sends a challenge number to Prover and Prover shows that he knows the fact that if the challenge number is QNR or QR. For me to convince Verfier all jacobi +1 elements have to be generated in $Z_n$ and Prover has show that exactly half of them are QR. (Assume that Verifier can generate with x itself thus it does not violate Zero knowledge. But I am not sure if it is easy(polynomial time consuming) to generate all Jacobi +1 elements yet. Well it is true that if we let $z = r^2$ for a randomly picked r from $Z_n$ then $y = r^2x$ is also a QNR with jacobi symbol +1... So finding another QNR with jacobi symbol +1 is easy for verifier... ) But To show "exactly half" then Prover will need to show which one is QR and which is are QNR then it will violate Zero knowledge property since V is not suppose know that. But any other way to show "exactly half"?

Any hint or help is greatly appreciated. Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Actually, it is not necessary for the prover to show that "exactly half" of elements with Jacobi symbols being +1 are, in fact, QR. Instead, here are some hints:

  • Assuming that n is not of that form (and also n is not of the form $n = p^a$, which is easy test for), the probability that a random element with Jacobi symbol +1 is a QR is at most $q$ (homework assignment for you: what is the value of $q$)

  • If we get a value $x$ from the verifier which is a QR, how can we show in a zero knowledge way that $x$ is a QR (with probability $> 1 - \delta$)?

  • If the provider gives us a series of random $x$'s, and we either respond to each $x$ with 'not a QR', or 'it's a QR; here's the zero knowledge proof with probability $> 1 - \delta$', how many trials with random elements would be needed before the verify can conclude (with probability $> 1 - \epsilon$) that the fraction of Jacobi symbol +1 elements which are QR are $> q$?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your help very much. But at your 3rd point I am a bit confused about the role of provider. Is it actually verifier that randomly picks a series of $x$'s? But if that is the case and we reply that "not a QR" or "it's a QR" then it won't be zero knowledge right? $\endgroup$
    – statham
    Feb 28, 2012 at 1:32
  • $\begingroup$ @statham: Yes, I typo'ed it, and wrote "provider" when I meant "Verifer". However, despite the protocol leaking whether a number is a QR, it would still appear that this is technically "Zero Knowledge", in the sense that the Verifier could build a simulator that, without knowing any of the properties of n, could still generate a transcript that is indistingushable from a transcript of a valid proof. $\endgroup$
    – poncho
    Feb 28, 2012 at 4:05
  • $\begingroup$ Yes ZK for QR and QNR can be easily simulated but that is a bit wired to me in a sense that Verifier will not know which zero proof to use for a random x .. So you mean in the simulator verifier randomly picks a x and he tosses a coin. if coin = 0 then he uses simulator of ZK proof about x being QNR. and if coin = 1 he uses that for x being QR? $\endgroup$
    – statham
    Feb 28, 2012 at 4:26
  • $\begingroup$ @statham: well, it is not weird at all if the simulator makes assertions that it does not know whether they are true. Of example, the simulator will be asserting that n had two prime factors; it need not know that (and must produce a valid-looking transcript even if that is not true). BTW: the simulator needn't produce a ZK proof that a number is QNR; all the simulator needs to simulate is that a sufficient number of the values are QR. Also, as for leaking the factor that verifier-chosen numbers are QR; that is easy to fix; we just need a way to select x values that neither side can control $\endgroup$
    – poncho
    Feb 28, 2012 at 15:20
  • $\begingroup$ @statham: Would you like to condense the result obtained in the comments here into a new answer? $\endgroup$
    – Paŭlo Ebermann
    Apr 29, 2012 at 21:09

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.