Zero knowledge: basics

Cryptography 2019-05-25

This post introduces the notion of a zero knowledge protocol. It is rudimentary. (I should have posted this earlier for the previous posts to make more sense. 🤣)

Zero Knowledge

The name Zero Knowledge sounds absolutely chic, but what is it?

The tutorial¹ by Oded Goldreich described it as follows,

Zero-knowledge proofs, introduced by Goldwasser, Micali and Rackoff², are fascinating and extremely useful constructs. Their fascinating nature is due to their seemingly contradictory definition; zero-knowledge proofs are both convincing and yet yield nothing beyond the validity of the assertion being proved.

So how are such proofs possible? One crucial component is the concept of interactive proof, which will be demonstrated in the following simple scenario (introduced in a lecture in Theory of Computation by Prof. Ran Duan at IIIS, possibly related to ‘‘Showing without telling’’³).

An example

Suppose you are trying to convince a color-blinded friend that two apples are of different colors (e.g. green and red). We can perform the following protocol, in which we use $P$ to denote the prover and $V$ to denote the verifier.

Apples in a color-blinded view
(w:en:User:Limbicsystem- English Wikipedia, src )

The protocol

$V$ holds the apples in the hands and turn back.
$V$ flips a coin, if the result is heads he switch the apples; otherwise he does nothing.
$V$ now asks $P$ whether he had switched the apple.

Analysis

If the apples are indeed different, $P$ can answer it correctly every time.
However, if they are identical, then in each execution $P$ has a probability of $\frac{1}{2}$ of being caught.

By the above example, we have demonstrated that interaction may really add something to the more traditional concept of proof. One thing to note is that the above protocol is automatically zero-knowledge; the prover does not need to tell which apple is of which color: he only needs to tell whether the apples are switched.

Use cases of ZK

Proving certain assertions is very important when it comes to protocol executions. However, revealing the proof $w$ directly and publicly is usually not the best option, e.g. when you want to show something like ‘‘you know the password of an account’’. And even worse, revealing $w$ in an $\mathcal{NP}$ relation $R(x,w) = 1$ will make anyone seeing the proof capable of proving it to others, raising a lot of concerns when malicious verifiers are present.

ZK finds usages in the following scenarios (from ‘‘Demonstrate how zero-knowledge proofs work without using math’’⁴).

Ownership: prove that you own a private key.
Account Balance: prove that your account has enough available balance for some transaction.
Sealed Bid Auctions: prove who won, without revealing any bid.
Any problem in $\mathcal{NP}$ admits ZK proof systems.

One can see that Ownership and Account Balance are important tasks when it comes to anonymous payments in digital currency applications (and in fact Zcash uses ZKs). And Sealed Bid Auctions are important to guarantee the auctioneer is not cheating in an online auction.

An arguably very important use case of ZK is the GMW compiler (conceived in GMW1987⁵), which uses ZK to ensure parties involved in a protocol to act according to the predetermined protocol, by requiring the parties to publish ZKs on their action, but without revealing it.

A formal definition

A zero-knowledge protocol for any $\mathcal{NP}$ relation is defined by two PPT (Probabilistic Polynomial Time) interactive algorithms, a prover $P$ and a verifier $V$ . Initially the prover is given the statement $x$ and a witness $w$ if $x \in L$ , and the verifier is given only the claimed statement $x$ .

Definition (The simulation paradigm)

(Zero-Knowledge proof) The protocol $(P,V)$ is is a zero-knowledge proof protocol for the relation $R$ if it satisfies the following requirements:

Completeness: If $R(x,w)=1$ and both players are honest then the verifier always accepts.
Soundness: For every malicious and computationally unbounded prover $P^*$ , there is a negligible function $\epsilon(\cdot)$ such that if $x$ is a false statement (i.e. $R(x,w) = 0$ for all $w$ ), the interaction of $P^*$ with $V$ on input $x$ rejects except with $\epsilon(\lvert x \rvert)$ probability.
Zero-knowledge: For every malicious PPT verifier $V^*$ there is a PPT simulator $M^*$ such that the view of $V^*$ interacting with $P$ on inputs $(x,w)$ for which $R(x,w) = 1$ , is computationally indistinguishable from the output distribution of $M^*(x)$ .
That is, there exists a negligible function $\delta(\cdot)$ such that for every efficient non-uniform distinguisher $D$ and every $x,w$ such that $(x,w) \in R$ we have
$\begin{aligned} \lvert \Pr(D(\text{View}_{V^*}(x,w) = 1) - \Pr(D(M^*(x)) = 1) \rvert \le \delta(\lvert x\rvert) \end{aligned}$
where $\text{View}_{V^*}$ denotes the view of $V^*$ , i.e.its input $x$ , its coin-tosses and its incoming messages.

Intuitively, the zero-knowledge requirement states that, instead of running the protocol, the verifier can run $M^*$ instead to generate the views. So the verifier can ‘‘simulate’’ an execution of the protocol using only $x$ and random coins. Therefore what the verifier sees during the protocol does not increase the knowledge of $V$ .

This post is a modification from a course project with Yuanhao Wang, on zero knowledge during the Fundamentals of Cryptography, Fall 2018 taught by Prof Wenfei Wu from IIIS.

Reference:

Oded Goldreich. Zero-Knowledge: a tutorial, 2010. tutorial. ↩
Shafi Goldwasser, Silvio Micali and Charle Rackoff. The Knowledge Complexity of Interactive Proof Systems. ↩
Oded Goldreich. Showing without telling, 2003. [Online, accessed 9-January-2019] Oded Goldreich’s page. ↩
Konstantinos Chalkias. Demonstrate how zero-knowledge proofs work without usingmaths, 2017. [Online, accessed 9-January-2019], LikedIn ↩
Oded Goldreich, Silvio Micali, and A. Wigderson. How to play any mental game or a com-pleteness theorem for protocols with honest majority. InProceedings of the NineteenthAnnual ACM Symposium on Theory of Computing, New York, NY, USA, 1987. ACM,ACM ↩