\documentclass[a4,slidesec,semhelv]{seminar}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{lastslide}

\newcommand{\compclass}[1]{\ensuremath{\mathbf{#1}}}
\newcommand{\NP}{\compclass{NP}}
\newcommand{\IP}{\compclass{IP}}
\newcommand{\CZK}{\compclass{CZK}}
\newcommand{\PSPACE}{\compclass{PSPACE}}
\newcommand{\BPP}{\compclass{BPP}}
\newcommand{\AM}{\compclass{AM}}

\newcommand{\problem}[1]{\textsc{#1}}
\newcommand{\SAT}{\problem{sat}}

\newcommand{\abs}[1]{\ensuremath{\lvert#1\rvert}}

\newcommand{\field}[1]{\ensuremath{\mathbb{#1}}}
\newcommand{\N}{\field{N}}
\newcommand{\Z}{\field{Z}}
\newcommand{\R}{\field{R}}


\newcommand{\ssim}{\ensuremath{\overset{s}{\sim}}}
\newcommand{\csim}{\ensuremath{\overset{c}{\sim}}}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\formula}{formula}
\DeclareMathOperator{\enccirc}{encCirc}
\DeclareMathOperator{\answer}{answer}
\DeclareMathOperator{\test}{check}

\theoremstyle{definition}
\newtheorem{Def}{Definition}
\newtheorem{Thm}[Def]{Theorem}
\newtheorem{Lem}[Def]{Lemma}
\newtheorem{Cla}[Def]{Claim}

\author{Johan Wall\'{e}n}

\title{Four Rounds Are Optimal for Zero Knowledge}
       
\date{October 10, 2001}


\slideframe{none}

\newpagestyle{mypagestyle}%
  {\slshape HUT T-79.511. Four Rounds Are Optimal for Zero Knowledge. %
   \hfil \theslide~(\pageref{LastSlide})}% 
  {\slshape johan.wallen@hut.fi \hfil \thedate}

% \raggedslides
\begin{document}



\begin{slide}
  \slidepagestyle{empty}
  \addtocounter{slide}{-1}

  \maketitle
\end{slide}

\slidepagestyle{mypagestyle}

\begin{slide}
  \section*{Motivation}
  If one-way functions exists, all languages in $\IP$ ($=\PSPACE$)
  have computational zero-knowledge proofs.

  Are one-way functions also \textbf{necessary}?
  \begin{itemize}
    \item Increases our understanding of the relationships between
    $\CZK$ and other cryptographic primitives.
    \item Shows that zero knowledge proofs build from any one-way
    function are \textbf{optimal}: they use the weakest assumptions 
    possible.
  \end{itemize}

  The answer is positive: One-way functions are indeed essential.  

\end{slide}

\begin{slide}
  \section*{Motivation continued}

  Zero knowledge proofs and arguments are fundamental building blocks
  for larger cryptographic protocols. In these applications, the
  \textbf{round complexity} is important.

  What is the optimal number of rounds?
  \begin{itemize}
    \item Any three round protocol is trivial. If a language $L$ has a
    three round $\CZK$ proof or argument, $L \in \BPP$.
    \item Four round $\CZK$ \textbf{arguments} built from any one-way
    function exist for all of $\NP$.
  \end{itemize}
\end{slide}


\begin{slide}
  \section*{Interactive proofs and arguments}

  Recall that an interactive proof system $(V, P)$ for $L$ consists of 
  \begin{itemize}
    \item A probabilistic polynomial time verifier $V$.
    \item An unrestricted prover $P$.
  \end{itemize}
  
  For common input $x$, $P$ and $V$ interacts by exchanging at most
  polynomially many messages of polynomial length. The protocol is
  ended by $V$ either accepting or rejecting $x$.

  The \textbf{transcript} $\langle V, P\rangle(x)$ consists of $x$ and
  all exchanged messages.

  The number of \textbf{rounds} is the total number of messages
  exchanged. 
  \newslide

  We require that the error probability is negligible: For some
  negligible function $\epsilon$ and all sufficiently large $x$,
  \begin{description}
    \item[Completeness:] $x \in L \Longrightarrow \Pr(V\
    \text{accepts}\ x) > 1 - \epsilon(\abs{x})$.
    \item[Soundness:] For all provers $P'$, $x \not\in L
    \Longrightarrow \Pr(V\ \text{accepts}\ x) < \epsilon(\abs x)$.
  \end{description}


  If $P$ and all provers $P'$ in the soundness condition are
  restricted to probabilistic polynomial time, we get an interactive
  \textbf{argument}. 
\end{slide}

\begin{slide}
  \section*{Computational indistinguishability}
  Let $X = \{X_n\}_{n \in \N}$, and $Y =
  \{Y_n\}_{n \in \N}$ be probability ensembles, where each $X_i$, $Y_i$
  range over strings of length $n$. 

  The ensembles are said to be
  \textbf{computationally indistinguishable}, written as $X \csim Y$, if
  for every probabilistic polynomial time algorithm $A$,
  \[
    d_A(n) = \abs{\Pr(A(X_n) = \top) - \Pr(A(Y_n) = \top)}
  \]
  is a negligible function of $n$.
\end{slide}

\begin{slide}
  \section*{Computational zero knowledge}

  An interactive proof (or argument) $(V, P)$ is a \textbf{black-box
  computational zero knowledge proof (argument)} for $L$, if
  there is a generic oracle calling algorithm $S$ (the
  \textbf{simulator}) running in expected polynomial time, such that for
  all verifiers $V'$, 
  \[
    \{\langle V', P\rangle(x)\}_{x \in L} \csim \{S^{V'}(x)\}_{x \in L}. 
  \]
\end{slide}

\begin{slide}
  \section*{Four rounds are needed}

  The main result covered in the survey is
  \begin{Thm}[Goldreich and Krawczyk, 1996]
    A language $L$ has a three round black-box computational zero
    knowledge proof or argument if and only if $L \in \BPP$.    
  \end{Thm}

  \begin{proof}[Proof sketch]
    Let $(P, V)$ be a three round zero knowledge proof or argument for
    $L$, and let $S$ be the 
    black-box simulator. We will derive a $\BPP$ algorithm deciding
    $L$. The algorithm $A$ will use $S$ as a subroutine to distinguish
    between $x \in L$ and $x \not \in L$.

    Let $x$ be the input, and $n = \abs x$.  

    \newslide

    \paragraph{The protocol:} First, $P$ sends $\alpha$ to $V$. $V$
    responds with $\beta$. Finally, $P$ sends $\gamma$ to $V$, and the
    protocol is terminated by $V$ accepting or rejecting.

    $\beta$ is a function of $x$, $\alpha$, and $V$'s random string
    $r$: $\beta = \beta_V(x, r, \alpha)$. Let $\rho_V$ be the
    predicate used by $V$ in order to accept or reject. For
    convenience, we assume that this is a deterministic function:
    $\rho_V(x, \alpha, \beta, \gamma)$. 

    \newslide

    \paragraph{The simulation:} Let $V^*$ be any verifier, and write
    $S = S^{V^*}$. The simulation process consist of several tries.
    In each try, the simulator feeds $V^*$ with the arguments $y$ (the
    input) and $\alpha$ (the prover's message). Let $\beta = V^*(y,
    \alpha)$ be the response of $V^*$ in this try. We can assume the
    following 
    \begin{itemize}
      \item $S$ always outputs a transcript of the form $(x, \alpha,
      \beta, \gamma)$, where $(x, \alpha)$ are fed to $V^*$ in some try,
      and $\beta = V^*(x, \alpha)$ is the response in this try.
      \item $S$ runs in polynomial worst-case time. Let $t(n)$ be a
      polynomial bound on the number of tries by $S$ for inputs of
      length $n$.
    \end{itemize}

    \newslide

    \paragraph{The $\BPP$ algorithm $A$:} A crucial observation is
    that the simulation process is completely determined by $x$, the
    random string of $S$, and the responses of the verifier.

    The algorithm $A$ operates as follows. First, it picks a random
    string $R_S$ for $S$ and $t = t(n)$ random strings $r^1, \ldots,
    r^t$. The simulator $S$ is used as a subroutine with $x$ as input
    and $R_S$ as random string.

    Whenever $S$ invokes the verifier with arguments $y$ and $\alpha$,
    we find the first unused $r^i$ and respond with $\beta^i =
    \beta_V(x, r^i, \alpha)$. If $S$ invokes the verifier with the
    same $\alpha$ more than once, we return the same $\beta$ as the
    last time, regardless of the value of $y$.

    Note that the conversation is uniquely specified by $x$, $R_S$, and
    $r^1, \ldots, r^t$. Thus, we can define the function $\conv_S(x,
    R_S, r^1, \ldots, r^t)$ to be the resulting transcript.

    \newslide 

    Let $\alpha^i$ be the $i$th different value of $\alpha$ output by
    $S$ during the simulation. Clearly, $\alpha$ is a function of $x$,
    $R_S$, and $r^1, \ldots, r^{i-1}$, $\alpha^i = \alpha_S(x, R_S,
    r^1, \ldots, r^{i-1})$. 

    By our assumptions, if $\conv_S(x, R_S, r^1, \ldots, r^t) = (x,
    \alpha, \beta, \gamma)$, $S$ tried $(x, \alpha)$ in some try, Thus,
    there is an $i$ such that $\beta = \beta_V(x, r^i, \alpha)$.

    \begin{Def}
      A vector $(x, R_S, r^1, \ldots, r^t)$ is \textbf{$S$-good}, if
      $\conv_S(x, R_S, r^1, \ldots, r^t) = (x, \alpha, \beta, \gamma)$
      and $\rho_V(x, \alpha, \beta, \gamma) = \top$.
    \end{Def}

    The algorithm $A$ accepts $x$ if and only if $(x, R_S, r^1,
    \ldots, r^t)$ is $S$-good.

    \newslide

    Since $S$ and $V$ runs in polynomial time, $A$ runs in polynomial
    time. By the following two technical lemmas, $A$ can distinguish
    between $x \in L$ and $x \not\in L$ with small enough error
    probability. Thus, $L \in \BPP$.
  \end{proof}

    \begin{Lem}
      For $x \not \in L$, only a negligible fraction of the vectors
      $(x, R_S, r^1, \ldots, r^t)$ are $S$-good.
    \end{Lem}

    \begin{Lem}
      For $x \in L$, a non-negligible fraction of the vectors $(x,
      R_S, r^1, \ldots, r^t)$ are $S$-good.
    \end{Lem}

\end{slide}

\begin{slide}
  \section*{One-way functions are essential}

  Another important result briefly discussed in the survey is
  \begin{Thm}[Ostrovsky and Wigderson, 1993]
    Under the assumption that auxiliary input one-way functions does
    not exist, if $L$ has a $\CZK$ proof, then $L \in \BPP$.
  \end{Thm}
\end{slide}

\begin{slide}
  \section*{An optimal zero knowledge argument}

  Given these result, it is natural to ask if there are four round
  computational zero knowledge proofs or arguments build from any
  one-way function for languages outside $\BPP$.

  A partial answer is discussed in the survey: a four round $\CZK$
  \textbf{argument} built from any one-way function is sketched for the
  $\NP$ complete \SAT.

  The protocol [Bellare, Jakobsson, and Yung, 1997] uses an atomic
  commitment based four round zero knowledge proof 
  with error probability $0.5$. The basic idea is to run several
  independent copies of the atomic protocol in parallel. With some
  care, this gives a four round $\CZK$ argument for $\SAT$ with
  negligible error probability.

\end{slide}

\end{document}

