# Usage of Zero-knowledge proofs for NP-complete languages

It is well known that if OWFs/PRGs exist, then there is a zero knowledge proof for any NP-complete language, say G3C (graph coloring in 3 colors). The zero-knowledge notion maintains that any malicious verifier that interacts with the prover can be simulated by a PPT algorithm (including the communication) and thus, doesn't gain any advantage from the prover's replies.

Yet, if a PPT algorithm can find a coloring in a graph with non-negligible probability (even without interacting with a prover), then the whole notion of zero-knowledge proofs for NP-Complete languages becomes useless!

Is there a distribution over graphs that enables generating graphs for which no PPT algorithm can find a 3-coloring in non-negligible probability?? (under the assumptions of P!=NP and OWF & PRGs exist). Or a distribution over graphs that enables generating graphs for which no PPT algorithm can determine if they are in G3C or not with non-negligible advantage? Otherwise I can't see how such a ZK proof can be beneficial.

• If you had a PPT algorithm that could find a coloring in a graph with nonnegligible probability, then you can likely use it to break AES (or RSA or EC); to find the setting of key bit i, generate two SAT instances, one with a solution if the bit is 0, and one with a solution if the bit is 1; convert those into G3C problems and hand both to your PPT algorithm. If it finds a coloring in one of them, then you know that bit setting. Because of this nonrigorous argument, it appears unlikely that any such algorithm exists (assuming $P \ne NP$) – poncho Aug 18 '15 at 20:27

In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP witness-finding question "what is a 3-coloring of this graph $G$?", by converting $y$ into a graph $G$ such that any 3-coloring of $G$ can be efficiently converted back to a preimage of $y$ under $f$.