3coloring_zeroknowledge.tex

\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts,xcolor}

\theoremstyle{definition}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{protocol}{Protocol}
\newtheorem{simulator}{Simulator}
\newcommand{\comment}[1]{\textcolor{blue}{[#1]}}
\setlength\parindent{0pt}

\newenvironment{problem}[2][Problem]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}\hskip \labelsep {\bfseries #2.}]}{\end{trivlist}}
%If you want to title your bold things something different just make another thing exactly like this but replace "problem" with the name of the thing you want, like theorem or lemma or whatever
 
\begin{document}
 
%\renewcommand{\qedsymbol}{\filledbox}
%Good resources for looking up how to do stuff:
%Binary operators: http://www.access2science.com/latex/Binary.html
%General help: http://en.wikibooks.org/wiki/LaTeX/Mathematics
%Or just google stuff
 
%\title{\textbf{Zero-Knowledge protocol for Graph 3-Coloring}}
%\author{Chloe Cachet}
%\maketitle


% definitions
\begin{definition} \textbf{Graph 3-Coloring} \\
Given a graph $G = (V, E)$, can we find a 3-colors assignment for the vertices such that adjacent vertices have different colors:
$$ 3COL = \{<G(V,E)> | \exists c: V \rightarrow \{1,2,3\} \textit{, s.t. } \forall (u,v) \in E, c(u) \neq c(v)\} $$
\end{definition}


\begin{definition} \textbf{Commitment Scheme} \\
Let $P$ be a PPT prover, $V$ be a PPT verifier and $(Commit,Open)$ be a commitment protocol. The protocol for $P$ to commit to a value $x \in \mathcal{M}$ goes as follows:

\begin{enumerate}
	\item $P$ draws a random value $r$.
	\item $P$ runs $c \leftarrow Commit(x,r)$ and sends $c$ to $V$.
	\item When $P$ is ready to reveal $x$, $P$ sends $r$ to $V$.
	\item $V$ runs $x' = Open(c,r)$, with $x' = x$ when $c \leftarrow Commit(x,r)$, $x' = \perp$ otherwise.
\end{enumerate}

The commitment scheme $(Commit,Open)$ is said to be \textbf{hiding} if, $\forall x_1,x_2 \in \mathcal{M}$, $\forall$ PPT distinguisher $D$:

$$ | \Pr[D(Commit(x_1;r)) = 1] - \Pr[D(Commit(x_2;r)) = 1] | \leq \eta(n) $$

The commitment scheme $(Commit,Open)$ is said to be \textbf{binding} if, $\forall x_1,x_2 \in \mathcal{M}$, $x_1 \neq x_2$:

$$ \Pr[Open(Commit(x_1;r_1);r_2) = x_2] \leq \epsilon(n)  $$
with $\eta$ and $\epsilon$ a negligible function of the security parameter $n$.
\end{definition}


% protocol and simulator
\begin{protocol} \textbf{(Sequential)} \\

Let $\mathcal{P}$ be an unbounded prover and $\mathcal{V}$ be a PPT verifier. The zero-knowledge protocol for $3COL$ goes as follows: \\

\begin{enumerate}
	\item $\mathcal{P}$ and $\mathcal{V}$ both receive the graph $G = (V,E)$ as input.
	\item $\mathcal{V}$ randomly draws a edge $e \in E$, such that $e = (v_j,v_k)$ with $v_j,v_k \in V$.
	\item $\mathcal{V}$ computes the commitment of $e$: $x \leftarrow  Commit(e,r)$, and sends $x$ to $\mathcal{P}$.
	\item $\mathcal{P}$ receives a 3-coloring assignment for $G$: $c(v_i)$ such that $c: V \rightarrow \{1,2,3\}$ and $v_i \in V$.
	\item $\mathcal{P}$ computes the commitment of each $c(v_i)$, $y_i \leftarrow Commit(v_i,r_i)$ and sends the list of committed values to $\mathcal{V}$.
	\item $\mathcal{V}$ opens $x$: $e = Open(x,r)$,  and sends $e$ as a challenge to $\mathcal{P}$.
	\item $\mathcal{P}$ opens $y_j$ and $y_k$ such that $e = (v_j,v_k)$: and sends $c(v_j),c(v_k)$ to $\mathcal{V}$.
	\item $\mathcal{V}$ rejects if the corresponding coloring is invalid, \textit{i.e.} $c(v_j) = c(v_k)$.
\end{enumerate}

\end{protocol}

If the 3-coloring computed by $\mathcal{P}$ is a valid one, then:
$$\Pr[<P,V>(G) = 1] = \Pr[c(v_j) \neq c(v_k) ] = 1 $$


otherwise, there exists at least one edge $e = (u,v)$ such that $c(u) = c(v)$ and we have:
$$ \Pr[c(u) = c(v) ] = \frac{1}{|E|}$$

\textbf{Commitment hiding reduction using V:}\\
Consider a malicious PPT verifier $\mathcal{V*}$ and assume it is able to extract the value from a commitment before the opening phase. Let $\mathcal{D}$ be a PPT distinguisher for the commitment hiding game and $\mathcal{O}$ be the corresponding oracle. The game goes as follows:

\begin{enumerate}
	\item $\mathcal{D}$ simultaneously build a graph $G=(E,V)$ and a valid 3-coloring for it, and sends $G$ to $\mathcal{V*}$.
	\item $\mathcal{D}$ randomly picks a vertex $v \in V$ and sends $c_0(v)$ and $c_1(v)$, respectively a valid and an invalid coloring for $v$, to $\mathcal{O}$.
	\item $\mathcal{O}$ draws $b \xleftarrow{\$} \{0,1\}$, computes $x \leftarrow Commit(c_b(v);r)$ and sends $x_b$ to $\mathcal{D}$.
	\item $\mathcal{D}$ forwards $x$ to $\mathcal{V*}$ and receives back an edge $e=(v_i,v_j) \in E$ as a challenge. 
	\item If $v \in e$, $\mathcal{D}$ assumes that the value $\mathcal{V*}$ extracted from $x$ was the invalid coloring $c_1(v)$ and returns $b'=1$. Otherwise, $\mathcal{D}$ assumes that $\mathcal{V*}$ extracted the valid coloring $c_0(v)$ from $x$ and that it chose $e$ at random, and it returns $b'=0$.
\end{enumerate}

%Let $\Pr[<\mathcal{P},\mathcal{V*}>(G) = 1]$ be the probability of $\mathcal{V*}$ winning its game and $\Pr[\mathcal{D}(Commit(c_b(v);r_b))=1]$ be the probability of $\mathcal{D}$ to output $b'=1$ given $Commit(c_b(v);r_b)$:
%
%$$ \Pr[<\mathcal{P},\mathcal{V*}>(G) = 1] = \Pr[\mathcal{V*} opens Commit(c_b(v);r_b)] $$

%\begin{equation*}
%	\begin{split}
%		 \Pr[<\mathcal{P},\mathcal{V*}>(G) = 1] &= \Pr[<\mathcal{P},\mathcal{V*}>(G) = 1 | b=0].\Pr[b=0] + \Pr[<\mathcal{P},\mathcal{V*}>(G) = 1 | b=1].\Pr[b=1] \\
%		 &= \frac{1}{2}\Pr[\mathcal{D}(Commit(c_0;r_0)) = 0] + \frac{1}{2}\Pr[\mathcal{D}(Commit(c_1;r_1)) = 1] \\
%		 &= \frac{1}{2}(1-\Pr[\mathcal{D}(Commit(c_0;r_0)) = 1] + \frac{1}{2}\Pr[\mathcal{D}(Commit(c_1;r_1)) = 1] \\
%		 &= \frac{1}{2} + \frac{1}{2}(\Pr[\mathcal{D}(Commit(c_1;r_1)) = 1] - \Pr[\mathcal{D}(Commit(c_0;r_0)) = 1]) \\
%		 &\leq \frac{1}{2} + \frac{1}{2} | \Pr[\mathcal{D}(Commit(c_1;r_1)) = 1] - \Pr[\mathcal{D}(Commit(c_0;r_0)) = 1]) | \\
%	\end{split}
%\end{equation*}


\textbf{Commitment binding reduction using P:}\\
Consider a malicious prover $\mathcal{P*}$ which goal is to make $\mathcal{V}$ accept an invalid coloring assignment for $G$ by opening the committed coloring of a vertex to a valid one, even when it was committed to an invalid color. Let $\mathcal{A}$ be a PPT adversary for the commitment binding game and $\mathcal{O}$ be the corresponding oracle. The game goes as follows:

\begin{enumerate}
	\item $\mathcal{A}$ builds a uncolorable graph $G=(E,V)$, such that at least one vertex $v_1 \in V$ cannot have a valid coloring, and sends $G$ to $\mathcal{P*}$.
	\item $\mathcal{A}$ receives a list of committed color assignment : $y_i \leftarrow Commit(c(v_i);r_i)$ with $v_i \in V$ and $r$ a random value.
	\item $\mathcal{A}$ sends $e = (v_1,v_2)$, which is colorable but shares $v_1$ with the uncolorable edge $e'$, as a challenge to $\mathcal{P*}$.
	\item $\mathcal{P*}$ sends $r_1,r_2$ to $\mathcal{A}$.
	\item $\mathcal{A}$ opens $y_1$: $c(v_1) = Open(y_1;r_1)$.
	\item $\mathcal{A}$ rewinds to step 3 and sends the uncolorable edge $e'=(v_0,v_1)$ as a challenge.
	\item $\mathcal{P*}$ sends back $r_0,r_1'$ to $\mathcal{A}$.
	\item $\mathcal{A}$ opens $y_1$: $c'(v_1) = Open(y_1;r_1')$.
	\item $\mathcal{A}$ sends $(y_1,c(v_1),r_1,c'(v_1),r_1')$ to $\mathcal{O}$.
\end{enumerate}

Let $\Pr[\mathcal{A}(y_1,c(v_1),r_1,c'(v_1),r_1')=1]$ be the probability of $\mathcal{A}$ winning this game and $\Pr[\mathcal{P*}(Open(y_1;r_1')=c'(v_1))=1]$ be the probability of $\mathcal{P*}$ to find an $r_1'$ to open $y_1$ to $c'(v_1)$, a valid coloring for $v_1$. We have:

$$ \Pr[\mathcal{A}(y_1,c(v_1),r_1,c'(v_1),r_1')=1] = \Pr[\mathcal{P*}(Open(y_1;r_1')=c'(v_1))=1] $$

From the commitment binding property, we know that $\Pr[\mathcal{A}(y_1,c(v_1),r_1,c'(v_1),r_1')=1] \leq \eta(n)$, with $\eta$ a negligible function over the commitment scheme's security parameter $n$. As a result, we also have:

$$ \Pr[\mathcal{P*}(Open(y_1;r_1')=c'(v_1))=1] \leq \eta(n) $$

From these 2 reductions, we get the probability that a malicious prover $\mathcal{P*}$ succeeds in making $V$ accept an uncolorable graph:

$$ \Pr[<P*,V>(G) = 1] \leq 1 - \frac{1}{|E|} + \eta(n) + \epsilon(n) = 1 - \frac{1}{|E|} + \nu(n) $$
with $\nu = \eta + \epsilon$ a negligible function over the commitment scheme security parameter $n$.\\

By repeating this protocol $k$ times, we can reduce the probability of $\mathcal{V}$ accepting when no valid 3-coloring for $G$ exists to:
$$ \Pr[<P*,V>(G) = 1] \leq (1 - \frac{1}{|E|} + \nu(n))^k $$


\begin{simulator} \textbf{(Sequential)} \\
Let $\mathcal{V*}$ be an untrusted PPT verifier and $\mathcal{S}$ be a PPT simulator such that: 

\begin{enumerate}
	\item $\mathcal{S}$ and $\mathcal{V*}$ both receive the graph $G = (V,E)$ as input.
	\item $\mathcal{S}$ receives the commitment value of an arbitrary edge from $\mathcal{V*}$: $x \leftarrow Commit(e;r*)$ with $e \in E$.
	\item $\mathcal{S}$ computes a random 3-colors assignment for $G$: $c(v_i)$ such that $c: V \rightarrow \{1,2,3\}$ and $v_i \in V$.
	\item $\mathcal{S}$ computes the commitment of each $c(v_i)$: $y_i \leftarrow Commit(v_i;r_i)$, and sends the list of committed values to $\mathcal{V*}$.
	\item $\mathcal{S}$ receives a challenge edge $e$ and verifies it corresponds to the received commitment $x$.
	\item $\mathcal{S}$ opens $y_j$ and $y_k$ such that $e = (v_j,v_k)$: $c(v_j) = Open(y_j,r_j)$ and $c(v_k) = Open(y_k,r_k)$.
	\item If $c(v_j) = c(v_k)$, $\mathcal{S}$ re-assigns valid colors to $v_j$ and $v_k$ such that $c(v_j) \neq c(v_k)$ and rewinds to step 5. Otherwise, $\mathcal{S}$ sends $c(v_j)$ and $c(v_k)$ to $\mathcal{V*}$. 
\end{enumerate}

\end{simulator}

Because the simulator can re-assign a valid coloring to the challenge vertices and re-wind to before it committed the coloring, we have:
$$ \Pr[\mathcal{V*} \textit{ accepts}] = \Pr[c(v_j) \neq c(v_k) ] = 1 $$



\begin{protocol} \textbf{(Parallel)} \\

Let $\mathcal{P}$ be an unbounded prover and $\mathcal{V}$ be a PPT verifier. The zero-knowledge protocol for $3COL$ goes as follows: 

\begin{enumerate}
	\item $\mathcal{P}$ and $\mathcal{V}$ both receive the graph $G = (V,E)$ as input.
	\item $\mathcal{V}$ randomly draws a list of $n$ edges such that $e_m = (v_j,v_k)$ with $v_j,v_k \in V$, $m \in 1,\cdots,n$, .
	\item $\mathcal{V}$ computes a commitment for each $e_m$: $x_m \leftarrow  Commit(e_m;r_m)$, and sends the list of $x_m$ to $\mathcal{P}$.
	\item $\mathcal{P}$ receives a 3-coloring assignment for $G$: $c(v_i)$ such that $c: V \rightarrow \{1,2,3\}$ and $v_i \in V$.
	\item $\mathcal{P}$ computes $n$ different permutation of the original coloring: $c_m = \pi_m(c)$.
	\item For each permuted coloring, $\mathcal{P}$ computes the commitment of each $c_m(v_i)$: $y_i \leftarrow Commit(v_i;r_i)$ and sends the list of committed values to $\mathcal{V}$.
	\item $\mathcal{V}$ opens $x$: $e = Open(x,r)$,  and sends $e$ as a challenge to $\mathcal{P}$.
	\item $\mathcal{P}$ opens $y_j$ and $y_k$ such that $e = (v_j,v_k)$: and sends $c(v_j),c(v_k)$ to $\mathcal{V}$.
	\item $\mathcal{V}$ rejects if the corresponding coloring is invalid, \textit{i.e.} $c(v_j) = c(v_k)$.
\end{enumerate}

\end{protocol}

If the 3-coloring computed by $\mathcal{P}$ is a valid one, then:
$$\Pr[<P,V>(G) = 1] = \Pr[c(v_j) \neq c(v_k) ] = 1 $$


otherwise, there exists at least one edge $e = (u,v)$ such that $c(u) = c(v)$ and we have:
$$ \Pr[c(u) = c(v) ] = \frac{1}{|E|}$$

\end{document}