Various Notions of Interactive Zero-Knowledge proof with an Open problem.

 Hi Folks!

Before reading tis blog, i hope you have checked my previous blog on Zero knowledge proof of knowledge. 

Directly jumping to zero knowledge notions we first discuss ensembles. 

Ensembles: It is a probability distribution. 

Example: {Xn}n ∊ I, where I denotes countable set. 

Going back to your high school a a countable set is those set whose bijection is possible with the set of natural numbers (as you know set of integers is countable: positive integers maps to even natural number and negative integers maps to odd natural numbers).

Random variable: It is a function whose outcome is an event from sample space.

Now, come to agenda of this Blog. 

Zero Knowledge proof of knowledge: We say that an interactive proof system (P, V) for a language 'L' o input "x" is zero knowledge if whatever can be efficiently computed after interacting with P can also be computed by "x" itself (without interaction). 

Keep remember that zero knowledge is a property of prescribed prover. 

As we know the condition of prescribed prover exists in case of completeness (which we generally think in a way for one prover there exist one verifier). 

1. Perfect Zero knowledge proof of knowledge (strict version).

Let (P,V) be an interactive proof system. We say that (P,V) especially P is perfect zero knowledge proof of knowledge if for every probabilistic polynomial time (PPT) interactive machine V* there exist an (ordinary) PPT algorithm M* such that the following two distribution are identically distributed. 

. (P,V*)(x) (i.e., output of interactive machine V* after interacting with the interactive machine P on common input x).

. M*(x) (i.e., the output of machine M* on input x).

Here the presence of simulator means that V* does not gain any knowledge from P (since the same output could be generated without any access to P).

2. Perfect Zero Knowledge proof of Knowledge (PZK).

The above definition of PZK is quite strict we relax this definition by bound on the simulator. 

The need of relax version is that because every language in BPP has a perfect zero knowledge in which the prover does nothing (and the verifier checks by itself whether to accept or reject the common input).

Let (P,V) be an interactive proof system for some language L. We say that (P,V) is PZK if for every PPT interactive machine V* there exist a PPT algorithm M* such that for every x ∊ L the following two conditions holds:

. 1. With probability at most 1/2  , on input x, machine M* output's a special symbol denoted 丄 (i.e., Pr[M*(x) =丄]<= 1/2).

2. Let m*(x) be a random variable describing the distribution of M*(x) conditioned on M*(x) != 丄. The following two distribution are identically distributed:

. (P, V*)(x)

. m*(x) (i.e., the output of machine M* on input x, conditioned on being 丄). 

Machine M* is called a perfect simulator for the interaction of V* with P.

3. Perfect Zero Knowledge, Liberal Formulation.

We say that (P,V) is PZK in liberal sense if for every PPT machine V* there exist an expected polynomial time algorithm M*, s.t. for every x belongs to L the random variable (P,V*)(x) and M*(x) are identically distributed. 

Still we always use PZK because in case of liberal formulation we are using expected polynomial. It means consider a function on average which is linear growth but if you square that function then the expected growth of that function is exponential. 

4. Computational Zero Knowledge proof of Knowledge (CZK).

The definition remains same as per the PZK but the following two distributions are computational indistinguishable. 

. {(P, V*)(x)}x ∊ L

. {M*(x)}x ∊ L

Here {.} denotes the ensembles. 

What is the difference between strict perfect and computational.

Ans: In case of perfect we are taking identically distributed but in case of computational we are taking computational indistinguishable. Although, sounds same then think in a way, in case you are consider about computational we are talking about ensembles.

5. Alternative Formulation of Zero Knowledge.

 It considers the verifier's view of interaction with the prover. Verifier's view means the entire sequence of local configuration of the verifier during an interaction with the prover. 

ViewPV*(x) a random variable describing the content of random tape of V* and the message receives from P during a joint computation on common input x.

We say that (P,V) is zero knowledge such that the ensembles {ViewPV*(x)}x ∊ L and {M*(x)}x ∊ L are computational indistinguishable. 

6. Almost Perfect (Statistical) Zero Knowledge (SZK).

If for every PPT interactive machine V* there exist a PPT algorithm M* such that the following two ensembles are statistical close as function of |x|.

. {(P, V*)(x)}x ∊ L

. {M*(x)}x ∊ L

7. Honest Verifier Zero Knowledge proof of knowledge.

This is a weak notion of zero knowledge. It requires simulatability of the view of only the prescribed verifier, rather than simulatability of the View of any possible verifier. 

We say that (P,V) is honest-verifier zero knowledge if there exist a PPT algorithm M such that the ensembles{ViewPV(x)}x ∊ L and {M*(x)}x ∊ L are computationally indistinguishable. 

Complexity Based on ZKP

BPP ⊆ PZK ⊆ SZK ⊆ CZK ⊆ IP

Assuming the existence of one-way function, the last inclusion is an equality (i.e., CZK = IP)

Then our belief is that 

BPP ⊂ PZK ⊆ SZK ⊂ CZK = IP

Open Problem: The relationship of PZK and SZK remains an open problem (with no evidence in either way).