Some notes about Zero Knowledge Proof - ZKP

How to prove to a color-blind person that 2 balls have different colors?

Suppose that you have 2 balls that are blue and red. You want to show a color blind person that they are two different colors. Here are the proof steps:

• First put 2 balls in front of the person and tell him that those 2 balls are in different colors. Of course, to color blind people, these two balls are identical.

• You let this person hide the two balls behind his back so you can't see them anymore. This person has the right to swap the two balls or not between his or her hands.

• Then this person challenges you by holding out a ball in the left or right hand and asking you whether he swaps the balls.

• Of course, if the balls are in the same color, you can not answer exactly. If you can always answer correctly this means the two balls are different colors.

The above proof is zero-knowledge because the person never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.

Properties of ZKP

• Completeness: If the statement is true, the verifier will be convinced (the verifier might challenge the prover more than 1 time until he/she eventually be convinced)

• Soundness: If the statement is false, the prover can't trick the verifier (except with some small probability)

• Zero-knowledge: The verifier learns nothing beyond the validity of the statement. (No verifier learns anything other than the fact that the statement is true)

Interactive ZKP vs. Non-Interactive ZKP

Basically, there are 2 methods of ZKP: Interactive ZKP (IZKP) and Non-Interactive ZKP (NIZKP). The significant difference between those methods:

• IZKP: Interaction is required between Prover and Verifier.

• NIZKP: Evidence can be made available before proofing, then the Verifier can use this evidence to verify later.

A simple scheme for I-ZKP

Why verify \(v=t\) ?

$$\begin{align*} v &= g^r.y^c \mod p \\ v &= g^{x-cw}y^c \mod p = g^{x-cw}(g^w)^c \mod p= g^{x-cw}g^{cw} \mod p\\ \implies v&= g^{x-cw}g^{cw}\mod p = g^{x-cw+cw} \mod p=g^x \mod p = t \end{align*}$$

You can try the demo here.

We can utilise this scheme for authentication, for example, the password is \(w\) on the scheme. This scheme offers significant advantages in terms of security and user experience. Here are some key benefits in enhancing security:

• Protection against Password Leaks: allow users to prove their identity without revealing their actual password or any sensitive information. This eliminates the risk of passwords being stolen during transmission or storage, even if the authentication server is compromised.

• Resistance to Phishing and Man-in-the-Middle Attacks: Since the user's credentials are never transmitted in cleartext, ZKPs make it significantly harder for attackers to intercept or manipulate authentication data.

• Resistance to dictionary and brute-force attacks: Since the password is never revealed, attackers cannot use techniques such as dictionary attacks or brute-force attacks to guess the password.

Digital Signature - A scheme of NI-ZKP

The central idea is that a digital signature, when used properly, can act as a self-contained proof of knowledge. This eliminates the need for back-and-forth interaction between the prover (the one demonstrating knowledge) and the verifier.

Basic Scenario

• Prover's Knowledge: The prover possesses a secret key \(sk\) and its corresponding public key \(pk\).

• Prover's Goal: To prove to a verifier that they know the secret key \(sk \) associated with a specific public key \(pk\), without revealing \(sk\).

• NIZKP Construction:

  1. Message: The prover selects a message \(m\).

  2. Signature: The prover generates a digital signature \(\delta\) on the message \(m\)using their secret key \(sk\).

  3. Proof: The prover presents the pair \((m,\delta)\) (the evidence) to the verifier.

• Verification: The verifier uses the public key \(pk\) to verify the signature \(\delta\) on the message \(m\). If the verification is successful, the verifier is convinced that the prover indeed knows the secret key \(sk\).