Are we sure that the base reveals nothing about the factors if n is composite? I have never seen a proof of that.<p>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 <i>not</i> zero-knowledge: say, if prover uses his knowledge of factorization to construct an explicit b that betrays that factorization.<p>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).<p>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.)<p>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.
On a related note, I've often wondered what each congruence in the quadratic seive reveals. Once you have enough of them you can factor the number, but what does a partial set of congruences reveal?<p>Its a matrix problem, so each row could be reducing the degrees of freedom of something. But what? And in what space?
If:<p>a^2 = b^2 (mod m)<p>Then:<p>a^2 - b^2 = 0 (mod m)<p>(a + b)(a - b) = 0 (mod m)<p>So, (a + b) must be a multiple of one of the factors of m. And (a - b) must be a multiple of the other factor of m.<p>> I've often wondered what each congruence in the quadratic seive reveals.<p>Each congruence reveals that the sum of the bases (a plus b) contains a factor of m. And the difference of the bases (a minus b) contains another factor of m.<p>The only thing you have to watch out for is the trivial case when one of the factors you find through this method is "1" and the other factor is "m". That case isn't very helpful.<p>It's not that each congruence gives you new information. You only have to find one single non-trivial congruence. But the other (trivial) congruences you find along the way only reveal that 1*m=m, which you already knew.
> It's not that each congruence gives you new information<p>So it's not that each congruence gives you N bits of information, and you want kN bits in total. It's more like each congruence has a 1/k chance of giving you the full kN bits.<p>But in some information theory sense those are the same! Or concretely, if you were testing a large quantity of numbers in parallel, you would get information from each congruence.
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.<p>In the example given, I can prove that N is composite without revealing anything (well, <i>almost</i> 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.<p>For example:<p>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 <i>can't</i> colour the graph then as we do this more and more, eventually I will fail.<p>So you are right, but the message of the post is, I think, still useful and relevant.
Suppose the graph admits only 4+ colorings, but when attempting a 3-coloring it's possible for only one edge to be misaligned. Then (A) you need O(n_edges) calls to the oracle to gain any confidence about the 3-colorability of a 3-colorable graph (else you might be easily duped by the one misaligned edge), and (B) in so doing, you learn almost all of the structure of the graph (since you have way more random calls than there are edges).<p>Restating, not only is the ZK algorithm slow, but by the time you have confidence in the ZK proof you also have additional knowledge about the structure whose properties you're proving.
can you explain this a little better?
I can certainly explain it more, a question of "better" is debatable!<p>Here's the process:<p>(A) You give me a graph to 3-colour;<p>(B) I claim I can 3-colour it;<p>(C) You demand that I prove it;<p>(D) I colour it with colours ABC and cover the vertices;<p>(E) You point at an edge;<p>(F) I reveal the colours of the vertices at the ends of the edge;<p>(G) If I have coloured the graph then the colours revealed will always be different;<p>(H) We repeat this process with a permutation of the colours between each trial;<p>(I) If I'm lying then eventually you'll pick an edge where either the vertices are not coloured, or the have the same colour.<p>(J) This process reveals nothing about the colouring, but proves (to some level of confidence) that I'm telling the truth.<p>So ... what's unclear?<p>Instructions on how to email me are in my profile if you prefer ...
The key insight is that Colin can show you a red-green-blue coloring of the graph, and flip the whole graph secretly, so it's blue-red-green instead when you look at an individual section, but really the graph is yellow-pink-orange colored. Even after showing you all the intersections of the graph individually in the red green blue coloring to satisfy that he can 3-color it, you still have no idea what is yellow pink or orange on his copy of the graph.
We also don't technically have proofs for some of the computational hardness assumptions that popular "real" ZK proof constructions rely on!<p>This might feel different because those assumptions were chosen in part because people had studied them and they certainly <i>seem</i> to be right, whereas perhaps here nobody has really studied this particular random number theory topic one way or the other.<p>But in some sense, there isn't a proof that regular ZK proof methods are actually completely zero-knowledge (against a computationally bounded adversary).