0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ By examining the 2 lsb of n. What are the possible combinations between all the primes composing the modulus ? $\endgroup$ – Robert NACIRI Mar 25 '15 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$ – CodesInChaos Mar 26 '15 at 9:48
2
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.