Basics of Non-interactive Zero-knowledge Proof of Knowledge

 Hi folks!

Till now, we have only discussed about interactive proofs. Interactive proofs are bi-directional but non-interactive proofs are monodirectional.

Non-interactive Zero Knowledge (NIZK) proofs consists of three entities, i.e., Prover, Verifier, and random sequence of bits. Prover and Verifier both can read the random string and have their own additional coin. In case of NIZK, Prover sends message to Verifier, who then is left with the decision (whether to accept or reject).

Let's discuss with a story.  Assume Alice and Bob are two friends. Alice loves mathematics. Alice always write some mathematics claim and sends it to the Bob. Bob always verifiers the Alice's claim.                    Now consider a tricky scenario. Besides mathematics Alice loves travelling. So, she went on a world tour. During her tour she wrote a claim of mathematics and send it to Bob's address. Bob now verifies it but Bob cannot give it's verification result to Alice (Because Alice is on world tour and Bob has no address of Alice). This process is known as non-interactive process. 

Non-interactive Proof. 

Both Prover and Verifier are ordinary probabilistic machine that, in addition to common input, also get a uniformly distributed string. 

A proof of probabilistic machine (P, V) is called non-interactive proof system for a language L if V is polynomial time and the following two axioms holds:

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

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

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

        Pr[V(x, R, B(x, R))=1] <= 1/3 

where x is claim, R is random variable uniformly distributed in {0,1}^poly(|x|).

Non-interactive Zero-knowledge Proof (NIZK).

A non-interactive proof system (P, V) for language L is zero knowledge if there exist a polynomial p and a PPT algorithm such that the ensembles {(x, U_p(|x|), P(x, U_p(|x|)))}_x ∈ L and {M(x)} _x ∈ L are computational indistinguishable, where U_m  is a random variable uniformly distributed over {0,1}^m. 

Construction of NIZK.

NIZK is designed with the help of hidden bit model. In this model common reference string is uniformly selected as before, but only the Prover can see all of it. 

Prover sends certificate and sequence of random bit string. Verifier receives it and check the bit location that is specified by the prover. 

Hidden Bit Model.

A pair of (P, V) probabilistic machines is called a hidden bits proof system for L if V is polynomial time and following two condition holds:

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

        Pr[V(x, R_I, I, π) = 1] >= 2/3.

Here (I, π) = P(x, R)

2. Soundness: for every x ∉ L, and every algorithm B,

        Pr[V(x, R_I, I, π)=1] <= 1/3 

Here (I, π) = B(x, R)

R is a random variable uniformly distributed in {0,1}^poly(|x|), and R_I is the sub string of R at position I is a subset of {1,2,...poly(|x|)}. That is R_I= r_i1, r_i2, …, r_it, where R = and I=(i₁, i₂, …, i_t).

In both case, I is called the revealed bits, π is certificate. 

Zero knowledge is defined as before, with the exception that we need to simulate 

(x, R_I, P(x, R)) = (x, R_I, I, π) rather (x, R_I, P(x, R)).

From Hidden Bit Proof System to Non-interactive Ones.

Suppose two functions f: {0,1}* --> {0,1}*, and b: {0,1}* --> {0,1} are polynomial time computable. Furthermore, m =poly(n) denote the length of common reference string for common inputs of length n, and suppose that f is one-one and length preserving.

. Common input: x ∈{0,1}ⁿ.

. Common reference string: S = (s₁, s₂,…,s_m), where each s_i is in{0,1}ⁿ .

. Prover (denoted P'):

1. Computes r_i= b(f^-1(s_i)) for i = 1,2,..m.

2. invokes P to obtain (I, π) = P(x, r₁, r₂, …, r_m).

3. Outputs (I, π, p_I), where p_I = (f^-1(s_i),.., f^-1(s_it))  for I = (i₁, i₂, …, i_t).

. Verifier (denote V'): Given the prover's output (I, π, (p_i,....p_t)), the verifier

1. Checks that S_ij= f(p_j) for each i_j belongs to I (in case mismatch found, V' halts and reject).

2. Computes r_i= b(p_i), for i = 1,..,t. Lets r =r₁, r₂, …, r_t.

3. invokes V on (x, r, I, π) and accepts if and only if V accepts.