# How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$

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!

-

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$?

-
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? –  statham Feb 28 '12 at 1:32
@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. –  poncho Feb 28 '12 at 4:05
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? –  statham Feb 28 '12 at 4:26
@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 –  poncho Feb 28 '12 at 15:20
oh yes now all pieces are put together... Thanks! –  statham Feb 28 '12 at 18:40