Sigma (Σ) - Protocol

Hope you enjoyed the Journey of Zero Knowledge Proof. Before, enjoying this blog it is recommended for user to study zero knowledge Proof (https://akshitaggarwaliiit.blogspot.com/2022/03/zero-knowledge-proof-of-knowledge.html) and then study the sigma (Σ) Protocol. 

Sigma Protocol is basically a way to obtain efficient Zero Knowledge. 

Sigma Protocol Template : 
    . Common Input : P and V both have x. 
    . Private Input : P has w such that (x, w) ∈ R. 

    . Three Round Protocol : 
        . P sends a message a. 
        . V sends a random t-bit string e.
        . P sends a reply z. 
        . V accepts based solely on (x, a, e, z). 

    . Completeness : As usual in Zero Knowledge (ZK).

    . Special Soundness : There exist an efficient extractor A that given any x and pair of transcripts (a, e, z), (a, e', z') with e ≠ e' outputs w such that (x, w) ∈ R.

    . Special Honest-Verifier ZK : There exists an efficient simulator S that given any x and e outputs an accepting transcripts (a, e, z) which is distributed exactly like a real execution where V sends e. 

Note: Symbol Specification. 

P : Prover, V : Verifier, w : witness, x : statement/query, e : String, R : Relation.


Properties of Sigma Protocol : 

    . Any Σ - Protocol is an interactive proof with soundness error 2-t
    . Properties if sigma protocol are invariant under parallel composition. 
    . Any sigma protocol is a proof of knowledge with error 2-t 
        . The difference between the probability that P* convinces V and the probability that an extractor K obtains a witness is at most 2-t
    . Proof needs some work.

Now we just seen the Basic understanding of Sigma protocol but I believe we should need some example for better clarity. 

So It is recommended for user to firstly think about the different scenario and then go to the the below text. 😊

Here I am going to take the example of Schnorr's discrete logarithmic, Hope you have basic understanding regarding Schnorr's algorithm if not then don't worry  you will easily understand with the help of below example. 

An Example – Schnorr’s Protocol for Discrete Logarithmic:

  . Let G be a group of order q, with generator g.

  . P and V have input h ∈ G. P has w such that gw = h.  

  . P proves that to V that it knows DLOGg(h).

         . P chooses a random r and sends a = gr to V.

         . V sends P a random e ∈ {0, 1}t

         . P sends z = r + ew % q to V.

         . V checks that gz = ahe.

  . Correctness: gz = g(r+ew) = gr(gw)e = ahe.

  . Proof of Knowledge:

         . Assume P can answer two queries e and e’ for some a.

         . Then, it holds that gz = ahe, gz’ = ahe’.

         . Dividing the two equation gives g(z-z’) = h(e-e’).

         . Therefore, h = g(z-z’) / (e-e’).

         . That is: DLOGg(h) = (z-z’) / (e-e’).

  . Conclusion:

         . If P can answer with probability greater than 1/2t, then it must know the discrete log.


Hope you enjoyed the basic information regarding Sigma Protocol. It is recommended to think about some other test cases . 
 Hope you enjoyed the below task : (Think and solve by yourself). 

Task 1 : Apply Sigma Protocol on K out of n Secret Sharing. 

If you have any doubt 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