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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ By examining the 2 lsb of n. What are the possible combinations between all the primes composing the modulus ? $\endgroup$– Robert NACIRICommented Mar 25, 2015 at 20:41
-
1$\begingroup$ "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. $\endgroup$– CodesInChaosCommented Mar 26, 2015 at 9:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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
