A Brief Introduction to Zero-knowledge proof of knowledge.

Hi!

Zero-knowledge proof (Zkp) was firstly introduced by Goldwasser, Micali, and Rackoff. Goldwasser firstly apply zkp on Quadratic residue (QR). She took 3 year to prove QR with the help of zero knowledge. Finally in 1985, Goldwasser gave zero-knowledge proof of knowledge to complexity theory as well as cryptography. 

Lets discuss about proof. 

Proof: Once upon a time a student ask from Shimon even regarding what is proof. A beautiful definition introduced by Shimon in his graph theory class is:

        "A proof is whatever convinces me".

Important Note1: In cryptography whenever we send something to the receiver then it's a nature of receiver that it apply all the possible case for neglecting that message because receiver always want to accept the true message. That's why receiver try all the possible case to check the correctness (that is honest nature) of any message. Remember if message is correct than receiver always accept it. 

Interactive Proof: For showing any process is interactive. Consider two turing  machines say P and V. We have one claim (x) and language L ∈ NP such that it follows the two axioms:

1. Completeness: for every x ∈ L, such that 

        Pr[(P,V)(x) = 1] >= 2/3.

2. Soundness: for every x ∉ L, such that

        Pr[(P*,V)(x) = 1] <= 1/3 

Important Note2: Anything that is feasible computed by zkp can also be feasible computed by itself. 

Why there is a need of Zero-Knowledge proof : In interactive proof, during the interaction prover can share some secret information to the verifier that is not necessary. In case of zkp, prover never shares the secret information, it always convinces the verifier regarding the particular assertion. In zkp, both prover and verifier gets zero knowledge before the interaction as well as after the interaction. 

Additionally, zkp consists:

a. Auxiliary inputs.

b. mandating universal and black box simulator. 

c. considering honest (or semi-honest) verifier.

d. level of similarity required of the simulator.

One-way Function: 

A function f: {0,1}* --> {0,1}* is called one way if following two condition satisfied. 

1. Easy to evaluate: There exist a polynomial time algorithm A such that A(x) = f(x).

2. Hard to invert. There exist a family of polynomial time circuits {Cn}, every polynomial p, and sufficiently large n, such that

        Pr[Cn(f(n) ∈ f'(f(n))] < 1/p(n)   (where f' is the inverse of function).

Computational Indistinguishability:

In modern cryptography the central notion is about effective similarity. In cryptography we are not more conscious about the how identical are the two objects moreover we are more conscious about the difference between the two ensembles ( may be any thing) are negligible. 

We assume that X and Y are two ensembles where {Dn} be the family of polynomial size circuits then

        |Pr[Dn(X) = 1] - Pr[Dn(Y) = 1]| < 1/p(n).

Zero Knowledge Proof of Knowledge:

An interactive strategy A is zk on (inputs from) set S if for every feasible (interactive) strategy B*, there exist feasible (non-interactive) strategy C* such that the following two ensembles are computationally indistinguishable.

1. {(A, B*)(x)} : the output of B* after interacting with A on common input x selected from set S.

2. {C*(x)}: the output of C* on input x (this is also known as stand alone simulator). 

Zero Knowledge Proof of Knowledge (with auxiliary inputs):

Consider the following two ensembles are computationally indistinguishable:

1. {(A, B*(z))(x)}

2. {C*(x,z)}

Important Note3: Knowledge tightness means how much hard work has to be done by the verifier to validate any assertion without interacting with the prover. 

Strict vs Expected Probabilistic Polynomial Time (PPT):

Strict PPT: There exist a bound on the number of steps in each possible run of the machine, regardless of the outcome of its coin tosses.

Expected PPT: Standard approach is to look at the running time as a random variable and bound its expectation.

Important Note4: We always consider zero-knowledge proof with auxiliary inputs.

Remark: Here we remark that all languages that belongs to the category of NP  (non-deterministic polynomial time) always follows the zero-knowledge proof. 

Zero-Knowledge proof of Graph 3-Colorability:

1. Common inputs: Consider a graph G(V,E). suppose V = {1,2,...,n}, and n=|V|.

2. Auxiliary input (to the prover): A 3-coloring f: V--> {1,2,3}.

The following steps are repeated t.|E| many times to obtain soundness error exp(-t).

P1: Select uniformly permutation π over {1,2,3}. For i = 1 to n sends commitments π(f(i)).

V1: Verifier randomly select an edge e from E and sends it to the prover. 

P2: on receiving edge e(i,j). decommit the i^{th} and j^{th} value and sends it to the veriifer.

V2: check whether or not if the decommitted values are different element of {1,2,3}. If different then accept else reject.