Interactive Zero-Knowledge Proof
Introduction
Good day everyone, last week we saw how one could prove the existence of data in real life through Interactive Zero-Knowledge Proofs. Today, we will look at what an Interactive ZKP is.
As usual, it will be easy to understand.
The main objective of a Zero-Knowledge proof is for the prover to prove to the verifier that they possess a "witness" or data, without revealing the "witness" to anyone. This is done through an interactive ZKP, which involves live interaction between the prover and verifier. Just like in the article on Peggy and Victor, the two must communicate back and forth to exchange information.
An example of Interactive ZKP using Discrete Algorithm
Discrete algorithms are used for Interactive ZKPs because they are well-suited for solving the mathematical problems that are central to the construction of Interactive ZKPs. These problems typically involve finite structures and require the manipulation of discrete data, making discrete algorithms a natural choice. Additionally, discrete algorithms are often more efficient than their continuous counterparts, making them a practical choice for real-world implementation. The use of discrete algorithms in Interactive ZKPs allows for efficient and secure proof construction, making them a crucial component of many secure systems and protocols.
A computation between the prover, Slytherin, and the verifier, Gryffindor, is a method for Slytherin to prove to Gryffindor that he knows the value of "Witness" without disclosing the actual value. The following is a step-by-step explanation:
⁃ Slytherin wants to prove to Gryffindor that she knows the value of "Witness." Such that y= g^ “witness”; where g is the base and w is the exponent
⁃ Slytherin picks a random value "x" from a set of values "Z" and computes "t" = "g^x". Slytherin then sends "t" to Gryffindor.
⁃ Gryffindor picks a random value "c" from the same set "Z" and sends it back to Slytherin.
Gryffindor picks the value of c to add randomness to the proof and to ensure that Slytherin cannot cheat.
⁃ Slytherin then computes "r" as "x - c * Witness" and returns "r" to Gryffindor.
r is a deterministic value (a value that can be predicted based on inputs) computed from the random values x and c and the secret value 'Witness'.
r is computed as r = x-c*'Witness', where x is a random value picked by Slytherin and c is a random value picked by Gryffindor. The value of r depends on the values of x, c, and 'Witness'.
The purpose of computing r is to prove to Gryffindor that she knows the value of "Witness" without revealing it
⁃ Gryffindor checks if "t = g^r * y^c" holds true, where "y = g^Witness." Since "r = x - c * Witness" and "y = g^Witness," Gryffindor can substitute these values into the equation to get "g^(x - c * Witness) * g^(c * Witness) = g^x = t."
⁃ If the equation holds true, it means that Slytherin does indeed know the value of "Witness," and Gryffindor can verify this without actually knowing the value.
This Interactive Zero-Knowledge Proof with Discrete Algorithm is a way for Slytherin to prove her knowledge of "Witness" to Gryffindor without revealing the actual value.
Problems with Interactive Zero-Knowledge proof
Unscalable
The two parties: the prover and verifier have to be online or together at the same for the proof to work.
Limited Transferability
To prove same proof to another verifier, the entire process has to be repeated.
Problems faced with Interactive Zero-Knowledge proofs are solved by Non-Interactive Zero-Knowledge proofs, making proofs more scalable and better.
Application
Authentication System
It can be used for users to verify their password without revealing it to the system.
Nuclear Disarmament
Princeton Plasma Physics lab and Princeton University demonstrated a technique that allowed inspectors to know if a device is a nuclear weapon without revealing anything.
Summary/ Conclusion
In conclusion, Interactive Zero-Knowledge Proofs (ZKPs) are a way for a prover to prove to a verifier that they have a certain "witness" or data without revealing it to anyone. This proof is done through an interaction between the prover and verifier and is usually implemented using discrete algorithms. However, Interactive ZKPs have limitations such as the requirement of both parties being online and the proof being limited to one verifier. Non-Interactive ZKPs have been developed to address these limitations. Interactive ZKPs have applications in areas such as authentication systems and nuclear disarmament.
Sources:
https://blog.chain.link/interactive-zero-knowledge-proofs/
https://www.geeksforgeeks.org/interactive-zero-knowledge-proof/amp/