FC08 Assignment 5

From Theory
Jump to: navigation, search

Back to CS 8803FC - Foundations of Cryptography. Spring 2008.

Problem 1: The role of randomness in interactive proofs.

(a) Prove that if <math>L</math> has an interactive proof system in which the verifier is deterministic, then <math>L\in NP</math>.

(b) Prove that if <math>L</math> has an interactive proof system, then it has one in which the prover is deterministic.

(c) Prove that if <math>L</math> has an interactive proof system in which the verifier never (not even with negligible probability) accepts a string not in the language <math>L</math>, then <math>L\in NP</math>.

Problem 2: Zero-knowledge proofs.

Considier the following proof for 3COL (the language of all 3-colorable graphs):

(1) The verifier sends commitments to <math>t</math> random edges <math>(i_1,j_1),...,(i_t,j_t)</math>.

(2) The prover sends commitments to <math>t</math> colorings of the graph, where each coloring is a random permutation of her original coloring at hand.

(3) The verifier reveals the <math>t</math> edges she committed to in round (1).

(4) For each <math>\ell=1,...,t</math>, the prover reveals the <math>\ell</math>'th coloring of the vertices <math>i_\ell,j_\ell</math>

(5) The verifer accepts if and only if all the colors are legal.

Prove that this is a zero-knowledge argument system with perfect completeness and negligible soundness (assuming <math>t\geq n^3</math>).

(Recall that an argument system is similar to a proof system, but where soundness is required to hold only against non-uniform PPT cheating provers.)