5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$) $\endgroup$
    – poncho
    Aug 18, 2015 at 20:27

1 Answer 1

5
$\begingroup$

If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for. In short, just put the OWF through the Cook-Levin reduction.

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.