An introduction to Zero Knowledge Proofs

A Zero Knowledge Proof protocol is a probabilistic algorithm specially designed to fulfill the following condition: A prover P convinces a verifier V that P knows an item of secret information, without revealing any detail about this secret information. I will present both historical protocols based on the difficulty of some computational problems in graphs and modern protocols based on the difficulty of the discrete logarithm problem. As the problem called MATHEMATICS is NP-complete, a possible application of the ZKP protocols is the following: Suppose that you found a proof of the Riemann Conjecture but you do not want to reveal this proof as long as your paper was not published. Then you can convince someone that, with great probability, you know a proof of the Riemann Conjecture but this process will reveal only Zero Knowledge about the actual proof.

Mihai Prunescu

Last modified: Wed Feb 14 2024