# Blum primes [x=3(mod 4)] zero knowledge proof?

Lets say we have 2 primes, $p \equiv q \equiv 3 \pmod{4}$, and we make $n=p \times q$ public.

I can, without revealing factors, show that $n$ has two prime factors. How can i zero knowledge prove that those are Blum primes, as described before?

• By examining the 2 lsb of n. What are the possible combinations between all the primes composing the modulus ? – Robert NACIRI Mar 25 '15 at 20:41
• "I can, without revealing factors, show that n has two prime factors" -- how? I'm not aware of any way to do this. Using MPC to jointly produce a modulus is the approach that comes closest to achieving this. – CodesInChaos Mar 26 '15 at 9:48

I believe a zero knowledge proof that $-1$ is a quadratric nonresidue would accomplish that.
If we know that $n$ has two prime factors, and that $n \equiv 1 \pmod{4}$, then $n$ is either a product of two primes both $1 \bmod 4$, or two primes both $3 \bmod 4$.
If it were the former, then $-1$ is a QR modulo $p$, and $-1$ is a QR modulo $q$, and hence $-1$ is a QR modulo $pq$.
On the other hand, if $p \equiv 3 \bmod 4$, and $-1$ is a QNR modulo $p$, and hence a QNR modulo $pq$.
As for how to implement a zero knowledge proof that $-1$ is a QNR, see this paper