> A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key.
I don't think a digital signature is a Zero-Knowledge Proof because someone else could copy and paste the signature and then it would look like they know the key, and because other third parties could check whether the signature was valid or not.
To be a true Zero-Knowledge Proof it needs to:
* show that you know the thing without revealing the thing
* not allow other people to copy your answer
* not allow anyone other than your intended counterparty to even verify the answer
Are we sure that the base reveals nothing about the factors if n is composite? I have never seen a proof of that.
Usually, zero knowledge proofs also require a prover who knows the answer (the factors in this case). This is just a primality test that can be performed locally.
That's a very good question. It all depends on how you pick the witness b: there is a procedure that definitely is not zero-knowledge: say, if prover uses his knowledge of factorization to construct an explicit b that betrays that factorization.
For example, if n = p1*p2*...*pk is square-free and not a Carmichael number, then by Korselt's criterion there exists a pi such that pi-1 does not divide n-1 (this also implies that pi>2). Use the Chinese Remainder Theorem to produce b such that b=1 (mod pj) for all j!=i, and b (mod pi) is a generator of (Z/piZ)^*. Then b is a Fermat witness: gcd(b, n) = 1 (because b is non-zero modulo every prime factor) and b^(n-1) != 1 (mod n) because b^(n-1) != 1 (mod pi) (as pi-1 does not divide n-1).
However, b "betrays" the prime factorization of n, since gcd(b-1, n)>1 (by construction b-1 is divisible by all pj with j!=i, but not divisible by pi>2), and thus gcd(b-1, n) is a non-trivial factor of n. (I assumed square-free above but if pi^ei (ei>=2) divides n, then b=1+pi^(ei-1) (mod pi^ei), b=1 (mod pj^ej) (j!=i) also would have worked.)
On the other hand, it is also known that for non-Carmichael numbers at least half of the bases b with gcd(b, n) = 1 are Fermat witnesses. So if you pick b uniformly at random, the verifier does not gain any new information from seeing b: they could have sampled such a witness themselves by running the same random test. Put another way, the Fermat test itself is an OK ingredient, but a prover who chooses b in a factorization-dependent way can absolutely leak the factors - the final protocol won't be ZK.
My understanding is that there is a difference between the concept of a Zero-Knowledge Proof (ZKP), and then the applications that such a thing is possible.
In the example given, I can prove that N is composite without revealing anything (well, almost anything) about the factors. But in practice we want to use a ZKP to show that I have specific knowledge without revealing the knowledge itself.
For example:
You can give me a graph, and I can claim that I can three-colour it. You may doubt this, but there is a process by which I can ... to any desired level of confidence ... demonstrate that I have a colouring, without revealing what the colouring is. I colour the vertices RGB, map those colours randomly to ABC, and cover all the vertices. You choose any edge, and I reveal the "colours" (from ABC) of the endpoints. If I really can colour the graph then I will always be able to reveal two different colours. If I can't colour the graph then as we do this more and more, eventually I will fail.
So you are right, but the message of the post is, I think, still useful and relevant.
We also don't technically have proofs for some of the computational hardness assumptions that popular "real" ZK proof constructions rely on!
This might feel different because those assumptions were chosen in part because people had studied them and they certainly seem to be right, whereas perhaps here nobody has really studied this particular random number theory topic one way or the other.
But in some sense, there isn't a proof that regular ZK proof methods are actually completely zero-knowledge (against a computationally bounded adversary).
> A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key.
I don't think a digital signature is a Zero-Knowledge Proof because someone else could copy and paste the signature and then it would look like they know the key, and because other third parties could check whether the signature was valid or not.
To be a true Zero-Knowledge Proof it needs to:
* show that you know the thing without revealing the thing
* not allow other people to copy your answer
* not allow anyone other than your intended counterparty to even verify the answer
Are we sure that the base reveals nothing about the factors if n is composite? I have never seen a proof of that.
Usually, zero knowledge proofs also require a prover who knows the answer (the factors in this case). This is just a primality test that can be performed locally.
That's a very good question. It all depends on how you pick the witness b: there is a procedure that definitely is not zero-knowledge: say, if prover uses his knowledge of factorization to construct an explicit b that betrays that factorization.
For example, if n = p1*p2*...*pk is square-free and not a Carmichael number, then by Korselt's criterion there exists a pi such that pi-1 does not divide n-1 (this also implies that pi>2). Use the Chinese Remainder Theorem to produce b such that b=1 (mod pj) for all j!=i, and b (mod pi) is a generator of (Z/piZ)^*. Then b is a Fermat witness: gcd(b, n) = 1 (because b is non-zero modulo every prime factor) and b^(n-1) != 1 (mod n) because b^(n-1) != 1 (mod pi) (as pi-1 does not divide n-1).
However, b "betrays" the prime factorization of n, since gcd(b-1, n)>1 (by construction b-1 is divisible by all pj with j!=i, but not divisible by pi>2), and thus gcd(b-1, n) is a non-trivial factor of n. (I assumed square-free above but if pi^ei (ei>=2) divides n, then b=1+pi^(ei-1) (mod pi^ei), b=1 (mod pj^ej) (j!=i) also would have worked.)
On the other hand, it is also known that for non-Carmichael numbers at least half of the bases b with gcd(b, n) = 1 are Fermat witnesses. So if you pick b uniformly at random, the verifier does not gain any new information from seeing b: they could have sampled such a witness themselves by running the same random test. Put another way, the Fermat test itself is an OK ingredient, but a prover who chooses b in a factorization-dependent way can absolutely leak the factors - the final protocol won't be ZK.
My understanding is that there is a difference between the concept of a Zero-Knowledge Proof (ZKP), and then the applications that such a thing is possible.
In the example given, I can prove that N is composite without revealing anything (well, almost anything) about the factors. But in practice we want to use a ZKP to show that I have specific knowledge without revealing the knowledge itself.
For example:
You can give me a graph, and I can claim that I can three-colour it. You may doubt this, but there is a process by which I can ... to any desired level of confidence ... demonstrate that I have a colouring, without revealing what the colouring is. I colour the vertices RGB, map those colours randomly to ABC, and cover all the vertices. You choose any edge, and I reveal the "colours" (from ABC) of the endpoints. If I really can colour the graph then I will always be able to reveal two different colours. If I can't colour the graph then as we do this more and more, eventually I will fail.
So you are right, but the message of the post is, I think, still useful and relevant.
We also don't technically have proofs for some of the computational hardness assumptions that popular "real" ZK proof constructions rely on!
This might feel different because those assumptions were chosen in part because people had studied them and they certainly seem to be right, whereas perhaps here nobody has really studied this particular random number theory topic one way or the other.
But in some sense, there isn't a proof that regular ZK proof methods are actually completely zero-knowledge (against a computationally bounded adversary).
A much smaller simpler example would have been useful for us mere mortals.
Ok 6 is not a prime. 5=b is not a multiple of 6
5^(6-1) = 3125 mod 6 = 5 which is not 1. Therefore 6 cannot be prime.