A Few Examples on Zero-knowledge Proof of Knowledge

Hi!

In this blog we will discuss a few examples that is based on zero-knowledge proof (zkp). To apply zero knowledge proof in any system we should ensure the following properties such as:
1. The strategy (claim) should belong to the category of NP class.
2. The strategy should be computational indistinguishable.
3. One-way function should exist.
4. Mandating the honest prover strategy.
5. Zero knowledge. (It means prover demonstrates the knowledge/solution of problem to the verifier without reveling the actual proof.) If all aforementioned properties satisfies then by default this also exists. 

Remark1. In this blog we remark that every strategy is interactive and every strategy does not guarantees the efficiency of protocol (efficiency may be in terms of round complexity, optimality, and many more). 
Here P1, V1, P2, V2 represents prover and verifier steps.

1. Zero-knowledge proof for COMPOSITE NUMBER.

Common Input: A number N.
Auxiliary Inputs: A composite number C = p*q (where p,q >=2)/

P1: Uniformly select a number π, and commit it.
V2: verifier randomly select σ ∈{0,1}.
P2: if σ=0 then send π to the verifier, else send C*π to the verifier.
V2: if σ=0, decommit it and check N^(π-1) ≡ 1(mod π) (if holds then reject else accept). Otherwise decommit C*π.

2. Zero-knowledge proof for K-VERTEX COVER.

Common Input: A graph G(V,E), where V={1,2,..n}.
Auxiliary Inputs: A set of vertices in G that form a vertex cover of size K (say C).

P1: Uniformly send random permutation π of vertices and commit it. 
V1: verifier randomly select σ ∈{0,1}.
P2: if σ=0 send and decommit π otherwise send C to the verifier.
V2: if σ=0, decommit π by checking |π| =K, vertex cover from graph G (accepts if decommitments follows). Otherwise accept.

3. Zero-knowledge proof for SAT.

Common Input: A Boolean expression φ.
Auxiliary Input: Set of literals ∈ φ, such that (say T).

P1: Prover sends random permutation π of literals and commit it. 
V1: Verifier randomly sends σ ∈{0,1}.
P2: if σ=0, prover send π by revealing it's decommitment , otherwise send T and decommit it.
V2: if σ=0, decommitment π, accept if and only if φ=1. Otherwise accept.

4. Zero-knowledge proof for TREE_DECOMPOSITION.

Common Input: A graph G(V,E).
Auxiliary Input: A valid tree decomposition graph δ.

P1: Prover sends a random permutation π of bags and commit it.
V1: Verifier randomly sends σ ∈{0,1}.
P2: if σ=0, prover send π by revealing it's decommitment. Otherwise, send δ.
V2: if σ=0, decommitment π, accept if and only if all decommitment follows the protocol. otherwise accept. 

Comments

Post a Comment

Popular posts from this blog

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 ...
Read more

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:  {X n } 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 knowle...
Read more