[raincole]

I've got another problem about this zero knowledge proof. The digital version doesn't make a lot of sense to me. It depends on the fact we don't have a fast integer factorization algorithm. But integer factorization is not proven to be NP-complete, and 3-coloring is NP-complete.

So isn't it possible that there is a polynomial time algorithm for integer factorization, but no polynominal time algorithm for 3-coloring, and therefore the "zero knowledge proof" actually reveals the answer?

[dmurray]

I think you're right, and integer-factorization is often used in these examples as a process that is hard to do but easy to verify. There are plenty of other processes that could be substituted in, e.g. reversing SHA256 hashes, that would likely be even less tractable to the target audience.

However, if P = NP, there is no process that works here - there's nothing that is hard to do but easy to demonstrate, and therefore no zero knowledge proofs exist.

Actually, that's not true either. It requires the definition that all polynomial-time algorithms run quickly and all superpolynomial ones run slowly. This is not an accurate definition for all practical problem sizes and this is where the analogies all break down. Polynomial vs nonpolynomial is more interesting to complexity theorists than "how many years would this actually take with a fast computer".

[taejo]

> However, if P = NP, there is no process that works here - there's nothing that is hard to do but easy to demonstrate, and therefore no zero knowledge proofs exist.

IIRC technically, there are zero-knowledge proofs for all statements in P: the proof is "prove it yourself", which the verifier can do because it's in P.