Zero Knowledge Proof of Knowledge

 Hi All !

Hope you all are doing great. !

This Blog is regarding Zero Knowledge Proof. The advance research in the area of Blockchain and Cryptographic Algorithm makes this concept very dominant. 

Zero Knowledge Proof :

Let R be a polynomial time decidable binary relation. The corresponding language L which is patches of statements x such that there holds or exist witness w and (x,w) ∈ R. We specify L as an NP Language. 

Consider two entities P and V which is called as Prover and verifier term as zero knowledge proof if it has two mandatory Properties i.e. Completeness and Soundness. 

A. Completeness :  It means ∀x ∈ L, (P,V)(x) is always 1. 

B. Soundness  : It means ∀x ∉ L, every Prover P*, Pr[<P*,V>(x) = 1] is always negligible. 

Example : Consider two friends Kuk (Prover) and Goa (Verifier). Goa has color blindness. Goa has two identical apples but of different colors green and red he wants to give red apple to Kuk but due to color blindness he is confused. Then zero knowledge proof can be like this:

> Goa holds the apples in their hand and asks to the Kuk which apple is in which hand. Then Kuk gives the reply. Now Goa applies a strategy, behind their back he might be switch the apple or not switch the apple. Then he asks to the Kuk. If Goa not switch the apple then after listing the Kuk reply Goa may think Kuk is not may be right so he again repeat the step. Suppose Goa switch the apple and then he asks to the Kuk and kuk gives the correct reply then Goa thinks that now Kuk is right. So now Kuk and Goa can eat the apple. 😀

This entire procedure is term as Zero Knowledge Proof.


We have seen the apple case so it might be possible that the convincing time is very large. Zero Knowledge Proof is of further two types .Interactive ad Non- Interactive. 

1. Interactive Zero Knowledge Proof : It means Prover and Verifiers interacts several time until they got the success.

2. Non- Interactive Zero Knowledge Proof : It means Prover and the verifiers interacts very minimum time say one and on the behalf of one interaction they give their decision. 

Now lets us understand this concept with the help of One example means how to apply the types of zero knowledge proof. 

Consider, 3-Colorable Graph. (Hope you know the concept of graph coloring and my favourite chromatic number. It means to color the entire vertices of a graph such that no two adjacent vertices have same color and the set of total number of colors should be minimum.)  

> Non-Interactive Procedure : Color the graph and permutate the colors to different possible sets if you find different sets after permutation then stop and return the graph is not 3 colorable. If not then pick an adjacent edge and note the color if the color is different then return 3 colorable else not 3 colorable. 

> Interactive Procedure : Color the graph and Permutate the color to different possible sets if finds different set then write not 3 colorable else pick an adjacent edge and not the color if same color then write not 3 colorable if not then pick another adjacent edge and write the color and repeats the procedure until you scan the entire edge. 

Note: In most research study, we apply non interactive zero knowledge proof due to complexity issue because if we apply interactive proof then it is time consuming but I think it is correct but time is major factor while executing any program so non interactive plays a dominant role.  

Hope You enjoy the beautiful Journey of Zero Knowledge Proof. You reading not stops here it is recommended to think different scenario and try to apply zero knowledge proof. If you have any doubt then fill the comment section. 😎


***************************************************************************************************************

Comments

Post a Comment

Popular posts from this blog

Homomorphic Encryption: A Basic Idea

Image
Homomorphic encryption has the same aim as other encryption-decryption mechanisms: maintaining confidentiality, security, privacy, etc.  In this blog, we will see homomorphic encryption and its type.  Homomorphic Encryption (HE):  It is an encryption that computes operations over encrypted data without decrypting it (or without the need for a secret key).  Mathematically speaking in a client-server architecture: client has message 'm' and function f. The task of client is to compute f(m). Due to computational expensiveness (maybe one of the reason) client sends encryption of message (say Enc(m)) and 'f' to the server. Server will compute function over encrypted message, that is, f(Enc(m)), and return the result to the client, that is, Enc(f(m)). Client will decrypt it Dec(Enc(f(m)), that is, f(m). Hence, client achieves f(m).  Let's understand HE with our daily life (Tea making process): Figure 1. Here m is message, Enc is encryption, f is function, and Eval in...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more

Brakerski-Fan-Vercauteren (BFV) Homomorphic Encryption

Image
Homomorphic encryption means computation over encrypted data without secret key.  How this is possible  ?? 😴 In this blog, we will explore the types of Homomorphic Encryption and demonstrate how computations can be performed on encrypted data without the secret key. In 2009, Gentry proposed Fully Homomorphic Encryption. In 2012, Brakerski proposed a leveled homomorphic encryption scheme that works over integer arithmetic, which later became known as the BFV scheme. BFV is an encryption scheme. Thus, as an encryption scheme, it is expected to be secure. To date, under certain conditions, it is assumed that the scheme is safe, and its security is based on the Learning With Errors (LWE) assumption.. Learning-with-error (LWE): Given a pair of a, b and the task is to recover secret key (s), such that b = a.s  + e  Here e is error mostly picked from gaussian distribution, and a, s are selected from Rq (known as ring module R) The above problem is HARD. The proof is not si...
Read more