\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage[table]{xcolor}
\usepackage{adjustbox}
\usepackage{dashbox}
\usepackage{cjhebrew}
\usepackage{xspace}
\usepackage{url}
\usepackage{hyperref}
% packages for the graphs:
\usepackage{tikz}
\usetikzlibrary{graphs,graphs.standard}
\usetikzlibrary[arrows.meta,bending]
\usetikzlibrary{positioning}
%\usepackage{tikz-qtree}
\begin{document}
\input{preamble.tex}
\lecture{8: {\large Zero-Knowledge Proofs}}{December 14, 2017}{Nir Bitansky}{Omer Benami, Alon Frydberg, Daniel Kozlov}
\section{Previously on Foundations of Crypto}
So far, we've focused mainly on cryptographic schemes that dealt with cryptography's oldest mission --- securing communication. In the following weeks, we'll move on beyond secure communication to discuss goals that are more related to securing computation (with different aspects in mind, like privacy and correctness). In particular, we will want to construct protocols for securely computing arbitrary functions. Here the first notion we will touch is that of zero-knowledge proofs.
\section{Must a Proof Convey Knowledge?}
Typically, when we think about the concept of {\em a proof} our most essential requirement is that {\em they're convincing} --- if a statement has a proof then it must be true. Different disciplines of course have different takes on what convincing means (e.g., it could be merely evidence in criminology, or perhaps a fully detailed mathematical proof in a calculus). Something that seems inherent to almost any kind of proof is that it doesn't only tell us that a given assertion $x$ is true, but it also gives us some information on {\em how it is true} (e.g., a weapon with fingerprints suggests how a murder was performed). In particular, it is often the case that by witnessing a proof we gain the knowledge required to prove the assertion to someone else. In some scenarios, we may wish to avoid conveying such knowledge (for instance, we may like to prove that there's an eye witness to a murder, without revealing their identity and thereby risking them).
Zero-knowledge proofs, introduced by Goldwasser, Micali and Rackoff \cite{GMR}, suggest that proofs could be both convincing and yet, somewhat magically, not convey any knowledge, except of course for the fact that the assertion is true.
\paragraph{An Example: Sudoku Puzzles \cite{GNPR}.} A Sudoku board is a $9\times 9$ board divided into $3\times 3$ subsquares where the goal is to fill the board with integers in $\set{1,\dots,9}$ so that every integer appears exactly once in every row, column, or subsquare. A corresponding puzzle comes with some initial hints (partial assignment of integers) and has to be completed to a full solution.
\begin{center}
{\em Can you convince someone that you know a solution without revealing anything about it?}
\vskip 3mm
%Stuff to draw Sudoku puzzle
\newcounter{row}
\newcounter{col}
\newcommand\setrow[9]{
\setcounter{col}{1}
\foreach \n in {#1, #2, #3, #4, #5, #6, #7, #8, #9} {
\edef\x{\value{col} - 0.5}
\edef\y{9.5 - \value{row}}
\node[anchor=center] at (\x, \y) {\n};
\stepcounter{col}
}
\stepcounter{row}
}
\begin{tikzpicture}[scale=.5]
%First block: Unsolved
\begin{scope}
\draw (0, 0) grid (9, 9);
\draw[very thick, scale=3] (0, 0) grid (3, 3);
%Hints:
\setcounter{row}{1}
\setrow { }{2}{ } {5}{ }{1} { }{9}{ }
\setrow {8}{ }{ } {2}{ }{3} { }{ }{6}
\setrow { }{3}{ } { }{6}{ } { }{7}{ }
\setrow { }{ }{1} { }{ }{ } {6}{ }{ }
\setrow {5}{4}{ } { }{ }{ } { }{1}{9}
\setrow { }{ }{2} { }{ }{ } {7}{ }{ }
\setrow { }{9}{ } { }{3}{ } { }{8}{ }
\setrow {2}{ }{ } {8}{ }{4} { }{ }{7}
\setrow { }{1}{ } {9}{ }{7} { }{6}{ }
\node[anchor=center] at (4.5, -0.5) {Unsolved Sudoku};
\end{scope}
%Solved puzzle:
\begin{scope}[xshift=12cm]
\draw (0, 0) grid (9, 9);
\draw[very thick, scale=3] (0, 0) grid (3, 3);
%Solved: hints
\setcounter{row}{1}
\setrow { }{2}{ } {5}{ }{1} { }{9}{ }
\setrow {8}{ }{ } {2}{ }{3} { }{ }{6}
\setrow { }{3}{ } { }{6}{ } { }{7}{ }
\setrow { }{ }{1} { }{ }{ } {6}{ }{ }
\setrow {5}{4}{ } { }{ }{ } { }{1}{9}
\setrow { }{ }{2} { }{ }{ } {7}{ }{ }
\setrow { }{9}{ } { }{3}{ } { }{8}{ }
\setrow {2}{ }{ } {8}{ }{4} { }{ }{7}
\setrow { }{1}{ } {9}{ }{7} { }{6}{ }
\node[anchor=center] at (4.5, -0.5) {Solved Sudoku};
%Solved hidden numbers
\begin{scope}[blue, font=\sffamily\slshape]
\setcounter{row}{1}
\setrow {4}{ }{6} { }{7}{ } {3}{ }{8}
\setrow { }{5}{7} { }{9}{ } {1}{4}{ }
\setrow {1}{ }{9} {4}{ }{8} {2}{ }{5}
\setrow {9}{7}{ } {3}{8}{5} { }{2}{4}
\setrow { }{ }{3} {7}{2}{6} {8}{ }{ }
\setrow {6}{8}{ } {1}{4}{9} { }{5}{3}
\setrow {7}{ }{4} {6}{ }{2} {5}{ }{1}
\setrow { }{6}{5} { }{1}{ } {9}{3}{ }
\setrow {3}{ }{8} { }{5}{ } {4}{ }{2}
\end{scope}
\end{scope}
\end{tikzpicture}
\end{center}
% End of Sudoku image
\newpage
Consider the following proof strategy using cards as props:
\begin{enumerate}
\item
The prover, who knows a solution, takes 81 cards with nine sequences of the numbers $\set{1,\dots,9}$. It then places them on the board according to the solution, so that their backs (which all look the same) are facing the verifier. It flips over only the cards participating in the hint.
\item
The verifier now chooses a random one of the three constraints (rows, columns, or subsquares) and asks the prover to prove that the constraint is satisfied.
\item
The prover does this as follows. Say for instance that the verifier asked to prove consistency of the rows. The prover stacks each of the rows, and shuffles its cards at random behind her back (turning around is also fine), and hands the nine corresponding shuffled stacks to the verifier.
\item
The verifier checks that each such stack contains all numbers $\set{1,\dots,9}$.
\end{enumerate}
Notice that if the solution is valid, the prover will always manage to pass the test. However, if the prover placed an invalid solution on the board, there will be at least one type of constraint that is violated, and will catch her w.p. at least 1/3. By repeating this proof $n$ times independently, the probability that the prover manages to cheat can be decreased exponentially in $n$.
\paragraph{What Does a Verifier Learn?} If the solution was valid, in each such proof, the verifier simply obtains 9 stacks of $\set{1,\dots,9}$ at a random order. This doesn't convey any information --- the verifier doesn't need a solution to generate 9 shuffled stacks, she can do it herself. In particular, the verifier doesn't gain the ability to prove to a third party that she knows a solution.
\medskip\noindent The above proof seems nothing like what we're used to. It's {\em interactive} and it's {\em randomized} (two aspects that turn out to be essential for zero knowledge). Is it just a card trick? or can we actually prove meaningful statements this way? does it have a digital analog where parties simply exchange messages? As we shall discuss later on, the last proof system is already very expressive (when generalized to $n^2 \times n^2$ Sudoku boards) and has a natural digital analog. First, let's figure out how to define these proof systems.
\section{Defining Zero-Knowledge Proofs}
We'll start by defining the concept of interactive proofs (IPs), without addressing the zero-knowledge requirement. Indeed, while born with zero-knowledge, this concept turned out to be fascinating on its own, and has completely revolutionized complexity theory (in particular, it can be seen as the seed for major results such as the characterization of PSPACE and the PCP theorem).
\newcommand{\prot}[2]{\left\langle#1,#2\right\rangle}
\begin{definition}[Interactive Proofs (IPs)]
An interactive proof system $(P,V)$ for a language $L\subseteq \zo^*$ consists of a PPT verifier $V$ and a prover $P$, which are both interactive. We require:
\begin{itemize}
\item
{\bf Completeness:} for any $x\in L$,
$$
\Pr\[\prot{P}{V}(x) = 1\] \geq 0.9\enspace,
$$
where $\prot{P}{V}(x)$ denote the output of $V$ after a joint interaction with $P$ on common input $x$.
\item
{\bf Soundness:} for any $x\notin L$ and any malicious prover strategy $P^*$,
$$
\Pr\[\prot{P}{V}(x) = 1\] \leq 0.1\enspace.
$$
\end{itemize}
\end{definition}
\paragraph{Remarks on the Definition:}
\begin{itemize}
\item
{\bf Soundness and Completeness Errors.} In the above we allow soundness error and completeness error $c=s=0.1$. In general, we may consider proof systems with arbitrary $s<1-c\leq 1$. We can also amplify this by running the protocols sequentially (the number of required repetitions depends on the new desired error and the gap between $1-c-s$).
\item
{\bf Honest vs Malicious.} So far in the course, a cryptographic scheme or protocol were always executed by the honest parties (Alice and Bob) and was subject to an attack by a third party (Eve). Here the protocol is supposed to behave correctly when both parties $P$ and $V$ are honest, and remain sound even if the prover party is malicious. This will be a common setting in the cryptographic protocols we're going to see.
\item
{\bf Efficiency of Parties.} The prover in the IP definition (honest or malicious) may be computationally unbounded. The verifier on the other hand is efficient.\footnote{Indeed, philosophically speaking, efficient verification is the essence of how a proof is superior to a truth.}
A common requirement is that the honest prover is also efficient (PPT), which we will call an {\em efficient prover IP}. The ability to obtain an efficient prover depends on the complexity of the language and may require that the honest prover will get an extra auxiliary input.\footnote{Note that an efficient prover IP where the prover doesn't get any auxiliary input implies that $L\in BPP$ (think why).} For instance, to prove an NP statements efficiently we mush provide the prover with a witness.
It is also quite common to limit malicious provers to being efficient, which is sometimes called an {\em interactive argument}, or a {\em proof with computational soundness}.
\end{itemize}
\paragraph{Defining Zero Knowledge.} We now move to formally define what it means for a protocol to be zero knowledge. The intuition that we'd like to capture is that
\begin{center}
{\em Whatever the verifier learns from a proof of a true statement, she could have learned on her own.}
\end{center}
This is formally captured by requiring that there's an efficient simulation algorithm $S(x)$ that can {\em simulate} the {\em view} of the verifier.
\def \view {View}
\begin{definition}[Zero Knowledge (ZK)]
A proof system $(P,V)$ for $L$ is zero knowledge if for any n.u. PPT $V^*$ (with arbitrarily long output), there exists a n.u. PPT $S$ such that
$$
\set{\prot{P}{V^*}(x)}_{x\in L} \approx_c \set{S(x)}_{x\in L}\enspace,
$$
where the random variable $\prot{P}{V^*}(x)$ denotes $V^*$'s output after an interaction with $P$ on common input $x$.
\end{definition}
\paragraph{Remarks on the Definition:}
\begin{itemize}
\item
{\bf WLOG: Simulate the View.}
Unlike the honest verifier that only outputs its decision bit, the malicious $V^*$ can produce an output that arbitrarily (but efficiently) depends on its view in the protocol's execution. We can assume w.l.o.g that the verifier outputs the view itself, including all messages and her randomness.
%\item
%{\bf Equivalent Definition.} A common equivalent definition is one where the simulator is simply required to simulate the verifier's output, which is allowed to be arbitrary, rather than just an acceptance bit (think why it's equivalent).
% \item
{\bf Expected Polynomial Time.} A common relaxation of the definition is that the simulator will only run in {\em expected polynomial time}.
\item
{\bf Universal Simulation.} Another common formulation requires that there is one {\em universal simulator} PPT $S$ that can simulate any verifier $V^*$, given the code of $V^*$ as additional input. This definition turns out to be very useful when composing zero-knowledge protocols with other protocols (or with themselves). For now, we can ignore this difference.
\end{itemize}
\paragraph{The Simulation Paradigm More Broadly.} The zero knowledge definition is a special case of a more general {\em simulation paradigm}, whose main idea is to capture at once {\em all the possible attacks}. Indeed, the verifier may try to learn different types of information. For instance, for an NP language $L$, it may try to learn a witness, or to just learn the first bit of the witness. Simulation guarantees that all of these potential attacks would fail, unless these are pieces of information that can anyhow be learned from the instance.
More generally, the simulation paradigm aims to capture the fact that whatever effect the adversary can have on our cryptographic scheme or protocol is restricted to what the adversary can do in {\em an ideal world}. (In ZK ideal world, the only information given to the adversary is the fact that the statement is true.) We've actually already encountered this paradigm in some of the encryption definitions we've discussed, where encryptions of any message could be simulated by a sampling from fixed distribution, independent of any message. We'll encounter this paradigm again later on in the course.
\section{Constructing Zero Knowledge Protocols}
We would now like to figure out how to construct zero knowledge protocols and in particular how to prove the existence of a simulator. We will start with a protocol for the specific problem of {\em quadratic residuosity}, which is in fact, the first zero knowledge protocol ever constructed \cite{GMR}.
\def \ZZ {\mathbb{Z}}
\smallskip\noindent Consider the language
$$QR = \set{(N,y) \pST \exists x\in \ZZ_N^*: y=x^2 \mod N}\enspace.$$
We'll design a zero knowledge proof system $(P,V)$ for the language $QR$ that has an efficient prover that gets as auxiliary input the square root $x$ of the instance $y=x^2$. The system will have perfect completeness (i.e. the completeness error is $c=0$) and soundness error $s=1/2$. In the following protocol all arithmetics is $\mod N$.
\paragraph{Protocol $\prot{P(x)}{V}(N,y)$:}
\begin{enumerate}
\item
$P$: chooses at random $r\gets \ZZ_N^*$, and sends $s=r^2$ to $V$.
\item
$V$: samples a bit $b\gets \zo$ at random and sends $b$ to $P$.
\item
If $b=0$, $P$ sends back $r$, and if $b=1$, it sends back $t = rx$.
\item
If $b=0$, $V$ checks that $s=r^2$, and if $b=1$ it checks that $sy = t^2$.
\end{enumerate}
\begin{claim}
The above protocol is a zero knowledge proof with soundness error $1/2$ and expected polynomial-time simulator.
\end{claim}
\begin{proof}[Proof Sketch]
Completeness of the protocol is straightforward. We'll focus on soundness and ZK.
\paragraph{Soundness.} To see that the protocol has soundness error $s=1/2$, note that if $y$ is not a quadratic residue $\mod N$ then for any quadratic residue $s=r^2$, $sy$ is not a quadratic residue; indeed if $sy =t^2$, then $y=s^{-1}t^{2} = (r^{-1}t)^2$. This means that if $(y,N)\notin QR$, either $s$ has no square root, or $sy$ has no square root, and we'll catch the prover with probability $1/2$.
\paragraph{Zero-Knowledge Simulation.} We now move to prove the that protocol is zero-knowledge in the case that $y=x^2$. First, to develop some intuition, let's start with a warmup. Imagine that the verifier always chooses $b=0$. Then in this case, all that it sees in an interaction with $P$ is a sample from the distribution $D_0:=\(r^2,r \pST r\gets \ZZ_N^*\)$, which is easy to simulate. Now imagine that the verifier always chooses $b=1$. Can we simulate it without the witness? This verifier always sees sample from $D_1 := \(r^2,xr\pST r\gets \ZZ_N^*\)$. The point is that $r^2,xr$ is distributed exactly like $(x^{-1}r)^2,x(x^{-1}r)=(y^{-1}r^2,r)$, which is again something we can easily simulate, given $y$ alone.
But how do we simulate a verifier that may arbitrarily choose $b$, possibly depending on the first message. Can the simulator predict which $b$ is going to be used? Well it can guess $b'$, hoping that $b=b'$, and then attempt to simulate $D_b$. This works because the first message in either $D_0$ or $D_1$ has the exact same distribution, independently of the simulator's guess $b'$ and thus $b=b'$ with probability $1/2$. If the simulator fails, it can try again (how many times until it succeeds?)
\smallskip\noindent
Let's the describe the simulator $S$ more formally:
\begin{enumerate}
\item $S$ samples $b'\gets \zo$ and $r\gets \ZZ_N^*$ and starts emulating an interaction with $V^*$:
\begin{itemize}
\item If $b'=0$, $S$ sends $r^2$ to $V^{*}$.
\item If $b'=1$, $S$ sends $y^{-1}r^2$.
\end{itemize}
\item $S$ receives $b$ from $V^*$ and:
\begin{itemize}
\item If $b=b'$, sends $r$ to $V^{*}$, and concludes the simulation.
\item Else, returns to the beginning and performs the entire simulation again.
\end{itemize}
\end{enumerate}
First, to see that the simulator runs in expected polynomial time, we use the fact that the simulator's first message is always from the same distribution --- a random quadratic residue --- and is independent of his choice $b'$. Thus the verifier's choice $b$ is also independent of $b'$, which implies that $b'=b$ w.p. $1/2$. So in expectation the simulator only has to perform the experiment twice.
Next, we would like to prove that the view of the verifier in a real execution with the prover is indistinguishable from the view produce by the simulator; we'll in fact show it's identically distributed. For this, it is sufficient to show that:
\begin{enumerate}
\item Conditioning on either verifier choice $b\in \zo$, the real interaction and simulated interaction are identically distributed.
\item The distribution of $b$ in the real interaction and simulated interaction is identical.
\end{enumerate}
The first claim follows similarly to our warmup. Indeed, in the real interaction, conditioned on $b$, the view is distributed as $D_b$, and our simulator conditioned on $b$ samples from a distribution that is identical to $D_b$.
The second claim follows directly from the fact that both in a real and simulated interaction the distribution of the first message is identical (a random quadratic residue).
\end{proof}
\section{More Expressive Zero Knowledge}
Quadratic residuosity is a specific problem, and we have strongly relied on its specific algebraic structure to construct the proof systems.
\begin{center}
{\em Do the protocols we saw generalize to broader classes? What can be proved in zero knowledge?}
\end{center}
Remarkably it turns out that we can prove much more in zero knowledge!
\begin{theorem}[\cite{GMW}]
Assuming OWFs, any NP language has a zero-knowledge proof.
\end{theorem}
%
We will prove this theorem, but first we need to define a tool which is very commonly used in protocols.
\paragraph{Commitments.} To be precise, GMW did not assume OWFs, but a more expressive primitive called {\em a commitment scheme}, which were later constructed from OWFs \cite{Naor}. We will now define such commitments and use them to prove the GMW theorem. Intuitively speaking, such commitment schemes are digital analogs of ``locked boxes". The sender puts a message in a box, locks it, and sends it to the receiver. The receiver cannot see what's in the box, until the opening phase, when the sender unlocks the box. The sender on the other hand cannot change the message, after she had sent the box.
Today, we'll define and use a simple case of commitments schemes that are non-interactive. The more general definition addresses protocols.
\begin{definition}[Non-Interactive Commitment Scheme]
A commitment scheme is given by a PPT commitment algorithm $Com$ satisfying:
\begin{itemize}
\item {\bf Computational Hiding:}
$$
\set{Com(m_0)}_{\begin{subarray}{l}n\in\Nat\\
m_0,m_1\in \zo^n\end{subarray}} \approx_c \set{Com(m_1)}_{\begin{subarray}{l}n\in\Nat\\
m_0,m_1\in \zo^n\end{subarray}}\enspace.
$$
\item {\bf Perfect Binding:}
For any messages $m_0,m_1$ and randomness $r_0,r_1$ if $Com(m_0;r_0)=Com(m_1;r_1)$, then $m_0=m_1$. (This means that any commitment can be ``opened'', by exhibiting a randomness, to a unique message.)
\end{itemize}
\end{definition}
\paragraph{A Simple Construction from Injective OWFs \cite{BM}.} We now describe a simple construction of non-interactive commitments based on injective OWFs. Let $f$ be an injective OWF, we define commitments for one bit messages $m\in\zo$ as follows
$$
Com(m;x,r) = f(x), r, \langle x,r\rangle \oplus m\enspace,
$$
where $x,r \gets \zo^n$.
\begin{claim}
The above construction satisfied hiding and binding.
\end{claim}
\begin{proof}[Proof Sketch.] To prove binding, assume that $Com(m;x,r) = Com(m';x',r')$. Then by definition $r = r'$and since $f$ is injective, $x = x'$ as well. Thus, $\langle x,r\rangle \oplus m = \langle x,r\rangle \oplus m'$, which means that $m = m'$.
To prove hiding, note that by the GL theorem, $\langle x,r\rangle$ is a hardcore bit of the function $(x,r)\mapsto \(f(x),r\)$ and so
$$
f(U_n),U_n',\langle U_n,U_n'\rangle \approx_c f(U_n),U_n',U_1\enspace,
$$
where $U_n,U_n'$ are independent. Thus for any message $m$:
$$
Com(m;x,r) = f(U_n),U_n',\langle U_n,U_n'\rangle \oplus m \approx_c f(U_n),U_n',U_1\oplus m \equiv f(U_n),U_n',U_1
$$
Since the r.h.s. does not depend on $m$, it follows that $Com(m_0) \approx_c Com(m_1)$ for any two messages $m_0,m_1\in \zo$.
\end{proof}
Given a commitment for one-bit messages, we can easily construct commitments for messages of arbitrary length, by committing each bit separately (make sure you understand why this construction is secure).
%\begin{definition}[Commitment Scheme]
%A commitment scheme $(S,R)$ is a protocol between a PPT sender $S$ and a PPT receiver $R$ satisfying:
%\begin{itemize}
% \item {\bf Computational Hiding:} for any malicious n.u. PPT receiver $R^*$,
% $$
% \set{\prot{S(m_0)}{R^*}}_{\begin{subarray}{c}n\in\Nat\\
% m_0,m_1\in \zo^n\end{subarray}} \approx_c \set{\prot{S(m_1)}{R^*}}_{\begin{subarray}{c}n\in\Nat\\
% m_0,m_1\in \zo^n\end{subarray}}\enspace,
% $$
% where $\prot{S(m_0)}{R^*}$ denotes the output of $R^*$ after interacting with $S$ that commits to $m_0$.
% \item
%\end{itemize}
%\end{definition}
\paragraph{The GMW Protocol.} \smallskip\noindent To construct a protocol for any NP language it suffices to construct a protocol for one NP-complete language The GMW protocol is for the language of $3$-colorable graphs
$$3COL = \set{(U,E) \pST \exists c:U \rightarrow [3] : \forall (u,v)\in E, c(u)\neq c(v)}\enspace.$$
We'll design a zero knowledge proof system $(P,V)$ for the language $3COL$ that has an efficient prover that gets as auxiliary input a legal coloring $c$ of $G$. The system will have perfect completeness (i.e. the completeness error is $c=0$) and soundness error $s=1-\frac{1}{|E|}$.
\begin{center}
\begin{tikzpicture}
\node[shape=rectangle,draw=black, minimum size=0.5cm] (E) at (10,0) {};
\node[shape=rectangle,draw=black, minimum size=0.5cm] (F) at (10,1.5) {};
\node[shape=rectangle,draw=black, minimum size=0.5cm] (G) at (11.5,1.5) {};
\node[shape=rectangle,draw=black, minimum size=0.5cm] (H) at (11.5,0) {};
\node[shape=rectangle,draw=black, minimum size=0.5cm] (E) at (5,0) {};
\node[shape=rectangle,draw=black, minimum size=0.5cm] (F) at (5,1.5) {};
\node[shape=rectangle,draw=black, minimum size=0.5cm] (G) at (6.5,1.5) {};
\node[shape=rectangle,draw=black, minimum size=0.5cm] (H) at (6.5,0) {};
\coordinate (A) at (9.72,1.75);
\coordinate (B) at (10.25,1.75);
\draw[-, white] (A) -- (B);
\coordinate (A) at (9.72,0.25);
\coordinate (B) at (10.25,0.25);
\draw[-, white] (A) -- (B);
\coordinate (A) at (1.9,0.7);
\coordinate (B) at (4.3,0.7);
\draw[->] (A) -- (B);
\coordinate (A) at (6.9,0.7);
\coordinate (B) at (9.3,0.7);
\draw[->] (A) -- (B);
\coordinate (A) at (9.72,1.75);
\coordinate (B) at (10.25,2);
\draw[-, black] (A) -- (B);
\coordinate (A) at (9.72,0.25);
\coordinate (B) at (10.25,0.5);
\draw[-, black] (A) -- (B);
\node[shape=rectangle,fill=blue,draw=white] (A) at (2.5,1.5) {};
\node[shape=rectangle,fill=red,draw=white] (B) at (3,1.5) {};
\node[shape=rectangle,fill=green,draw=white] (C) at (3.5,1.5) {};
\node[shape=rectangle,fill=green,draw=white] (A1) at (2.5,1) {};
\node[shape=rectangle,fill=blue,draw=white] (B1) at (3,1) {};
\node[shape=rectangle,fill=red,draw=white] (C1) at (3.5,1) {};
\path [->] (A) edge node[left] {} (A1);
\path [->] (B) edge node[left] {} (B1);
\path [->] (C) edge node[left] {} (C1);
\node[shape=circle,fill=blue,draw=black] (A) at (0,0) {};
\node[shape=circle,,fill=red,draw=black] (B) at (0,1.5) {};
\node[shape=circle,fill=green,draw=black] (C) at (1.5,1.5) {};
\node[shape=circle,fill=red,draw=black] (D) at (1.5,0) {};
\path [-] (A) edge node[left] {} (B);
\path [-] (C) edge node[left] {} (A);
\path [-](B) edge node[left] {} (C);
\path [-](A) edge node[left] {} (D);
\path [-](D) edge node[left] {} (C);
\node[shape=circle,fill=green,draw=black] (A) at (5,0) {};
\node[shape=circle,,fill=blue,draw=black] (B) at (5,1.5) {};
\node[shape=circle,fill=red,draw=black] (C) at (6.5,1.5) {};
\node[shape=circle,fill=blue,draw=black] (D) at (6.5,0) {};
\path [-] (A) edge node[left] {} (B);
\path [-] (C) edge node[left] {} (A);
\path [-](B) edge node[left] {} (C);
\path [-](A) edge node[left] {} (D);
\path [-](D) edge node[left] {} (C);
\node[shape=circle,fill=green,draw=black] (A) at (10,0) {};
\node[shape=circle,,fill=blue,draw=black] (B) at (10,1.5) {};
\node[shape=circle,fill=red,draw=black] (C) at (11.5,1.5) {};
\node[shape=circle,fill=blue,draw=black] (D) at (11.5,0) {};
\path [-] (A) edge node[left] {} (B);
\path [-] (C) edge node[left] {} (A);
\path [-](B) edge node[left] {} (C);
\path [-](A) edge node[left] {} (D);
\path [-](D) edge node[left] {} (C);
\end{tikzpicture}
\newline
{\em Figure: Illustration of the GMW protocol.} \newline {\em The sealed black boxes represent the commitments. The open boxes are the opened commitments.}
\end{center}
\paragraph{Protocol $\prot{P(c)}{V}(U,E)$:}
\begin{enumerate}
\item
$P$: chooses a random permutation $\varphi:[3]\rightarrow [3]$, and sends $V$ commitments to all colors after applying the permutation:
$$\(Com(\varphi(c(v))) \pST v\in U\) \enspace.$$
\item
$V$: samples $e\gets E$ at random and sends $e=(u,v)$ to $P$.
\item
$P$ opens the commitments corresponding to $u$ and $v$.
\item
$V$ verifies that the two opened colors are distinct.
\end{enumerate}
\begin{claim}
The above protocol is a zero knowledge proof with soundness error $1-\frac{1}{|E|}$ and expected polynomial-time simulator.
\end{claim}
\begin{proof}[Proof Sketch]
Once again completeness of the protocol is straightforward and we'll focus on soundness and ZK.
\paragraph{Soundness.} To see that the protocol has soundness error $s=1-\frac{1}{|E|}$, note that if $(U,E)$ is not three colorable, then in any coloring, there must exist an edge $e$ that is not properly colored. Since the commitment is perfectly binding, it fixes a coloring of the corresponding vertices (some of the commitments may be invalid altogether, so this coloring may be partial). The probability that the verifier asks to open an improper edge (where improper may mean either that the coloring is improper or that the commitments are invalid) is thus at least $1/|E|$.
\paragraph{Zero-Knowledge Simulation.} We now move to prove the that protocol is zero-knowledge. To get some high-level intuition, let us indeed think of the commitments as ideal locked boxes. Then, all that the verifier sees is a bunch of opaque boxes, it then opens two boxes of his choice and simply sees two distinct random colors, this is something that it could simulate on its own.
The actual simulator will act as follows:
\begin{enumerate}
\item $S$ samples $e'\gets E$ and commitments
$$\(Com(0) \pST v\in U\setminus e'\) \enspace.\footnote{Here $0$ is an abitrary choice and we assume $0$ and each $i\in [3]$ are represented by the same number of bits.}$$
For the vertices $v',u'$ of $e'$ it samples $c(v')$ and $c(u')$ to be two distinct random colors in $[3]$.
$S$ then emulates $V^*$, sending the simulated commitments.
\item $S$ receives $e$ from $V^*$ and:
\begin{itemize}
\item If $e=e'$, opens the corresponding commitments and concludes the simulation.
\item Else, returns to the beginning and performs the entire simulation again.
\end{itemize}
\end{enumerate}
Intuitively, we'd like to apply a similar argument as we did in the quadratic resinously protocol. That is claim that the simulator's first message distributed similarly to the first prover message and is independent of his choice $e'$. Then, we'd argue that conditioned on any particular $e$ the views in a real interaction and an ideal interaction are distributed identically. Similarly, we would argue that the simulator runs in expected polynomial time (that scales this time with $1/|E|$).
Of course that all of the above is simply not true, the prover first message and simulator's are distributed very differently, and the simulator's first message not only depends on $e'$, but uniquely determines it. However, we do know that the prover's first message is computationally indistinguishable from that for the simulator, and thus there should be a computational analog to the above argument.
This is indeed the case. To show this, we consider an imaginary simulator $S'$ that also gets a legal coloring $c$ (this is only a mental experiment). It proceeds similarly to $S$, except that instead of computing commitments to zeros for all $v\notin e'$, it uses $c$ to commit to their colors, consistently with the permutation it chose (note that choose two distinct random colors for $e'$ already fixes a random permutation $\varphi:[3]\rightarrow [3])$. It then proceeds just like $S$. We can show that
\begin{itemize}
\item
$S$ and $S'$ have roughly the same expected running times.
\item
Output computationally indistinguishable views.
\end{itemize}
Otherwise, we can use them to break the computational hiding of the commitment scheme.
Now, it is left to show that $S'$ run in expected poly time and produces a view that is indistinguishable (in fact, identical) to the an interaction with the real prover. This can already be done following the argument we started with (which didn't work for $S$).
\end{proof}
In the homework, you will show a ZK protocol for the Sudoku problem, which is actually also NP complete.
\bibliographystyle{alpha}
\bibliography{bib8}
\end{document}