A formal introduction to zero-knowledge proofs

Abstract

The idea of zero-knowledge proof was first introduced by Goldwasser, Micali and Rackoff [GMR89] and has found its way to many real-world applications. The growing need for privacy in information exchange (e.g. transactions, digital signatures, commitment schemes, ...) lead to the development of proofs that yield nothing more than their validity.

We introduce the building blocks for zero-knowledge proofs through mathematical rigour, allowing the reader to gain a solid foundation to research further related topics. We explore some necessary notions of cryptography and probability, as well as computation theory by utilizing Turing machines as an automation abstraction. We delve into the theory of decision problems and the consequent classification through complexity classes, specially $\mathcal{P}, \mathcal{N} \mathcal{P}, \mathcal{B} \mathcal{P} \mathcal{P}$ and $\mathcal{I P}$. We use the concepts of repetition and interaction to prove that the decision error for languages in $\mathcal{B P} \mathcal{P}$ and $\mathcal{I P}$ can be decreased exponentially and explore the example of Graph Non-Isomorphism. We introduce the idea of zero-knowledge interactive proof systems and define some variations of its definition. We explore the example of Graph Isomorphism and conclude showing that the sequential repetition of zero-knowledge interactive proofs is indeed a zero-knowledge interactive proof.