% Search for PPP
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Modified by Cynthia, June 17, 1999
%     Added 5-round Protocol II' and proof of co-zk and soundness
%     (Left Amit's 7-round II' commented out after the bibliography text.)
%
%     Added the 12-round Protocol II'' (we should improve our nomenclature),
%     together with proof of ordinary zk and soundness for this protocol.
%     Restored several paragraphs that had been omitted for lack of space.
%
%     Search for ``cynthia2:'' or ``Cynthia2:'' for other miscellany.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Proofs for II,II' modified by Amit.
% Currently working on II'.  II should be easier.
% Giving up for time being on II';  correcting II.
%
%Modified by Cynthia.  Search for cd2.
%Modified by Cynthia.  Search for cd1.
%\documentstyle[fullpage,epsf]{article}
\documentstyle[epsf,amsfonts]{article}
%\documentstyle{ACMconf}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% yashmac.tex : useful macros, by Yashash
%
% requires AMS TeX symbol fonts msam & msbm.
% use the tweaked mssym.sty (or the original amssym.def) to
% define the symbols.
%
% requires epsf.sty (for postscript)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%                              some math shorthand
%                              -------------------
%
%                                AMS TeX symbols
%                                ---------------
%
%            Include, center &scale encapsulated postscript figures
%            ------------------------------------------------------
%#1 - caption, #2 - filename, #3 - label, #4 - Xsize
%
%For example -
%
% \filefig{Legend of bag components} {Fig/bag.pstex}
% {bag.pstex}{4.75in}
%
\hyphenation{the-or-etic}
\newcommand{\filefig}[4]{
  \begin{figure}[thpb]
    \begin{center}
      \setlength{\epsfxsize}{#4}
      \leavevmode
      \epsfbox {#2}
      \caption{\protect {#1}}
      \label {#3}
    \end{center}
  \end{figure}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% mboxit.sty
% version: 25-6-92
%
% Stolen from 'boxit.sty' by Marcel van der Goot, marcel@cs.caltech.edu
% Corrupted by Avishai Wool, yash@wisdom.weizmann.ac.il to fit
%    snuggly around tabbing env with thin left/right margins.
%
% Defines a boxit environment, which draws lines around its contents.
% Usage:
%   \begin{boxit}
%       ... (text you want to be boxed, can contain other environments)
%   \end{boxit}
%
% The width of the box is the width of the contents.
% The boxit* environment behaves the same, except that the box will be
% at least as wide as a normal paragraph.
%
% The reason for writing it this way (rather than with the \boxit#1 macro
% from the TeXbook), is that now you can box verbatim text, as in
%   \begin{boxit}
%   \begin{verbatim}
%   this better come out in boxed verbatim mode ...
%   \end{verbatim}
%   \end{boxit}
%

\def\Beginboxit{%
    \vbox\bgroup
           \hrule
           \hbox\bgroup
                  \vrule \kern12pt %       left margin
                  \vbox\bgroup\kern1.2pt %   top
   }
\def\Endboxit{%
                              \kern-1.5ex      %  kill extra space below
                       \egroup
                  \kern12pt\vrule        % right margin
                \egroup
           \hrule
         \egroup
   }

\newenvironment{boxit}{\Beginboxit}{\Endboxit}
\newenvironment{boxit*}{\Beginboxit\hbox to\hsize{}}{\Endboxit}




\setlength{\evensidemargin}{.25truein}
\setlength{\oddsidemargin}{.25truein}
%\setlength{\textwidth}{6.0truein}
\setlength{\textwidth}{6.5truein}
\setlength{\topmargin}{0.25truein}
\setlength{\textheight}{8.5truein}
%\setlength{\textheight}{9.00truein}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% control keywords for algorithms
%
\newcommand{\If}{{\bf if }}
\newcommand{\Then}{{\bf then }}
\newcommand{\Else}{{\bf else }}
\newcommand{\Endif}{{\bf end-if }}
\newcommand{\While}{{\bf while }}
\newcommand{\Endwhile}{{\bf end-while }}
\newcommand{\Until}{{\bf until }}
\newcommand{\Repeat}{{\bf Repeat }}
\newcommand{\Do}{{\bf do }}
\newcommand{\Enddo}{{\bf end-do }}
\newcommand{\For}{{\bf for }}
\newcommand{\Endfor}{{\bf end-for }}
\newcommand{\Return}{{\bf return }}
\newcommand{\st}{\, \vert \,} %puts vertical bar with space around it
\newcommand{\sidecomment}[1]{{\sloppy \marginpar{\tiny #1}}}


\def\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt
\hskip 1pt}}
\def\QED{\quad\blackslug\lower 8.5pt\null\par}
%\def\proof{\par\penalty-1000\vskip .5 pt\noindent{\bf Proof\/: }}



\newcommand{\ms}[1]{{\it #1}}
%                           -- numbered separately...

% \remove{
% before the text to be excluded and
% }
% after the text

\newcommand{\pre}{{\bf Precondition:}}
\newcommand{\eff}{{\bf Effect:}}
\def\inpt{{\it input}}
\def\del{{\it del}}
\def\fail{{\it fail}}
\def\comp{{\it comp}}
\def\to{T}
\def\tend{{t_{\it end}}}
\def\fin{{\it final}}
\def\halted{{\it halted}}
\def\smalldel{\delta}
\def\bigd{D}
\def\bigdel{\Delta}
\def\last{\ms{last}}
\def\Zeta{\zeta}
\def\l{\ell}
\def\BC{{\bf BCK}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\commit{\mbox{\sc basic commit}}
\def\P{{\cal P}}
\def\A{{\cal A}}
\def\D{{\cal D}}
\def\S{{\cal S}}
\def\M{{\cal M}}
\def\reveal{\mbox{\sc reveal}}
\def\BC{{\bf BCK}}
\def\MBC{{\bf MBCK}}
\def\ACS
{\langle (P,V), (C,D), ~\A:\psi(B) \leftrightarrow \psi(C) \rangle}
\def\CZK{Concurrent ZK}
\def\IV{intended value}
\def\h{{\mbox{hist}}}
\def\zo{\{0,1\}}
\newcommand{\qedsymb}{\hfill{$\Box$}}
%\newenvironment{proof}{\begin{trivlist}
%\item[\hspace{\labelsep}{\em\noindent Proof: }]
%}{\qedsymb\end{trivlist}}
%\newcommand{\qed}{\hfill\rule{2mm}{2mm}}
%\renewcommand{\topfraction}{1}
%\renewcommand{\textfraction}{0}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%CYNTHIA: took these out so the margin comments will print
%AMIT: these are way over requirements
%\setlength{\evensidemargin}{.25truein}
%\setlength{\oddsidemargin}{.25truein}
%\setlength{\textwidth}{6.0truein}
%%\setlength{\textwidth}{6.5truein}
%\setlength{\topmargin}{0.25truein}
%\setlength{\textheight}{8.5truein}
%%\setlength{\textheight}{9.00truein}
%\setlength{\headheight}{0in}
%\setlength{\headsep}{0in}

\def\bdm{\begin{displaymath}}
\def\edm{\end{displaymath}}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\benum{\begin{enumerate}}
\def\eenum{\end{enumerate}}
\def\bcen{\begin{center}}
\def\ecen{\end{center}}
\def\ls{\{\,}
\def\rs{\,\}}
\def\lb{[\,}
\def\rb{\,]}
\def\type1{computational}
\def\ni{\noindent}
\def\NN{\hbox{$\rlap{I} \> \kern-.2mm{\rm N}$}}
\def\RR{\hbox{$\rlap{\rm I} \> \kern-.2mm{\rm R}$}}
\def\ZZ{\hbox{$\rlap{Z} \> {\rm Z}$}}

% theorem-like environments -- numbered together...
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{corollary}[theorem]{Corollary}
%     -- numbered separately...
\newtheorem{assumption}{Assumption}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{remarks}[theorem]{Remarks}
\newtheorem{definition}{Definition}[section]
\newtheorem{claim}{Claim}[section]

%PPP Added definition
\newtheorem{proto}{Protocol}


% to get nice proofs ...
\def\qed{\mbox{\ \ \ $\Box$}}
\def\rqed{\mbox{ }~\hfill~$\Box$}
\newenvironment{proof}{\begin{trivlist}
\item[]{\it Proof.}}{\qed\end{trivlist}}
\newenvironment{proofr}{\begin{trivlist}
\item[]{\it Proof.}}{\rqed\end{trivlist}}
%\newenvironment{proof}{\begin{trivlist}
%\item[\hspace{\labelsep}{\it\noindent Proof. }]
%}{\qedsymb\end{trivlist}}

\def\cent{\hbox{\rm\rlap/c}}
\def\str{\raise.3ex\hbox{\tenrm{*}}}
\def\ccdot{\!\cdot\!}
\def\cross{\!\times\!}
\def\ve{\varepsilon}
\def\th{{\rm th}}
\def\emp{\emptyset}
\def\Pr{{\mbox Pr}}
\newcommand{\len}[1]{\vert #1 \vert}
\newcommand{\setof}[2]{\{\,{#1}\mid {#2}\,\}}% Set (as in \setof{x}{x>0})
\newcommand{\focs}[3]{{\it Proc. #1th IEEE Symp. on Foundations
of Computer Science}, 19#2, pp.~#3.}
\newcommand{\stoc}[3]{{\it Proc. #1th ACM Symp. on Theory of
Computing}, 19#2, pp.~#3.}
\newcommand{\podc}[3]{{\it Proc. #1th ACM Symp. on Principles
of Distributed Computing}, 19#2, pp.~#3.}
\newcommand{\jacm}[3]{{\it J. Assoc. Comput. Mach.} #1 (19#2), pp.~#3.}
\newcommand{\sicomp}[3]{{\it SIAM J. Comput.} #1 (19#2), pp.~#3.}
\newcommand{\jcss}[3]{{\it J. Comput. System Sci.} #1 (19#2), pp.~#3.}
\newcommand{\tcs}[3]{{\it Theor. Comput. Sci.} #1 (19#2), pp.~#3.}
\newcommand{\ipl}[3]{{\it Inform. Proc. Lett.} #1 (19#2), pp.~#3.}
\newcommand{\ic}[3]{{\it Information and Computation\/}
#1 (19#2), pp.~#3.}

\newcommand{\remove}[1]{}
\newcommand{\op}[1]{} %out of proceedings
\newcommand{\lackofspace}[1]{}
%\newcommand{\cd}[1]{}
%\newcommand{\cdthree}[1]{\marginpar{\raggedright \tiny cd: #1}}
\newcommand{\cdthree}[1]{\begin{quote} {\it Question: #1} \end{quote}}
\newcommand{\cd}[1]{\marginpar{\raggedright \tiny cd: #1}}
%\newcommand{\mn}[1]{}
%\newcommand{\mn}[1]{\marginpar{\raggedright \tiny mn: #1}}
%\newcommand{\as}[1]{\marginpar{\raggedright \tiny as: #1}}

\newcommand{\cdtwo}[1]{}
%\newcommand{\cdtwo}[1]{\marginpar{\raggedright \tiny cd2: #1}}
\remove{
\newcommand{\cd}[1]{\marginpar{\raggedright \tiny cd: #1}}
}

\def\dist{{\it dist}}
\def\calS{{\cal S}}
\def\calL{{\cal L}}
\def\calG{{\cal G}}
\def\calC{{\cal C}}
\def\calI{{\cal I}}
\def\calH{{\cal H}}
\def\F{{\cal F}}
\def\lan{\langle}
\def\ran{\rangle}





\def\Z{{\mathchoice {\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\textstyle Z\kern-0.4em Z$}}
{\hbox{$\sf\scriptstyle Z\kern-0.3em Z$}}
{\hbox{$\sf\scriptscriptstyle Z\kern-0.2em Z$}}}}
\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm
Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}
{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise
0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}}


\def\PtoV{P \longrightarrow V:}
\def\VtoP{V \longrightarrow P:}
\def\VwithP{V \longleftrightarrow P:}
\def\PwithV{P \longleftrightarrow V:}
\def\KtoS{K \longrightarrow S:}
\def\StoK{S \longrightarrow K:}

\def\siml{simulateable}
%\def\pka{public key authentication}
%\def\Pka{Public key authentication}
\def\pka{deniable authentication}
\def\Pka{Deniable authentication}
\def\PKA{Deniable Authentication}
\def\tce{$t$-concurrent-execution}
\def\ZK{zero-knowledge}
\def\cek{concurrent $\varepsilon$-knowledge}

\begin{document}
%%%%% %%%%%%%%\begin{titlepage}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%cd2 added footnote.  This might screw up counters.
\title{Concurrent Zero-Knowledge\footnote{A preliminary version
of this work appeared in STOC'98}}
\author{Cynthia Dwork\footnotemark[1]  \and Moni Naor\footnotemark[2]
\and Amit Sahai\footnotemark[3]}
%\date{}

\maketitle
\thispagestyle{empty}

\footnotetext[1]{IBM Research Division,
Almaden Research Center, 650 Harry Road,
San Jose, CA 95120, USA.
Research supported by
BSF Grant 32-00032-1.
E-mail: dwork@almaden.ibm.com.}
\footnotetext[2]{Dept.\ of Computer Science and
Applied Mathematics,
Weizmann Institute of Science, Rehovot 76100, Israel.
Some of this work performed while at the IBM Almaden Research Center.
Research supported by
BSF Grant 32-00032-1.
E-mail: naor@wisdom.weizmann.ac.il.}
%\footnotetext[3]{MIT Laboratory for Computer Science,
%545 Technology Square, Cambridge, MA.  02139.
%Most of this work performed while at the IBM Almaden Research Center.
%Also supported by a DOD NDSEG doctoral fellowship.
%E-mail: amits@theory.lcs.mit.edu}
\footnotetext[3]{MIT Laboratory for Computer Science,
545 Technology Square, Cambridge, MA.  02139, USA.
Most of this work performed while at the IBM Almaden Research Center.
Also supported by a DOD NDSEG doctoral fellowship and partially
by DARPA grant DABT63-96-C-0018.
E-mail: amits@theory.lcs.mit.edu}


\renewcommand{\thefootnote}{\arabic{footnote}}





\begin{abstract}
Concurrent executions
of a zero-knowledge
protocol by a single prover (with one or more verifiers)
may leak information and may not be zero-knowledge {\it in toto}.
In this paper, we study the problem
of maintaining zero-knowledge

We introduce the notion of an
{\em $(\alpha,\beta)$ timing constraint}:
for any two  processors $P_1$ and $P_2$,
if $P_1$  measures $\alpha$ elapsed time on its local clock and
$P_2$ measures $\beta$ elapsed time on its local clock, and
$P_2$ starts
{\em after} $P_1$ does,
then $P_2$ will finish after $P_1$ does.
We show that if the adversary is constrained by an $(\alpha,\beta)$
assumption then there exist
four-round almost concurrent zero-knowledge interactive proofs
and perfect concurrent zero-knowledge arguments
for every language in $NP$.
We also address the more specific problem of
 {\it Deniable Authentication}, for which we
propose several particularly efficient solutions.
Deniable Authentication is of independent interest, even
in the sequential case; our concurrent solutions
yield sequential solutions {\em without recourse to timing},
{\it i.e.}, in the standard model.
\end{abstract}

%%%%%% %%%%%%%%\end{titlepage}

\section{Introduction}

%amit1: Changed for style
In a distributed computing aggregate,
a collection of physically separated processors 
communicate via a heterogeneous network.
To date, research applications of cryptographic techniques
to distributed systems
have overwhelmingly concentrated on the paradigm
in which the system consists of
$n$ mutually aware processors trying to cooperatively
compute a function of their respective
inputs
%cd1: we should have a long list here of recent papers on multiparty
%computation and secret sharing
(see {\it e.g.} \cite{BGW,GMW2}).
In distinction with this traditional paradigm,
processors in an aggregate in general do not
know of all the other members,
nor do they generally know the topology of the network.
The processors are typically {\it not} all trying cooperatively
to compute one function or perform a specific set of tasks;
in general no coordination is assumed.
A prime example of an aggregate is the Internet.
%cd1 should we say web instead of internet?

Electronic interactions over an aggregate, such as
economic transactions, transmission of medical
data, data storage, and telecommuting, pose
security risks inadequately addressed in
computer science research.
In particular, the issue of the security
of {\em concurrent} executions is often ignored.
%cd1 eliminated this until related work section
%(but not always; see, {\it e.g.},  \cite{BR}, in a different setting).
In this paper we address the problem of
maintaining zero-knowledge under concurrency,
continuing research initiated in~\cite{DDN}
on zero-knowledge interactions in an aggregate.

\iffalse
Informally, an interactive proof is a protocol in which
a computationally unbounded prover $P$ attempts to convince
a probabilistic polynomial-time verifier $V$ of an assertion,
\ie that a string $x$ is in a language $L$.
Following the framework laid out by Goldwasser, Micali,
and Rackoff~\cite{GoldwasserMiRa89},
we consider two probability distributions in defining zero-knowledge:
\begin{enumerate}
\item The interaction of $P$ and $V$ from $V$'s
point of view.
\item The output of a probabilistic polynomial-time
machine not interacting with anyone, called the {\em simulator}, on
input $x$.
\end{enumerate}
We say an interactive proof system $(P,V)$ for $L$ is {\em
zero-knowledge} against $V$ (the {\em honest verifier}),
if for every input $x$ in
$L$, the two distributions above are ``alike.''  Intuitively,
the verifier gains no knowledge
by interacting with the prover except
that $x\in L$, since it could have run the simulator instead.  The
specific variants of zero-knowledge differ by the interpretation given
to ``alike.''  The most strict interpretation, leading to {\em perfect
zero-knowledge}, requires that the distributions be identical.  A
slightly relaxed interpretation, leading to {\em statistical
zero-knowledge}, requires that the distributions have negligible
statistical deviation from one another.  The most liberal
interpretation, leading to {\em computational zero-knowledge},
requires that samples from the two distributions be indistinguishable
by any polynomial-time machine.
\fi

\subsection{Description of the Problem}
\label{illustration}

A zero-knowledge protocol is supposed to ensure that no information
is leaked during its execution.
More specifically, but still informally,
a Black-Box Zero-Knowledge Interactive Proof
between a prover $P$ and probabilistic
polynomial time verifier $V$ on input $x$ satisfies
\begin{list}{}{}
\item{soundness}:
$\Pr[V~{\rm{accepts}} \,|\, x \notin L ] \le \nu(n)$
\item{completeness}:
$\Pr[V~{\rm{accepts}} \,|\, x \in L ] \ge 1-\nu(n)$
\item{black-box zero-knowledge}:
$\exists \mbox{ polynomial-time oracle machine}S
\, \forall V^* \, \forall x \in L$
$S^{V^{*}}[x] \approx_{poly} (P,V^*)[x]$.
\end{list}
If the prover is polynomial-time bounded, then the interaction
is called an {\em argument}~\cite{GMR}.
%cd1 add other citations?

For concreteness, we will consider an interactive proof
for graph Hamiltonicity.
For this we need a {\em string commitment} primitive.
Roughly speaking, string commitment has two phases.
During the {\em commit} phase, a {\em sender} and a {\em receiver}
interact to produce a conversation $\alpha$ that
represents a string $s$.  The receiver should gain no
information about $s$.  If the secrecy of $s$ depends on the
computational boundedness of the receiver, we use the notation
$\alpha \in C(s)$.  If the secrecy of $s$ is information-theoretic,
then we use the notation $\alpha \in K(s)$.
A commitment protocol in which the secrecy is information-theoretic
is sometimes called a {\em strong-receiver} commitment, since
secrecy is preserved even against a computationally unbounded receiver.

During the {\em reveal} phase, the sender reveals $s$ together
with information proving that $\alpha$ is a commitment to $s$.
When $\alpha \in C(s)$, there is only one possible value $s$
that can be revealed, no matter how powerful the prover.
When $\alpha \in K(s)$, since secrecy is information-theoretic,
$\alpha$ can be opened to {\em any} value $s'$; in this case
its computational boundedness ensures that the sender
will be unable to find two different ways of opening the commitment.
%cd1 add citations to Naor and to BCC'88?

As is well known,
graph Hamiltonicity can be proved in black-box zero-knowledge using
the sequential iteration of the following basic block,
due to Manuel Blum~\cite{Bl}.
In the first message, the prover commits to the adjacency matrix
of a graph.  The commitment is bit-by-bit, that is, each bit
is committed to individually.

\noindent
Basic Block:
\begin{tabbing}
xx\= xxxXXXxx \= xxx\= \kill
\>$\PtoV$ $C$(adjacency matrix $A$ of random permutation $\pi(G)$)\\
\>$\VtoP$ $b \in_R \zo$\\
\>$\PtoV$ \>If $b = 0$ then reveal $\pi$ and open $A$\\
\>      \>If $b=1$ then reveal a Hamiltonian cycle in $A$
\end{tabbing}

In the na\"{\i}ve parallelization of this basic block,
the prover commits to $n$ adjacency matrices,
receives a vector of $n$ bits, and, according to the $i$th
bit, reveals either the $i$th permuation and
the $i$th adjacency matrix, or the cycle in the
the $i$th adjacency matrix.
However, the proof
that the basic block is zero-knowledge fails
for the na\"{\i}ve parallelization.
Indeed, there is no 3-round black-box zero-knowledge
proof or argument for any language not in BPP~\cite{GK}.
However, in order to parallelize the basic block
it suffices for the verifier to commit to the vector of queries
in advance:

\noindent
\begin{tabbing}
Protocol Parallel-Hamiltonicity:\\
4. \= $\VtoP$ \=  \kill
1. \> {$\VtoP$} {$K$}{$(\vec{q})$}\\
2. \> {$\PtoV$}
        ${C(Adj(\pi_1(G)), \dots, Adj(\pi_n (G)))}$\\
3. \> {$\VtoP$}
        {open $\vec{q}$}\\
4. \> {$\PtoV$ reply to queries}
\end{tabbing}
%cd1 attribution here? GMW or Feige Shamir?
The simulation runs as follows.

\noindent
\begin{tabbing}
3'=3. \= $\VtoP$ \=  \kill
Simulation:\\
{1}. \>  {$\VtoP K(\vec{q})$}\\
2. \>  $\PtoV C(garbage)$\\
{3.} \> ${\VtoP {\rm ~open~} \vec{q}}$\\
{2'}.   \> {$\PtoV$} {Commit to graphs}\\
{3'=3}. \>${\VtoP {\rm ~open~} \vec{q}}$\\
{4.} \> {$\PtoV$ reply to queries}
\end{tabbing}
where Step 2' is repeated as often as necessary
in order to get a reply from $V$ in Step~3'.
When Protocol Parallel-Hamiltonicity is run concurrently,
say, by a single prover interacting with multiple verifiers,
the simulation fails in a manner analogous to the failure
of the simulation of the na\"{\i}ve parallelization of the basic block.
Since there are many verifiers, and
since they are not all known to the prover (or provers) before interaction
with the first verifier begins, there is no algorithmic
way to force all subsequent verifiers to commit to their
queries before the first interaction begins.
\remove{
(There may be meta-methods, for example, involving
certified public keys
for the verifiers, but we do not consider such approaches
here, and in any case at best such methods move the burden to some
initial step.)
}
Consider the following {\em nested} interleaving,
shown in Diagram 1 below, of $n$
colluding verifiers $V_1,\ldots,V_n$
concurrently executing Protocol Parallel-Hamiltonicity with
a single prover.

$$
\begin{array}{c}
%\mbox{Colluding Verifiers interacting with the Prover}\\
\begin{array}{cccc}
V_1 & V_2 & \ldots &  V_n \\
\mbox{Step } 1\\
\mbox{Step } 2\\
&\mbox{Step } 1\\
&\mbox{Step } 2\\
&&\vdots\\
&&&\mbox{Step } 1\\
&&&\mbox{Step } 2\\
&&&\mbox{Step } 3\\
&&&\mbox{Step } 4\\
&&\vdots\\
&\mbox{Step } 3\\
&\mbox{Step } 4\\
\mbox{Step } 3\\
\mbox{Step } 4\\
\end{array}
\end{array}
$$
\begin{center}
{{\em Diagram 1.} A troublesome interleaving.}
\end{center}








\remove{
However, when zero-knowledge interactions are executed {\em concurrently}
both parties can be at risk.
Consider the case of zero-knowledge proofs:
the verifier faces the possibility that the
prover with which it is interacting is actually
using some concurrently running second interaction as
an ``oracle'' to help answer the verifier's queries --
this is the classic chess master's problem.
Thus, for example in the case of a proof of knowledge,
the interaction may not actually yield a {proof}.
This is an issue of potential {\em malleability} of the
interactive proof system, and is addressed in~\cite{DDN}.

The {prover} faces the risk that concurrent executions
of a protocol by a single prover (with one or more verifiers)
may leak information and may not be zero-knowledge {\it in toto}.
(The problem is slightly more general than this; we elaborate
in Section~\ref{defs}.)
In this case the interaction remains a proof but may fail
to remain {zero-knowledge}.
To date, no zero-knowledge proof system has been proven zero-knowledge
under concurrent execution.
%cynthia: softened reference to KP
 Indeed, recent work of Kilian, Petrank and Rackoff
 suggests that certain types of
 four-round interactive proof systems and arguments\footnote{
In an {\em argument} the prover is polynomial time bounded.}
 cannot remain zero-knowledge
 under concurrent execution~\cite{KPR}.%\footnote{
%%Furthermore we conjecture that such proofs are impossible for any
%number of rounds.}. \mn{What do you think about this conjecture?}
%\cd{deleted the conjecture about none existing.}
% In contrast,
% there exist four-round (non-concurrent) zero-knowledge interactive
% proofs and arguments for every language in $NP$ (for
% a recent discussion see \cite{BJY}).

%\cd{Naor-Ostrovsky-? paper?}
%\as{Modified paragraph structure of this part; original is commented.}
%The situation is reminiscent of the case of {\em parallelizing}
%the iterations of any given zero-knowledge interactive proof $(P,V)$
%consisting of a basic block that is iterated some number $k$
%of times in order to ensure that the verifier will accept
%the proof of a false statement with a probability that shrinks
%exponentially in $k$.
The situation is reminiscent of the case of {\em parallelizing}
the iterations of a zero-knowledge interactive proof $(P,V)$.
Such a proof consists of a basic block that is iterated $k$
times in order to ensure that the verifier will accept
the proof of a false statement with a probability that shrinks
exponentially in $k$.
For example, if the basic block consists of
\begin{tabbing}
XXX \= xxx\= \kill
\>$\PtoV$ Commit to $M_0, M_1$\\
\>$\VtoP$ $b \in_R \zo$\\
\>$\PtoV$ open $M_b$
\end{tabbing}
then the parallelization looks like
\begin{tabbing}
XXX \= xxx\= \kill
\>$\PtoV$ Commit to $M_0^1, M_1^1, \dots, M_0^k, M_1^k$\\
\>$\VtoP$ $b_1 \dots b_k \in_R \zo^k$\\
\>$\PtoV$ open $M_{b_1}, \dots, M_{b_k}$
\end{tabbing}
This natural parallelization is probably {\em not} zero-knowledge; indeed
Goldreich and Krawczyk have shown that if $L$ is any language having
a three-round zero-knowledge (black-box simulatable)
proof with negligible probability
of error, then $L \in BPP$~(see \cite{GK} for this and analogous
results for zero-knowledge arguments
and constant round Arthur-Merlin
games).

In many cases the parallelization can be modified to achieve zero-knowledge
by prepending a step in which the verifier commits to $b_1, \dots, b_k$
(see~\cite{BCY,fs,GK}):
\begin{tabbing}
XXX \= xxx\= \kill
\>1. $\VtoP$ Commit to $b_1, \dots, b_k$\\
\>2. $\PtoV$ Commit to $M_0^1, M_1^1, \dots, M_0^k, M_1^k$\\
\>3. $\VtoP$ open $b_1, \dots, b_k$\\
\>4. $\PtoV$ open $M_{b_1}, \dots, M_{b_k}$
\end{tabbing}
Since the verifier is completely committed to its queries
before the prover sends any message,
the simulation is easy: commit to random noise, wait until the
verifier reveals its queries,
%(which it will do with probability
%subpolynmially close to the probability with which it opens
%its commitment during a real execution, by the semantic security
%of the commitment scheme),
then re-wind and choose a new sequence
of commitments so that the --- now known ---
queries $b_1, \dots, b_k$ can be answered, and finish the simulation.
%Note that we should be careful to make sure
To ensure that the prover's commitments
at Step~2 are independent of the verifier's commitments at Step~1,
%can be achieved, for instance, by making
the Step~1 commitments are strong-receiver.


%cynthia: reworded slightly
In the concurrent scenario,
since there are many verifiers, and
since they are not all known to the prover (or provers) before interaction
with the first verifier begins, there is no algorithmic
way to force all subsequent verifiers to commit to their
queries before the first interaction begins.
(There may be meta-methods, for example, involving
certified public keys
for the verifiers, but we do not consider such approaches
here, and in any case at best such methods move the burden to some
initial step.)
Consider the following {\em nested} interleaving,
shown in Diagram 1 below, of $n$
colluding verifiers $V_1,\ldots,V_n$
following the generic four-round protocol
described above with a single prover.
\iffalse
Suppose the different protocol executions
are nested as follows:
Steps~1,2 of the first execution of $P$ with $V_1$,
followed by Steps~1,2 with $V_2$, \dots, followed
by Steps~1,2 with $V_n$; then
Steps~3,4 with $V_n$, followed by Steps~3,4 with $V_{n-1}$,
\dots, followed finally by Steps~3,4 with $V_1$.
\fi

%\op{DELETED PICTURE
%cynthia: deleted one of the columns (and therefore 4 rows) to shorten
%the text
\op{
$$
\begin{array}{c}
\mbox{Colluding Verifiers interacting with the Prover}\\
\begin{array}{ccccc}
V_1 & V_2 & \ldots & V_{n-1} & V_n \\
\mbox{Step } 1\\
\mbox{Step } 2\\
&\mbox{Step } 1\\
&\mbox{Step } 2\\
&&\vdots\\
&&&\mbox{Step } 1\\
&&&\mbox{Step } 2\\
&&&&\mbox{Step } 1\\
&&&&\mbox{Step } 2\\
&&&&\mbox{Step } 3\\
&&&&\mbox{Step } 4\\
&&&\mbox{Step } 3\\
&&&\mbox{Step } 4\\
&&\vdots\\
&\mbox{Step } 3\\
&\mbox{Step } 4\\
\mbox{Step } 3\\
\mbox{Step } 4\\
\end{array}
\end{array}
$$
\begin{center}
{{\em Diagram 1.} A troublesome interleaving for concurrent zero-knowledge.}
\end{center}
}

$$
\begin{array}{c}
%\mbox{Colluding Verifiers interacting with the Prover}\\
\begin{array}{cccc}
V_1 & V_2 & \ldots &  V_n \\
\mbox{Step } 1\\
\mbox{Step } 2\\
&\mbox{Step } 1\\
&\mbox{Step } 2\\
&&\vdots\\
&&&\mbox{Step } 1\\
&&&\mbox{Step } 2\\
&&&\mbox{Step } 3\\
&&&\mbox{Step } 4\\
&&\vdots\\
&\mbox{Step } 3\\
&\mbox{Step } 4\\
\mbox{Step } 3\\
\mbox{Step } 4\\
\end{array}
\end{array}
$$
\begin{center}
{{\em Diagram 1.} A troublesome interleaving.}
\end{center}
%}%end of DELETED PICTURE
%\noindent
} %end of remove of most of original introduction
An adversary controlling the verifiers can arrange that
the Step~1 commitments to queries made by verifiers $V_{i+1}, \dots,$ $V_n$
can depend on messages sent by the prover in
Step~2 of its interaction with $V_i$.
The difficulty with the straightforward approach
is that once the queries in the interaction with $V_i$ are opened
(in Step~3), it becomes necessary to re-simulate Step~2 of the
interaction with $V_i$,
and therefore the entire simulation of the interaction with
verifiers $V_{i+1}, \dots, V_{n}$ must be re-simulated.
The most deeply nested transaction, with $V_n$, is simulated roughly
$2^{n}$ times.
It has recently been shown
that transcripts of this interleaving
cannot be simulated in probabilistic polynomial time
unless Hamiltonicity is in BPP~\cite{KPR}.

\iffalse
For example, in $t$ concurrent executions of the
generic four-round protocol
described above, an
adversary controlling the verifiers can arrange that
commitments to queries made by verifiers $i+1, \dots, t$
can depend on messages sent by the prover in
Step~2 of execution~$i$.
Suppose the different protocol executions
are {\em nested}:
Steps~1,2 of the first execution, $E_1$,
followed by Steps~1,2 of $E_2$, \dots, followed
by Steps~1,2 of $E_t$; then
Steps~3,4 of $E_t$, followed by Steps~3,4 of $E_{t-1}$, \dots,
followed by Steps~3,4 of $E_1$.
It is a well-known open problem how to simulate transcripts
with this interleaving in polynomial time;
the difficulty with the straightforward approach
is that once the queries in $E_i$ are opened (Step~3
of $E_i$), it becomes necessary to re-simulate Step~2 of $E_i$
and therefore the entire simulation of $E_{i+1}, \dots, E_{t}$.
The most deeply nested transaction, $E_t$, is simulated roughly
$2^{t}$ times.
%\as{got rid of roughly, changed to $2^{t-1}$.}
%\cd{put it back, since part of $E_t$ is simulated $2^t$ times --
%even if $t=1$.}
\fi

\subsection{Our Approach}
It is possible that the definition of zero-knowledge
({\it i.e.}, \siml) is too demanding:
interactions that leak no ``useful'' information may nonetheless not
be \siml.
This is the philosophy in~\cite{fs}, and the motivation for
{\em witness indistinguishability}.
In the same spirit, we suggest three ideas for exploration:
\begin{enumerate}
\item
introduce a notion of time to sufficiently restrict
the behavior of an adversarial scheduler that the
resulting execution is always \siml{}
(an {\em explicit} use of time);
\item
use ``moderately hard'' functions to enforce timing constraints
(an {\em implicit} use of time);
\item
enhance the power of the simulator or relax the
requirements on the output distribution.
%\as{perhaps ``ease the requirements on the simulator'' would be
%more accurate?}
\end{enumerate}
%Of these three, we have found the explicit use of time quite fruitful.
Our precise notion of an explicit use of time
is an {\it $(\alpha,\beta)$-constraint} (for
some $\alpha \leq  \beta$):
for any two (possibly the same) non-faulty processors $P_1$ and $P_2$,
if $P_1$  measures $\alpha$ elapsed time on its local clock and
$P_2$ measures $\beta$ elapsed time on its local clock,
and if in addition $P_2$ begins its measurement in real time no sooner than
$P_1$ begins,
then $P_2$ will finish no sooner than $P_1$ does.
\begin{remark}
\begin{enumerate}
\item
An $(\alpha,\beta)$ constraint is implied by most reasonable assumptions
on the behavior of clocks in a system ({\it e.g.} the
linear drift assumption).
\item
In the special case in which $P_1 = P_2$, the constraint
holds trivially.
In this case, the proofs are necessarily zero-knowledge,
and timing only affects completeness:
if $\alpha$
is too small (not allowing some parties sufficient time to compute
and send messages), then completeness may fail to hold.
\item In the general case,
the $(\alpha,\beta)$-constraint may be important for correctness of
the protocol for both parties involved,
{\it i.e.},  zero-knowledge in concurrent zero-knowledge proofs and arguments
(Protocols II and II')
and unforgeability (soundness)  and deniability in the Deniable Authentication
protocols (Protocols \ref{protIII} and \ref{protIV})
% and V),
discussed below.
\end{enumerate}
\end{remark}



%Cynthia: moved here so that the paragraphs follow the same order as the
%enumerated suggestions
%\mn{Are we ever using the shortcut, as opposed to the moderately-hard
%function? We could do a Dwork-Sahai type
%thing for the short-cut information
%and then finish the simulation once and for all}
It is often possible to partially eliminate the
explicit use of time from concurrent zero-knowledge arguments
by employing {\em moderately hard functions},
possibly  with {\em shortcut} information~\cite{dn}\footnote{
A short-cut behaves similarly to a trapdoor, except
that the gap between what can be computed
having the short-cut and not having the
short-cut is polynomial rather than the (conjectured) super-polynomial
gap between what can be done
having the trapdoor information and not having the trapdoor
information.}.
Intuitively, these functions are used in order to make
sure that a certain party operating within in a time limit $\alpha$ may not
extract secret information, but an off-line simulator having sufficient time
may extract this information; in this sense they supplement the
$(\alpha,\beta)$-constraint.



In some protocols we achieve
a slightly relaxed notion of zero-knowledge,  which we call
$\varepsilon$-knowledge,
requiring that for any polynomial time bounded
adversary $\A$ and for any $0 < \ve =o(1)$,
there exists a simulator running in time polynomial in the
running time of $\A$ and $\ve^{-1}$ that outputs
simulated transcripts with a
distribution $\ve$-indistinguishable from the distribution
on transcripts obtained when the prover interacts
with (verifiers controlled by) $\A$.
(By $\ve$-indistinguishable we mean that no polynomial time
%cd1 independent of \varepsilon?
observer
can distinguish the two distributions with advantage better than $\ve$.)
For a discussion of related topics, see~\cite{GP}.

To illustrate the significance of $\ve$-knowledge,
suppose we have a simulator that runs in time
$S(n,1/\varepsilon, \A(n))$,
where $\A(n)$ is the running time of an adversary $\A$ interacting
with the prover on inputs of length $n$.
Suppose further that
there is a task whose success can
be recognized ({\it e.g.}, solving an NP search problem or breaking
a particular cryptosystem).
Suppose that
%{\em after} viewing
%an $\varepsilon$-knowledge proof,
there is a procedure~$\Pi$ that takes part in an $\ve$-knowledge proof
and then solves
the given task.
Let $T(n)$ be the total running time of $\Pi$ (including the interaction
and the solving of the task) and let $P(n)$ be the probability
that $\Pi$ succeeds in solving the task.
Under the normal definition of zero-knowledge,
where the simulator runs in time $S'(n,\A(n))$,
we have that without the interaction
%seeing the proof,
one can complete the task in time $S'(n,T(n))$,
with success probability $P(n)-\mu(n)$, where $\mu(n)$ is negligible.

%cd1 where is \varepsilon here?
For our model, without the interaction, one can complete
the task in time $S(n,1/2 P(n),T(n))$, with success
probability $P(n)-P(n)/2 = P(n)/2$ (ignoring negligible terms).

Since we assume we can recognize when the task is completed
successfully, the claim above follows by a contradiction argument:
if the probability were smaller, then this task
would be a distinguisher between simulated and real
interactions with better than $P(n)/2$ distinguishing power,
a contradiction.

This implies in particular that if the original breaking task
could be achieved
in polynomial-time with an inverse polymomial probability of success
 after interacting in the $\ve$-knowledge proof,
then it will still be achievable in this way without
the interaction
(although possibly requiring much more time).




%cd2 changed title of section
\subsection{Deniable Authentication}
\label{authentication}

%cd2
The example of concurrent proofs of Hamiltonicity, described
in the previous section, provides
ample motivation for the study of concurrent zero-knowledge.
However, the impetus for our work came from the
problem of {\em concurrent deniable authentication}.
Deniable authentication first appears in~\cite{DDN},
which presents
an extremely simple protocol for what is there termed
{\em public key authentication},
a relaxation of digital signatures that permits an authenticator
$A\P$ to authenticate messages $m$ to a second party $V$, but
in which the authentication needn't
(and, to quote \cite{DDN}, ``perhaps shouldn't!'') be
verifiable by a third party.
To emphasize this last point we introduce the term {\em \pka}
and strengthen the definition in~\cite{DDN} by insisting on
{\em deniability}.
There are many reasonable definitions of deniability;
for this informal discussion one can think of
zero-knowledge.


%Specifically, a \pka{} scheme
%permits a party
%$P$ to {authenticate} a message $m$ of her choice to a second party $V$.
Similar to a digital signature scheme, a \pka{} scheme
can convince $V$ that $A\P$ is willing to authenticate
$m$.  However, unlike in the case of digital signatures, \pka{}
does not permit $V$ to convince a third party that $A\P$ has
authenticated $m$ -- there is no ``paper trail'' of the conversation
(say, other than what could be produced by $V$ alone, if
deniability is defined as zero-knowledge).
Thus, \pka{} is incomparable with digital signatures.
\Pka{} differs from the concepts of {\em undeniable signature}
introduced in 1989 by Chaum and Van Antwerpen~\cite{CVA}
and {\em chameleon signature} introduced by Krawczyk and  Rabin~\cite{KR},
in that \pka{} is {\em not} intended for
%\cd{mention designated verifier proofs?}
ultimate
adjudication by a third party, but rather to assure $V$ -- and only $V$ --
of the validity of the message
(see~\cite{GKR} for an excellent discussion of work on undeniable signatures).
In addition to addressing the privacy needs cited in the literature
on undeniable signatures,
zero-knowledge public key authentication also provides a solution to
a major commercial motivation for undeniable signatures: to provide proof of
authenticity of software to authorized/paying customers only.
In particular, proving authenticity of the software to a pirate
does not in any way help the pirate to prove authenticity
of pirate copies of the software to other customers.

Another nice application of \pka{} is in authenticating ``off the record''
remarks that are not for attribution.
The prover's public key allows a reporter to be certain of the
identity of the source while providing plausible deniability
to the source.
%When the remarks are for attribution the source could insist
%on the use of a digital signature in the attribution, actually
%providing a check for accidental misquoting.



The notion of non-malleable security for a
public key authentication scheme, defined in~\cite{DDN},
is analogous to that of
{\em existential unforgeability under
an adaptive chosen plaintext attack} for signature schemes~\cite{gmri},
while taking care of ``person-in-the-middle" attacks.
%Given an interactive protocol pair $(P,V)$, we
%distinguish between the protocols $P$ and $V$ and the
%{\em agents} $\psi(P)$ and $\psi(V)$ that are supposed to be executing
%these protocols.
%An {\it adversarially coordinated} system of interactive
%protocols
%$$\ACS$$
%consists of two interactive protocols
%$(P,V)$ and
%$(C,D)$, an
%adversary $\A$ controlling the agents
%$\psi(V)$ and $\psi(C)$,
%the communication between these agents, and
%the times at which these controlled agents take
%steps.
%Let $\ACS$ be an adversarially coordinated system
%in which $(P,V) = (C,D)$ is a public key authentication protocol.
%We assume
The definition can be described informally as follows
(see~\cite{DDN} for details).
Assume that an authenticator
$P$ is willing to authenticate
any polynomial number of messages
$m_1, m_2, \ldots$, which may be chosen adaptively by
an adversary $\A$.
We say that $\A$ successfully attacks the scheme if
a forger $C$, under control of $\A$ and pretending to be $P$,
succeeds in authenticating to a third party $D$
a message $m \not= m_i$, $i=1,2,\dots$.
Note that the forgery may occur concurrently with
valid authentications by $P$.

This definition describes the protection afforded to
the {\em verifier} (receiver) against an imposter trying to impersonate
the {\em prover} (authenticator) and falsely ``authenticating''
the message $m$.
A \pka{} protocol satisfying the above definition of non-malleable
security clearly also provides some protection for the prover/authenticator;
for example, even though the protocol may not be zero-knowledge,
it protects any private key used in the authentication
to a great extent -- otherwise it would be possible to impersonate
the authenticator by learning the private authentication key.

The following public key authentication protocol appears in
Section 3.5 of~\cite{DDN}
(see also \cite{dnpatent}).
$P$'s public key is $E$, chosen according to a generator of
%%%PPP  changed order
a non-malleable public key cryptosystems.
  Roughly
speaking, a public key cryptosystem is non-malleable
if, for all polynomial time relations $R$ (with certain trivial exceptions),
seeing an encryption $E(\alpha)$ ``does not help'' an attacker
to generate an encryption $E(\beta)$ such that $R(\alpha,\beta)$.
In particular, for this application
we require {\em non-malleability under chosen ciphertext
attack in the post-processing mode}, defined formally in~\cite{DDN}
and informally below.
In all our protocols we assume that the message $m$ to be authenticated
is a common input, known to both parties.
Also, if any message received is of the wrong format,
then the protocol is terminated.
In particular, if the message received by $P$ in Step~1 below
is not an encryption of a string with prefix $m$, then
$P$ terminates the protocol.
The concatenation of $x$ and $y$ is denoted $x \circ y$.

\begin{proto}
\label{prot0}

{\bf  Public Key Authentication}\\
\begin{tabbing}
XX \= xxxx\= yyyyyyyyY \= \kill
\>1. \>  $\VtoP$   $\gamma \in_R E(m \circ r)$,  $r \in_R \{0,1\}^n$\\
\>2. \>  $\PtoV$ \>            $r$
\end{tabbing}
\end{proto}
%PPP changed a bit
Although Protocol \ref{prot0} was proved in~\cite{DDN} (Lemma 3.6) to be
secure against {\em existential} forgery based on the
 non-malleability of $E$,
Protocol \ref{prot0} is not zero-knowledge.
% however non-malleable security, proved in~\cite{DDN},
%implies that no verifier (or set of verifiers) can
%learn enough information to impersonate the prover and
%spuriously authenticate messages.
Zero knowledge is easily achieved by having $V$ perform a
zero-knowledge proof of knowledge of $r$ before $P$ reveals~$r$.
(A zero-knowledge
interactive proof is a {\em proof of knowledge} if there
is a polynomial time simulator to {\em extract} the information
for which knowledge is being proved~\cite{ffs}.)
%cynthia: refined next sentence
Clearly, once the interaction is zero-knowledge it yields no
``paper trail''  of involvement %by the prover/authenticator,
under sequential executions by the same prover/authenticator.

%cynthia: kept this out of the final version, since we now have
%a better one.  KEEP IN THIS FILE.
\op{
The modified protocol is:
\begin{proto}
\label{protI}
{\bf  Sequential ZK \PKA}\\
\begin{tabbing}
XXX \= xxx\= \kill
\> 1. $\VtoP$ Commit to random $r$ using the scheme in~\cite{N}\\
\> 2. $\VwithP$ Zero-Knowledge interactive proof that $V$ knows $r$\\
\> 3. $\VtoP$ $E(m \circ r)$ and NIZK proof of consistency with Step~1\\
\> 4. $\PtoV$ $r$
\end{tabbing}
\end{proto}

In Step~2 the verifier proves interactively to the prover that
the verifier knows $r$; intuitively, this means that the
verifier will learn nothing in Step~3: both already know $m$ and
the verifier has just proved that it knows $r$.
Clearly, once it is zero-knowledge the interaction yields no
%cynthia: added the part about p/a's involvement
``paper trail'' of the prover/authenticator's involvement
%under any definition of paper trail,
under sequential executions by the same prover/authenticator.
However, the proof of zero-knowledge fails under concurrent
composition; that is, by nesting the executions,
essentially as described above, we obtain a
distribution on transcripts for which we
cannot find a good
probabilistic expected polynomial time simulator.
%
%Moreover, although conceptually divided into four steps, the protocol
%is not a four-round protocol (for example, Step~2 requires
%multiple rounds), so the Kilian-Petrank result does not apply.
%cynthia reworded slightly
We do not know if Protocol~\ref{protI}
 remains zero-knowledge under concurrent
executions by the same authenticator/prover.
Similarly, if there is a collection of authenticator/provers, all
using the same secret key, concurrent executions of the protocol
may not be zero-knowledge.

To help develop more intuition, we give
an additional example of a \pka{} protocol
that has frustrated our attempts to prove zero-knowledge under
concurrent executions.
}
The modified protocol is:
\begin{proto}
\label{protI}
{\bf  Sequential ZK \PKA}\\

\begin{tabbing}
XXX \= xxx\= \kill
\> 1. $\VtoP$ Choose $r \in_R \{0,1\}^n$ and send $E(m \circ r)$\\
\> 2. $\PtoV$ $E(r)$\\
\> 3. $\VtoP$ $s,r$, where $s$ is the string of random \\
\>\> bits used for the encryption in Step~1\\
\> 4. $\PtoV$ open $E(r)$
\end{tabbing}
\end{proto}

Sequential zero-knowledge (deniability) follows from simple rewinding.
Non-malleable security holds from the non-malleability property
of the encryption function under a strong
type of chosen ciphertext attack (seeing
$E(x)$ does not help in finding $E(\mbox{a suffix of x})$).
We were unable to prove that
Protocol~\ref{protI} remains zero-knowledge under concurrent executions, and
in light of the results of~\cite{KPR} this seems unlikely.
However, it is the next example that lead us to search for
new alternatives to zero-knowledge.
The protocol may not be sound, and is presented only for pedagogical
reasons.
This protocol requires a strong-receiver commitment scheme
$K_{g_1,g_2,p}(r)$~\cite{chp} to commit
to a string~$r$.
%cd1 citation for this commitment scheme?
$K_{g_1,g_2,p}(x)$ is defined as
follows: $g_1, g_2$ generate
%cynthia a --> the same
the same $q$-sized subgroup of $\Z_p^*$,
where $q$ is a large prime dividing $p-1$.
Given $g_1, g_2$, and $p$, commit to $x$
by sending
$g_1^x g_2^z \bmod p$ where $z \in_R \Z_q$.
Note that this is distributed uniformly in the subgroup
generated by $g_1$ for all $x$.
%\mn{Said that $q|p-1$}
Decommitment is by revealing $x$ and $z$.
Note that if the committer knows
$a$ such that $g_2 \equiv g_1^a \bmod p$, then the ``commitment'' can
be opened arbitrarily, so the security of the commitment
relies on the hardness of finding discrete logarithms modulo~$p$.
%If you know $g_1^x g_2^{r_1} = g_1^{x_2}g_2^{r_2}$
%then you can decommit.
%\mn{You can test the order, but let's not waist space on that}
%\cd{are we letting $V$ choose the $K$-parameters?}
\begin{tabbing}
X \= xxxxxx\= \kill
{\bf  Protocol P: SeqZK \PKA ? (may not be sound)}\\
\>1. $\VtoP$ $E(m \circ r)$, $g_1, g_2, p$\\
\>2. $\PtoV$ $K_{g_1,g_2,p}(r)$\\
\>3. $\VtoP$ $s,r$, where $s$ is the
string of random \\
\>\>bits used for the encryption in Step~1\\
\>4. $\PtoV$ open commitment to $r$\\
%PIM: can erase last bit of $r$ by setting $y' = yg_1$.
\end{tabbing}
Protocol~$P$ (for ``Pedagogical'') is readily
seen to be sequential zero-knowledge\footnote{%
The protocol may not be sound because of a malleability issue:
there could conceivably be some way for $P$ to write a string $\alpha$
in Step~2 as a function of what was received in Step~1, so that,
upon seeing the Step~3 message from $V$, $P$ can successfully open
$\alpha$ to $r$.}.
Intuitively, this protocol
``should be'' concurrent zero-knowledge as well,
since Step~2 yields
no information about $r$ {\em even information-theoretically}.
However, again
standard simulation techniques fail for the interleavings
described in Diagram~1.
This example -- the fact that we could not prove concurrent
zero-knowledge even though nothing is leaked information-theoretically
-- motivated us to seek an alternate definition of zero-knowledge,
giving rise to the results in this paper.




%\cd{What were we thinking of in ``questionable'' below?
%And, where does chameleon hashing appear?  It's not in GKR's
%Undeniable Signatures paper in CRYPTO'97.
%Move hierarchy discussion (in file) to a final section.}
\remove{
Other approaches: receiver has a public key

Hierarchy of deniability:\\
  signature: if you know the PUBLIC key it is not deniable\\
  undeniable: (prove or disprove by interacting with the real prover;
               funny: this is just the thing
               people refused to accept for verifiable secret sharing)
             if you know the PRIVATE key it is not deniable\\
  questionable: if you know the history (message) then it is not deniable
                chameleon hashing?  add sign(E(m)); then you don't need m
                if you know the private key\\
  deniable: if you know the PRIVATE key it is STILL deniable


chameleon hashing: can find collisions in $H_u$ if you know the secret info
(as above, the relationship between $g_1$ and $g_2$).
}


%cd1 made related work a subsection
\subsection{Related work}
The study of zero-knowledge in an aggregate was
initiated in~\cite{DDN}, who considered the soundness
of concurrent executions of zero-knowledge proofs of knowledge:
the verifier faces the possibility that the
prover with which it is interacting is actually
using some concurrently running second interaction as
an ``oracle'' to help answer the verifier's queries --
this is the classic chess master's problem.
Thus, for example in the case of a proof of knowledge,
the interaction may not actually yield a {proof}.
The problem is the possible
{\em malleability} of the
interactive proof of knowledge, formalized
and addressed in~\cite{DDN}.

For a discussion of attempts to construct
parallel (as opposed to concurrent)
zero-knowledge protocols, see \cite{BJY} and
Goldreich, Chapter 6~\cite{Gold}.
The problem of concurrent zero-knowledge was considered by several
groups including
Kilian, Petrank, and Rackoff \cite{KPR},
Bellare, Impagliazzo and
Jakobsson~\cite{BIJ}, and
Richardson and Kilian~\cite{RK}.
The first of these extends Goldreich and Krawczyk's results
on the impossibility of a 3-round black-box zero-knowledge proof for
membership in any language $L \notin BPP$, to show that
there is no 4-round {\em concurrent} black-box zero-knowledge
proof or argument for membership in any language $L \notin BPP$~\cite{KPR}.
%cd1 what does Impagliazzo et al. do?
The third shows the existence of (long) concurrent black-box
zero-knowledge proofs for any language in $NP$~\cite{RK}.
We will say more about this protocol below.

The use of timing considerations to ensure soundness and zero-knowledge
is new.  The only work of which we are aware that uses timing in
zero-knowledge protocols is Brands and Chaum \cite{BC},
in which very accurate timing is needed in order to
prevent person-in-the-middle attacks by distant processors (see also
Beth and Desmedt \cite{BD}).
Note that timing
has been suggested as a cryptanalytic tool -- the best example
is Kocher's timing attack~\cite{Kocher} -- so it follows that any
implementation of a cryptographic protocol must be time-aware in some sense.
The use of moderately hard functions was
introduced by Dwork and Naor~\cite{dn}, and their
application to time-capsules  was considered by
Bellare and Goldwasser~\cite{BG}.  The notion of ``time-lock
puzzles'' is discussed by Rivest, Shamir, and Wagner~\cite{rsw}.


\paragraph{Summary of Results:}
We introduce timing in order to obtain zero-knowledge
in concurrent executions.

We obtain four-round
concurrent $\varepsilon$-knowledge interactive proofs
and perfect concurrent zero-knowledge arguments
for every language in $NP$ under an $(\alpha,\beta)$ constraint.
The protocol remains zero-knowledge independent of how many
different theorems the prover (or provers) is proving in the
concurrent interactions (Section \ref{czkproofs}).
%cd1  Took the next sentence out of comments.  I assume it is true.
%we say something similar above.
This construction can be modified to give concurrent perfect
zero-knowledge arguments.
In Section~\ref{examples} we give several examples of
protocols for deniable authentication.
In particular, Protocols \ref{protIII} and \ref{protIV} are concrete and
efficient concurrent solutions to the problem.
When run without timing
these yield sequential solutions {\em in the standard model}.
%cd1 III will be Protocol I with timing.


\def\pept{{probabilistic, expected polynomial time }}
\def\ppt{{probabilistic polynomial time }}

\section{Model and Definitions}
\label{defs}
\paragraph{Timing.}
%cynthia: copied full definition of constraint here
In our protocols, processors (or machines) use local clocks to measure
elapsed time.
In any execution an {\em adversary scheduler} has control over
the timing of events, subject to
an $(\alpha,\beta)$-constraint
(for some $\alpha \leq  \beta$):
for any two (possibly the same) non-faulty processors $P_1$ and $P_2$,
if $P_1$  measures $\alpha$ elapsed time on its local clock and
$P_2$ measures $\beta$ elapsed time on its local clock,
and if in addition $P_2$ begins its measurement in real time no sooner than
$P_1$ begins,
then $P_2$ will finish no sooner than $P_1$ does.
The particular constraint may vary between protocols and must
be stated explicitly as part of the description of any protocol.
\iffalse
Consider a particular two-party protocol $(P,V)$.
When several executions are running concurrently, we do not distinguish
between the scenario in which a single machine runs multiple
copies of, say, $P$, and that in which multiple machines
possibly holding the same secret information, as
could be in the case of
message authentication, are concurrently running $P$.
The phrase ``copy of $P$''  applies equally to these two
scenarios.
\fi

\paragraph{Zero-Knowledge and Concurrent Zero-Knowledge}
In the original ``black box'' forumulation of
zero-knowledge proof systems~\cite{gmr},
%We first follow the original formulation of~\cite{gmr} to
%define zero-knowledge for proof systems\footnote{We
%use the ``black-box'' formulation.}.
an interactive proof system
$(P,V)$
for a language $L$
is computational (or perfect) {\em zero-knowledge}
if there exists a \pept  oracle machine $S$, called the
{\em simulator}, such that for every \ppt verifier
strategy $V^*$, the distributions $(P,V^*)(x)$ and
$S^{V^*}(x)$ are computationally indistinguishable (or identical)
whenever $x \in L$.
Here, formally, the machine $V^*$ is assumed to take as input
a partial conversation transcript, along with a random tape,
and output the verifier's next response.
This defintion also holds in the case of
arguments or computationally-sound proofs, where the
prover and verifier are both \ppt machines.


To investigate preservation of zero-knowledge in a distributed
setting, we consider a \ppt adversary that controls many verifiers
simultaneously.  Here, the adversary $\A$ will take as input
a partial conversation transcript of a prover interacting
with several verifiers concurrently.
Hence the transcript includes with each
message sent or received by the prover,
the local time on the prover's clock at which the event occurred.
The output of $\A$ will either be a tuple
$({\mbox{\rm receive}},V,\alpha,t)$, indicating that $P$ receives message
$\alpha$ from $V$
at time $t$ on $P$'s local clock, or
$({\mbox{\rm send}},V, t)$, indicating that $P$ must send a message to $V$
at time $t$ on $P$'s local clock.
The adversary must output a local time for $P$ that
is greater than all the times given in the transcript that
was input to $\A$ (the adversary cannot rewind $P$),
and standard well-formedness conditions must apply.
If these conditions are not met, this corresponds to a non-real
situation, so such transcripts are simply discarded.
\remove{
time on $P$'s local
clock, indicating the next time at which $P$ will
an event and, together with a time on $P$'s local
clock if the event occurs
a tuple either of the form $(V,\alpha)$ or $(t,V)$.
If the output is $(t,V,\alpha)$,
$V$ identifies a verifier (which may be new to the conversation)
that sends the message $\alpha$ to $P$; $t$
is a vector specifying
the local times on each party's clock at which the message $\alpha$
was sent or received.
If the output is $(\t,V)$,
this specifies the local times on each party's clocks $\t$ at which
$P$'s next message to verifier $V$ must be sent or received.
}
Note that we assume
that if the adversary specifies a response time $t$ for the prover that
violates a timing constraint of the protocol with $V$,
the prover should
answer with a special null response which invalidates the remainder
of the conversation with verifier $V$.
The distribution of
transcripts generated by an adversary $\A$ interacting with
a prover $P$ on common input $x$ is denoted $(P\leftrightarrow \A)(x)$.

An argument or proof system $(P,V)$ for a language $L$
is computational (or perfect) {\em concurrent zero-knowledge}
if there exists a \pept oracle machine $S$ such that
for every \ppt adversary $\A$, the distributions
$(P\leftrightarrow \A)(x)$
and $S^{\A}(x)$ are
computationally indistinguishable (or identical) whenever
$x \in L$.

An argument or proof system $(P,V)$ for a language $L$
is computational {\em concurrent $\varepsilon$-knowledge}
if for every $\varepsilon>0$,
there exists an oracle machine $S$, such that
for every \ppt adversary $\A$, the running time
of $S^{\A}$ is polynomial in $n$ and $1/\varepsilon$, and
any \ppt machine $B$ that attempts to distinguish between
the distributions
$(P\leftrightarrow \A)(x)$
and $S^{\A}(x)$ will have advantage at most $\varepsilon$ whenever
$x \in L$.


When the prover acts honestly and follows the
protocol, it does not matter
if there is a single entity that is acting as the prover for all verifiers,
or if there are many entities that are acting as provers for subsets
of the verifiers, since the actions of the provers would be the same,
and in our model, the timing of events is controlled by the adversary.

\remove{%No need for NIZKs any more
We now introduce some of hte tools used in the constructions

\paragraph{NIZK.}
In a non-interactive zero-knowledge (NIZK)
proof~\cite{BY,BDMP,BFM,FLS}
the prover $P$ and verifier $V$ have a common input $x$ and also
share a random string $\sigma$, called the reference
string, of length polynomial in the
length of $x$.
To convince the verifier of the
membership of $x$ in some fixed $NP$ language $L$,
the prover is allowed to send the verifier a single message
$m=P(x,\sigma)$, computed (probabilistically)
as a function of $x$ and $\sigma$.  The \ppt verifier must decide
whether or not to accept as a function of $x$, $\sigma$, and $m$.
Such an interaction $(P,V)$ is an NIZK proof system for $L$ if:
(1) If $x \in L$, for all $\sigma$, $(P,V)(x,\sigma)$ accepts.
(2) If $x \notin L$, for all $P^*$, the probability over $\sigma$ and
the random coins of $P$ and $V$ that
$(P^*,V)(x,\sigma)$ accepts is negligible.
(3) There exists a \ppt simulator $S$ such that,
if $x \in L$, then the distributions $S(x)$ and $(\sigma,P(x,\sigma))$,
where in the latter distribution $\sigma$ is chosen uniformly,
are computationally indistinguishable.
We further ask that the prover be
probabilistic polynomial time, but also allow that
in the case when $x \in L$,
the prover is given a witness $w$ for the membership of $x \in L$.
The distribution $(\sigma,P(x,\sigma,w))$
must be computationally indistinguishable from $S(x)$ no matter how
the witness $w$ is chosen.
%cynthia: added next sentence and deleted everything after it.
%note this requires another reference.
We use the variant proposed by~\cite{FLS}, in which
any polynomial number of $NP$ statements can be proven in
zero-knowledge using the same reference string $\sigma$
(see~\cite{KP1} for a more efficient implementation).
%\cite{FLS,BY} show that such NIZK proof systems with efficient provers
%exist for every
%language in $NP$ assuming trapdoor permutations
%exist.  Note that the definition above gives
%``bounded'' NIZK proof systems, {\it i.e.}, a given reference
%string $\sigma$ can be used to prove only one $NP$ statement.
%We also require unbounded NIZK proof systems, in which
%
%\cite{DY,FLS} have shown that the existence of a
%bounded NIZK proof system for an $NP$-complete language $L$
%with an efficient prover
%implies the existence of unbounded NIZK proof systems with
%efficient provers for any language in $NP$.  A precise definition
%of unbounded NIZK can be found in~\cite{BY,BDMP,FLS}.

%cynthia: omitted (it didn't belong here anyway; came from DS):
%Note that NIZK proofs are truly non-interactive only if the
%prover and the verifier already agree on a random string $\sigma$.
%Furthermore, if the distribution of $\sigma$ is far from uniform,
%then the zero-knowledge condition fails to hold.
%This issue motivates our concurrently simulable random selection protocol,
%described below.

\iffalse
In proving zero-knowledge, we construct a simulator
whose task, intuitively, is to produce a transcript of
a ``typical'' multi-execution (multiple concurrent protocol
executions).
During a simulation, the adversary controls the timing of events,
as in an actual execution.  As in the traditional
solitary zero-knowledge scenario,  the simulator can ``rewind''
the adversary to any point in time, and also
controls the inputs and messages of the
non-faulty machines.
We use the term {\em transcript} to describe communications
during a concurrent execution; the term {\em conversation}
refers to a {\em single} prover/verifier interaction.
\fi

} %of remove

%cynthia: decided to change this to strong-sender
%\def\type1{computational}
\def\type1{strong-sender}
\paragraph{String Commitment.}
A {\em string commitment} protocol between sender $A$
and receiver $B$ consists of two stages:
(1) The {\em commit} stage:  $ A$ has a string $\alpha$
 to which she wishes
to commit to $ B$. She and $ B$ exchange messages. At the end
of the stage $B$ has some information that represents $\alpha$,
but $B$ should gain no information about the value of $\alpha$.
(2)The {\em reveal} stage: at the end of this stage $B$ knows
$\alpha$.
The literature discusses two types of bit or string commitment:
{\em \type1{}} and {\em strong-receiver}.
%cynthia2: deleted next sentence because of new terminology.
%These terms describe the type of secrecy of the
%committed values offered by the scheme.
In \type1{} string commitment there is only one possible
way of opening the commitment.
Such a scheme is designed to be secure against a
probabilistic polynomial time
receiver and an arbitrarily powerful sender.
In strong-receiver commitment it is possible to open
the commitment in two ways, but the assumed computational
boundedness of the sender prevents him from finding a second
way.
Such a scheme is designed to be secure against an arbitrarily
powerful receiver and a probabilistic polynomial time prover.
See~\cite{DDN} for a formal definition of \type1{} commitment.


We require that $\alpha$ be semantically secure to $B$.
Roughly speaking, this means that $B$ has no ``useful'' information about
$\alpha$.
Clearly, if the commitment is information-theoretic it is
semantically secure.
%cynthia: ommitted details from proceedings
For the case of \type1{} security,
we follow~\cite{DDN}, and specify
what this means using the notions of security with
respect to relations (as shown in~\cite{DDN}, this is equivalent to
the traditional definition of semantic security \cite{gm}).
The following discussion is from~\cite{DDN}.

Let $\A$ be
an adversary that  produces a distribution $\cal M$
on strings of length $\ell(n)$
computable in probabilistic polynomial time.
A string $\alpha \in_R {\cal M}$ is chosen and $\cal A$ receives $\h(\alpha)$,
where $\h$ is a probabilistic polynomial time computable function.
The commitment protocol is executed where $A$ follows the protocol and
$B$ is controlled by $\cal A$.
The adversary $\A$ then produces a
string $\beta$. We assume that the prefix of $\beta$ is the description of
$\cal M$.

$\A$ is considered to have succeeded
with respect to $R$ if $R(\alpha,\beta)$.
Let $\pi(\A,R)$ be the probability that $\A$
succeeds with respect to $R$.
The probability is over
 the coin-flips of $\A$, and the
choice of $\alpha$.

For the second probability,
we have an adversary
simulator $\A'$ who will not have access to the string commitment protocol,
but has, however,  the same computational power
as $\A$.
 $\A'$ chooses a distribution $\cal M'$.
An $\alpha\in_R {\cal M'}$ and  $\h(m)$ is given to $\A'$.
$\A'$ produces $\beta$.
As above, $\A'$ is considered to have succeeded
with respect to $R$ if $R(\alpha,\beta)$ holds.

In information-theoretic string commitment, we require
that the committer should with overwhelming probability
be able to open the commitment in at most one way: any
polynomial ability of the prover to find two openings of
the commitment should translate into a polynomial probability
of solving some underlying problem assumed to be intractable.







\paragraph{Non-Malleability.}
This was introduced in~\cite{DDN} as a natural
strengthening of semantic security better suited to
a distributed computing aggregate.
Informally,
in the context of encryption
the additional requirement is that
given the ciphertext it is impossible to generate
a {\it different} ciphertext so that the respective
plaintexts are related.
The same concept makes sense in the contexts of
string commitment and
zero-knowledge proofs of possession of knowledge.
In this paper we use non-malleable public-key cryptosystems
resilient to the following chosen ciphertext attack in
the post-processing mode~\cite{RS}:
The adversary has a ciphertext message $c \in E(m)$ she wishes
to attack.  She is given access to a decryption mechanism, to which
she can make polynomially many adaptively chosen queries with one
exception: she cannot submit the query~$c$.

{\em Malleability} specifies what it means
to ``break'' the cryptosystem. Informally, given a
probabilistic polynomial
time computable relation $R$ (with certain
trivial restrictions) and
a ciphertext of a message $\alpha$, the attacker
is considered successful if she creates a
{\em ciphertext} of $\beta$ such that $R(\alpha, \beta)  =1$.
The cryptosystem is
non-malleable if for every attacker $\cal A$ there is
an ${\cal A}^{\prime}$ that, without access to the ciphertext of
$\alpha$,
 succeeds with similar probability as $\cal A$ in creating a
ciphertext of $\gamma$ such that $R(\alpha, \gamma)=1$.
A formal definition can be found in~\cite{DDN}.


\paragraph{Deniable Authentication.}

We now summarize the
  requirements of a deniable authentication scheme, as discussed in Section
\ref{authentication}. The prover or authenticator $P$
publishes a public-key $E$. The verifier knows the public-key
and following  the execution of an authentication protocol
it  decides whether to accept or reject the session as an authentication
of a message $m$.
Consider an adversary
$\cal A$ that controls the communication of
several copies of a prover $P$ who are not aware of each other
and control the verifiers with whom they interact.

The authentication protocol should satisfy:
\begin{description}
\item[Completeness]
For any message $m$,
if the prover and verifier follow the protocol for
authenticating the message $m$, then
the verifier accepts; this can be relaxed to
``accepts with high probability."
\item[Soundness - Existential Unforgeability] Consider an adversary
$\cal A$ as above.
Suppose that the copies of  $P$ are willing to authenticate
any polynomial number of messages
$m_1, m_2, \ldots$, which may be chosen adaptively by
the adversary $\A$.
We say that $\A$ successfully attacks the scheme if
a forger $C$, under control of $\A$ and pretending to be $P$,
succeeds in authenticating to a third party $D$ (running the
verifier's $V$ protocol)
a message $m \not= m_i$, $i=1,2,\dots$.
The soundness requirement is that all probabilistic
polynomial time $\cal A$ will succeed
with negligible probability.
\item[Zero-Knowledge - Deniability]
Consider an adversary
$\cal A$ as above and
suppose that the copies of  $P$ are willing to authenticate
any polynomial number of messages.
Then for each $\cal A$ there exists a polynomial-time simulator
that outputs an indistinguishable transcript.
Two possible relaxation are: (1) allow the
simulator to depend on $\varepsilon$  ($\varepsilon$ -knowledge)
(2) Let the  simulator have access to the {\em real} $P$
when it produces the simulatoted transcript, but $P$
would be authenticating some fixed sequence of
messages (and not the ones that were actually authenticated).
\end{description}




\section{Concurrent Zero-Knowledge Proofs and Arguments}
\label{czkproofs}

In this section we show how applying timing constraints can help in designing
in designing concurrent zero-knowldge protocols for proof and argument systems.
We first present in Section
\ref{epsilonk} a four round ``generic"
 protocol for NP and show that it is concurrent $\varepsilon$-konwledge.
In Section \ref{DLP} we  present a 5-round protocol for NP,
which under the hardness of the discrete log assumption is
concurrent zero-knowledge. In Section \ref{general} we show two
nore involved protocols
 that achieve this property but can can be based on general
assumptions
  (existence of one-way functions)

\subsection{Generic $\varepsilon$-Knowledge}
\label{epsilonk}
We now show that adding timing constraints
to Protocol Parallel-Hamiltonicity yields
a protocol for \cek{} proofs of Hamiltonicity.
Thus, every langauge in NP has a \cek{} proof.
There is nothing magical about the Hamiltonicuty protocol;
any ``natural" prtocol for an NP-Compelte problem
could also be used).

%Amit:problematic:
%as well as proofs of knowledge.
%PPP
\remove { %Why do we need it?
The protocol can be modified to
yield concurrent perfect zero-knowledge arguments
at little extra cost.
}

\remove{ %repetition!
\noindent
\begin{tabbing}
Protocol II:\\
4. \= $\VtoP$ \=  \kill
1. \> {$\VtoP$} {$K$}{$(\vec{q})$}\\
2. \> {$\PtoV$}
        ${C(Adj(\pi_1(G)), \dots, Adj(\pi_n (G)))}$\\
3. \> {$\VtoP$}
        {open $\vec{q}$}\\
4. \> {$\PtoV$ reply to queries}
\end{tabbing}
} %end of remove of repetition!

\remove{
In that protocol, the prover chooses a random
permutation $\pi$ of the graph $G$ and sends to the
verifier for every pair of vertices $i$ and $j$,
a commitment to the existence or nonexistence of the edge $(i,j)$.
The verifier chooses a random bit $q$.  If $q=0$, the prover
opens all the commitments and sends the permutation $\pi$; if $q=1$,
the prover reveals only those edges in a Hamiltonian circuit.
The verifier either checks that the graph revealed really
maps to $G$ under $\pi^{-1}$, or that all the edges revealed
really do form a Hamiltonian circuit.

This is iterated $n$ times, where $n$ is the size of the graph or
a security parameter.

In the parallelized version, all $n$ executions will be run
concurrently, with the verifier committing to
the queries in advance in order to
ensure zero-knowledge~\cite{GK}.
The commitments in Step~1 are information-theoretic, so
even an arbitrarily powerful prover learns nothing about the
committed values before the commitments are opened;
moreover this implies that
the Step~2 commitments are {\it a fortiori} independent
of the Step~1 commitments.
}
We assume the parameters for
the information-theoretically secret
commitment scheme $K$ are part of the prover's public key.
Commitments in Step~2 are computational (see, {\it e.g.},
\cite{N}), so even an
arbitrarily powerful prover is really committed.
We do not require the prover to prove the same theorem
in all of its concurrent interactions.

%\cd{What happens to the a fortiori stuff when we replace the information-
%theoretic commitment in Step 1 with commitment
%a moderately hard functions? Or $C(r)$?}
\begin{proto}
\label{protII}
{\bf  Generic CoZKP with Timing}\\
\begin{tabbing}
XXX \= xxx\= \kill
\>1. $\VtoP$ Commitment $K(q)$ to $m^2$ queries \\
\>2. $\PtoV$ ${C(Adj(\pi_1(G)), \dots, Adj(\pi_n (G)))}$\\
%to colors in all $m^2$ copies\\
\>3. $\VtoP$ Open queries $q$\\
\>4. $\PtoV$ Reply to all queries\\
\end{tabbing}
\end{proto}

\noindent
{\it Timing Constraints}:
\begin{enumerate}
\item
 $P$ requires the Step~3 message be received within
$\alpha$ (local) time from receipt of the Step~1 message;
\item
 $P$ delays Step~4 until
the entire interaction, from the receipt of the Step~1
message to the sending of the Step~4 message, takes at least $\beta$
local time. See Figure \ref{time_zk}.
\end{enumerate}
  For the proof to be zero-knowledge
we require that the adversary adhere to the
$(\alpha,\beta)$-constraint.
For {\em completeness} we must assume that $V$ can send the required messages
in local time $\alpha$.
%the bounds $\alpha$ and $\beta$ are chosen to satisfy:
%the real time elapsed in all concurrent measurements by (copies of) $P$
%of $\alpha$ is less than every concurrent
%measurement by $P$ of $\beta$.

\begin{figure}[t]
\epsfbox{time_zk.eps}
\caption{The timing requirements for the generic ZK protocol.}
\label{time_zk}
\end{figure}



%\cd{Moni, you removed the definition of $n$.
%Did you mean to replace it with something else?}


The following theorem says that Protocol \ref{protII} is
sound under concurrent executions and is \cek,
{\it i.e.},
that there is a simulator that produces transcripts
$\ve$-indistinguishable from
the true ones. Note that this is a relaxation of the usual notion of
zero-knowledge.
 As we shall see, we remove this relaxation in Protocols \ref{protII'} and
\ref{protII''}.



\begin{theorem}
\label{IIczk}
Protocol \ref{protII} is computational concurrent $\varepsilon$-knowledge and s
ound.
\iffalse
Let the adversary $\A$  controlling the verifiers in protocol II
be any probabilistic Turing Machine whose run time
is bounded by $q(n)$. For any $\varepsilon >0$ there exists a simulator
$\S=\S(\A,\varepsilon)$ whose running time is polynomial in $q(n)$
and $1/\varepsilon$,
such that any polynomial time machine $\B$ that attempts to distinguish
between the transcript  of the verifiers controlled by $\A$ and
the output of $\S$ has advantage at most $\varepsilon$.
\fi
\remove{
Protocol II achieves concurrent zero-knowledge.  That is,
for every $\ve>0$, there exists a simulator running in
expected $\mbox{poly}(n,\ve^{-1})$ time that outputs
a distribution $\ve$-indistinguishable from the
distribution of actual transcripts of $P$ interacting
with $\A$, for every  polynomial time adversary $\A$.
}
%\as{$\ve$ is in the proof so we should put this in the statement
%to remind the reader.  this is a new notion, so it is probably
%worth reminding after the introduction.}
\end{theorem}

\remove{
Let $n$ be the security parameter to the interactive proof system,
as well as a bound on the number of vertices in the graph
whose hamiltonicity is to be proved.
We assume the verifiers are under the control of a polynomial
time bounded adversary $\A$.
(This is consistent with the verifier being a polynomial time
machine in the usual definition of IP.)
For any polynomial $q(n)$, we show how to simulate executions
of the system in which $\A$ is $q(n)$-bounded
so that the simulated executions will be indistinguishable
to any polynomial in $n$ bounded Turing machine from
actual executions of the protocol running with $\A$.
The simulation will require expected polynomial time.
}
%A DIFFERENT APPROACH:
%   We show for any polynomial $q(n)$ how to
%   construct a simulator that fools any
%   $q(n)$-bounded distinguisher. The bound $q(n)$ is not a
%   bound on the running time of the distinguisher as a function
%   of its input size; rather, it is a bound on the running time
%   of the distinguisher as a function of the security parameter $n$
%   of the interactive proof system.
%   A $q(n)$-time bounded distinguisher can only examine a transcript
%   of length $q(n)$; thus, the transcript can
%   contain steps from at most $t = q(n)$ different executions
%   of the protocol.

%%%%%%%%%%PROOF%%%%%%%%%%%%%%%%%

\begin{proof}
%PPP
we must show completeness soundness and $\varepsilon$-knowledge.
Completness follows ``by inspection."
\paragraph{Concurrent $\varepsilon$-Knowledge.}
If $\A$ is $t=q(n)$-bounded, it can initiate at most $q(n)$ concurrent
executions of the protocol.
We first describe a procedure, whose
expected running time is polynomial (in $t=q(n)$ and $1/\ve$),
to simulate up to $t$ concurrent executions of the protocol.
We then argue that simulated transcripts
can be distinguished from actual transcripts
with advantage at most $\ve$.

Consider the first interaction, say with $V_1$.
$V_1$ sends $K(q_1)$ and the simulator replies with $C(r_1)$ where
$r_1$ is random noise.
The simulator tries to extract $q_1$.
It is willing in this process to start (at $\A$'s request)
up to $t-1$ other concurrent interactions.
In each of these concurrent interactions it sends only commitments
to random noise.  Because of the $(\alpha, \beta)$ constraint it
never has to issue the Step~4 reply in these interactions.
If, even after running up to $t-1$ concurrent interactions and
waiting until time $\alpha$ has elapsed, the simulator has not
received $q_1$ from $V_1$, then the simulator rewinds $V_1$ to
just after Step~1 and again tries to extract $q_1$.
%% Going to t^4 :
If after $t^4/\varepsilon$ trials $V_1$ has still not revealed $q_1$, then
$V_1$ is declared {\em conditionally delinquent}.
Intuitively, declaring a verifier {\em conditionally delinquent}
reflects a guess by the simulator that the
probability that the verifier will
open its committed queries (Step~3) in a timely fashion
({\it i.e.}, before $\alpha$ has elapsed on $P$'s clock since
the receipt of the Step~1 message)
given that none of the previously declared conditional delinquents
opens its committed queries in a timely fashion,
%% To \varepsilon/t^3 to do the proof:
is at most $O(\varepsilon / t^3)$.
In this case the simulator is betting that this
verifier will not open its commitments (in a timely fashion)
later in the simulation (thereby causing additional rewinding).
Note that each of the $t^4/\varepsilon$ trials requires $O(t \alpha)$ time,
or, if we view $\alpha$ as a constant, then the bound is $O(t)$.
%%Amit:  By our definitions, shouldn't the above always be O(t)?

In general, after the simulator
%cynthia: builds --> initiates
initiates the first $j-1$ interactions $E_1, E_2,
\ldots, E_{j-1}$, it starts $E_j$ and tries
to extract $q_j$.
We call $E_j$ the {\em current interaction}.
At this point
each of $E_1, \ldots, E_{j-1}$
is classified into one of two
%minor rewording of rest of paragraph
categories, {\em extracted} or {\em conditionally delinquent}.
{\em Extracted} means that
the queries $q_i$ have been extracted and a proper answer
(for Step 2) prepared for $V_i$. This response may or may not
have been sent;
this depends on the scheduling controlled by $\A$; the important property is
that $V_i$ need not be rewound anymore.
{\em Conditionally Delinquent} means that the verifier has been declared
conditionally delinquent because
it did not execute
Step 3 within time $\alpha$ after many trials.
The probability that such a  verifier will open
its committed queries
%% This goes to t^3
in a timely fashion should be smaller than $\ve/4t^3$.

During the current interaction $E_j$ the extraction is done as it
was done for $V_1$, with one change:
When $V_j$ is declared conditionally delinquent or when $q_j$ has been
extracted, $E_j$ is rewound until after the commitment to
$q_j$ (end of Step~1).
The simulation is now ready for a new current execution.
This will be the next execution in which some
copy of $P$ receives the next Step~1 message.
The only difference (with the extraction at $E_1$)  is that now
the simulator may have to handle
conditionally delinquent $V_j$ that wake up.


At any step in the {\em extraction} of $q_j$,
if a conditionally delinquent $V_i$
opens its queries $q_i$ in a timely fashion,
then such a trial, called a {\em failed} trial,
is not counted among the $t^4/\varepsilon$ attempts to
extract $q_j$.
If, however, over $3t^4/\varepsilon$ failed trials occur, then
the entire simulation is aborted.
We will show that the probability of this happening must be small.
All the executions are rewound until the time just before Step~2 of $E_j$,
and a different value for
$r_j$ is chosen and committed to.
The rewinding puts $V_i$ back to ``sleep'' --
in the state in which it has committed to its queries but
not yet opened them.
The values $q_i$ are now known to the simulator but they are ignored.


We treat a waking conditionally delinquent $V_i$
differently if it awakens
(within time $\alpha$)
while we are waiting for a new $V_j$ following
a successful extraction of $q_{j-1}$.
This $V_i$ should be part of the output transcript.
If at such a  step of the simulation (not during extraction),
a conditionally delinquent $V_i$
opens its queries $q_i$ in a timely fashion,
then essentially we abort the execution
(and either restart or output the empty transcript).
If this happens, we say that the {\em output was aborted}.
As we shall see
this does not occur with probability negligibly
more than $\varepsilon/4t^3$.


We now discuss the implication of a waking conditionally delinquent verifier
on the runnng time of the simulator and on the closeness of the
%cynthia: clarified end of sentence
simlated distribution to the distribution on real transcripts.
For any verifier $V_i$, when $V_i$ commits to $q_i$ there
is an {\it a priori} probability, over the choices of
$\A$ and the prover in the remainder of the \tce,
that $V_i$ will eventually open its commitment (Step~3).
We now define a verifier $V_i$ being {\em delinquent}, as opposed to
conditionally delinquent, and show that
verifiers declared ``conditionally delinquent''
are indeed delinquent.

The definition is recursive starting from $V_1$.
Let $p_i$ be the probability that verifier $V_i$ opens its  commitment to
$q_i$  in a timely fashion,
{\em conditioned on the event that no
delinquent verifier $V_{i'}$ ($i' <i$) wakes up
within time $\alpha$ (from the receipt of $V_{i'}$'s Step~1 message)}.
If $p_i \leq \ve/4t^3$ then $V_i$ is delinquent.


We compute the probability that the
simulation will declare $V_i$ conditionally delinquent
if $p_i \ge {\varepsilon \over 4t^3}$.
Recall that $\lim_{x \longrightarrow \infty} (1 - {f(x) \over x})^x
\sim e^{-f(x)}$ when ${(f(x))^2 \over x}$ is $o(1)$.
Assuming that $\A$ cannot distinguish encryptions of random noise
from encryptions of valid permutations of the graph,
if $p_i \ge {\varepsilon  \over 4t^3}$ then the probability that none of the
$t^4/\varepsilon$ attempts to extract $q_i$ will succeed is at most
$(1 - {\varepsilon \over 4t^3})^{t^4/\varepsilon}$.
Setting $x = {t^4/\varepsilon}$
 yields $f(x)=  t/4$,
so the condition on $f(x)$ is satisfied
when $\ve = o(1)$, and we get a probability
of $e^{-t/4}$.
%cynthia: reworded next sentence
Thus, the probability of
classifying $V_i$ as
conditionally delinquent when $V_i$ is in fact {\em not} delinquent,
is at most $e^{-t/4} + \mu$, where
$\mu$ is the probability that $\A$ can break the Step~2 commitment
scheme and distinguish commitments of valid permutations of the graph from
commitments to random noise.

The only computationally detectable
difference between the transcripts produced by the simulator and
the true transcripts arises from the cases that the simulation is aborted.
We will show that this has a sufficiently low probability of occurring:
The probability that the output is aborted is bounded by
$ t \cdot {\varepsilon  \over 4t^3}  \le \ve/4$.
The probability that the simulation is aborted due to failed trials
can be bounded as follows:
Such a failure can happen in any of up to $t$
extractions $E$,
due to any of up to $t$ delinquent verifiers $V$
waking up too often.
This means that $V$ produced at least $3t^3/\ve$ valid Step 3
responses out of at most $4t^4/\ve$ trials.
We claim, however, that if this happens, then with all but
negligible probability, the probability that
$V$ produces a valid Step 3 response conditioned on the initial
transcript used in extraction $E$ is at least $1/2t$.
Indeed, the multiplicative form of Chernoff's bound
states that if this were not the case, the probability
of observing $3t^3/\ve$ valid Step 3 responses by $V$
out of $4t^4/\ve$ trials would be $e^{\Omega(t^3)}$.
Since $V$ is delinquent, however, this implies that the probability of such
a transcript arising is at most $\ve \over 2t^2$.
Summing over all $t^2$ possible extractions and delinquent verifier
pairs, we see that such a failure occurs with probability only
negligibly more than $\ve/2$.  Thus the total probability of a simulation
being aborted is at most negligibily more than $3\ve/4$, and hence
less than $\ve$, as required.

Since the number of trials in any extraction is bounded by
$4t^4/\ve$, it is clear that the entire simulation runs in time
polynomial in $t$ and $1/\ve$.

\paragraph{Soundness.}
Soundness is immediate from the fact that in each $(P,V_i)$ interaction
the prover prepares its
Step~2 commitments with no information whatsoever
about the queries.
\end{proof}

\begin{remark}
In the case of arguments,
the use of timing in Protocol~\ref{protII} can be partially eliminated
by employing moderately
hard functions.
For example, the verifier can use a moderately hard function for
commitment in Step~1
({\it e.g.}, a weakened Fiat-Shamir function).
The protocol is zero-knowledge because
the simulator can compute the query from the (moderately hard to break)
commitment in (large) polynomial time.
For soundness the verifier would require the Step~2 message
to be received within a reasonably short time after the Step~1 message
was sent: the delay should be considerably less than the time required to
break the commitment without the short-cut information.
Also care should be taken to prevent the prover's commitment
from having any
dependency on the commitments of the verifier.
This can be done by making the verifier's commitments
information-theoretic.

Note that as the theory of moderately hard functions
is much less developed than the theory of ``really" hard functions,
such an approach is bound to be less rigorous (although by
making sufficiently strong assumptions it is possible to obtain
rigorous statements).
\end{remark}




\subsection{Concurrent Zero-Knowledge Based on DLP}
\label{DLP}

In this section we modify
Protocol~\ref{protII} to obtain
Protocol~\ref{protII'} below, for which
there exists a simulator that yields a distribution which is identical to
the one produced in real interactions
(no dependency on $\ve$).
The version described below assumes that the prover $P$ is
polynomial-time bounded, and is thus an argument-system
 (rather than a proof system).
%PPP
Protocol~\ref{protII'} requires five rounds of communication,
and requires the Discrete Log Assumption.

%PPP Please read!
The main problem in the simulation of Protocol \ref{protII}
that made it ``only" $\varepsilon$-knoweldge (and not
zero-knowledge) is that there is a need to change $P$'s response
in Step 2 as we extract information from the (perhaps faulty)
verifier. Therefore we design Protocol \ref{protII'} (as well as Protocol
\ref{protII''})
so that the simulation is {\em straight-line},
%think of alternate term?
in the sense that $P$'s original communications are the
ones that are actually produced in the transcript.
There is rewinding, but its only purpose is to extract information
from the verifier, not to alter $P$'s communications.






%Cynthia: dropped the assumption that $p$ and $q$ are chosen by
%a third party
\remove{  %p and q chosen by a third party
We assume that $p$ and $q$ are large primes such that $q|p-1$,
publicly known and chosen neither by the prover
not the verifier, so that it is safe to assume that neither
party can compute discrete logarithms modulo $p$.  We assume
generators $g_1$ and $g_2$
of a $q$-sized subgroup of $\Z_p^*$ are part of $P$'s public key
(or given in a first message from $P$).
%\as{i assume p=2q+1 is the worst case}
% \as{added P's check to the protocol description}

\begin{tabbing}
XXX\= XXXXXXXXX\= XXXXX\= \kill
{\bf Protocol II': Generic Concurrent Perfect ZK with Timing}\\
\>1. $\VtoP$ $K_{g_1,g_2,p}(\vec{q})$
        to all $n$ queries \\
\>\> and $g = g_1^a \bmod p $ and $g' = g_1^{a'} \bmod p$,
        where $a,a' \in_R \Z_q$\\
\>2. $\PtoV$ Information-theoretic commitment using $K_{g_1,g,p}$
         to all $n$ permutations of the graph\\
\>\> and $r \in_R \Z_q$\\
\>3. $\VtoP$ Reveal $\vec{q}$ and $c=a+ra' \bmod q$ \\
\>4. $\PtoV$ Check $g\cdot(g')^r = g_1^c \bmod p$.  Reply to all queries\\
\end{tabbing}
} % end of remove of p and q chosen by a third party


%Cynthia2: removed and replaced with 5-round version
\remove{ %7-round from proceeding
\begin{tabbing}
XXX\= XXX\= XXXXX\= \kill
{\bf Protocol II': Generic Perfect CoZKA with Timing}\\
\>0. $\PtoV$ primes $p_P$,$q_P$, and $g_P,h_P \in \Z_{p_P}^*$, where\\
\>\>    $ord(g_P)=q_P$, and $h_P=g_P^b \bmod p_P$, for $b \in_R \Z_{q_P}$.\\
\>1. $\VtoP$ $K_{g_P,h_P,p}(\vec{q})$ to all $n$ queries, \\
\>\>    primes $p_V, q_V$, and  $g_V, h_V, h_V' \in \Z_{p_V}$,\\
\>\>    where $ord(g_V) = q_V$, $h_V = (g_V)^{a} \bmod p_V$,\\
\>\>    and $h_V' = (g_V)^{a'} \bmod p_V$, for $a,a' \in_R \Z_{q_V}$\\
\>2. $\PtoV$  commitment using $K_{g_V,h_V,p_V}$ to all $n$\\
\>\> graphs, and $K_{g_V,h_V,p_V}(r_P)$, for $r_P \in_R \Z_{q_V}$\\
\>3. $\VtoP$ $r_V \in_R \Z_{q_V}$\\
\>4. $\PtoV$ Open $r_P$.  Set $r := r_V + r_P \bmod q_V$\\
\>5. $\VtoP$ Reveal $\vec{q}$ and $c=ra + a' \bmod q_V$ \\
\>6. $\PtoV$ Check $(h_V)^r\cdot(h_V') = (g_V)^c \bmod p_V$.\\
\>\>      Reply to queries, and reveal $b$.\\
\end{tabbing}
\noindent
{\it Timing Constraints}:
%cynthia: reworded slightly
\begin{enumerate}
\item
 $P$ requires the Step~5 message be received within
$\alpha$ (local) time from receipt of the Step~1 message;
\item
 $P$ delays Step~6 until
the entire interaction, from the receipt of the Step~1
message to the sending of the Step~6 message, takes at least $\beta$
local time.
\end{enumerate}
See Figure \ref{time_per}.
\begin{figure}[t]
\epsfbox{time_per.eps}
\caption{The timing requirements for the Perfect ZK protocol.}
\label{time_per}
\end{figure}
 For the proof to be zero-knowledge
we require that the adversary be constrained by the
$(\alpha,\beta)$-constraint.
For completeness we must assume that $V$ can send the required messages
in local time $\alpha$.
%the bounds $\alpha$ and $\beta$ are chosen to satisfy:
%the real time elapsed in all concurrent measurements by (copies of) $P$
%of $\alpha$ is less than every concurrent
%measurement by $P$ of $\beta$.


In Step 2 the prover commits to the graphs and then
initiates a random string selection subprotocol for choosing the
string $r$ used in Step~5 (explained below).
Steps 3 and~4 are part of the string selection protocol.
We prove the following theorem.

\begin{theorem}
\label{II'zk}
Protocol~\ref{protII'} is sound and is concurrent perfect zero-knowledge.
\end{theorem}


\begin{proof}
We give only a sketch of the proof of soundness; a complete
proof appears in the full version.
The proof of perfect concurrent zero knowledge is given in full.

\paragraph{Soundness.}
%We give a sketch of the proof of soundness for this protocol.  A
%complete proof appears in the full version of the paper.
%
First, observe that if a commitment using $K_{g,h,p}$
is revealed in two different ways, say $g^{r_1}h^{s_1}=g^{r_2}h^{s_2}$,
then the discrete log of $h$ with respect to $g$ can easily
be recovered; in this case it would be $(r_1-r_2)/(s_2-s_1)$.

Formally, to argue soundness, we show
that if any \ppt{} $P^*$ can convince $V$ of a false
statement with probability $\rho$, then there exists a \ppt{}
machine $M$ that can break the DLA with probability $\rho^2-\mu(n)$,
for some negligible function $\mu$.  Here, we give an informal argument
to this effect.
Note that there is no need to argue this in a concurrent setting,
since all parameters to the commitment scheme $K$ are used
only once for each $(P,V)$ interaction.
On input primes $p,q$, generator $g$ of a $q$-order subgroup of
$\Z_p^*$, and $h=g^a$, $M(p,q,g,h)$ proceeds as follows:
$M$ chooses $c,r \in_R \Z_q$, and lets $h'=g^c\cdot h^{-r}$.
$M$ uses $P^*$ as a subroutine, interacting with $P^*$
through Steps 0 and 1, using $p_V=p$, $q_V=q$, $h_V=h$, and
$h'_V=h'$.  $M$ proceeds through Steps 2-4 with $P^*$,
and receives $r_P$ in $P^*$'s Step 4 message.
$M$ then rewinds $P^*$ to Step 3, and sends $r_V=r-r_P$.
If $P^*$ then in Step 4 opens its commitment to something
other than $r_P$, then $M$ can immediately extract $a$
and terminate.  If $P^*$'s Step 4 response is the same as
before, then $M$ proceeds to Step 5, revealing its random
queries and sending the value of $c$ that it had chosen
in the beginning.  Note that $P^*$'s Step 6 check will pass
by construction of $h'$, and $P^*$ will reply correctly to all queries,
and supply $b$ such that $g_P^b=h_P$.  By assumption, we make
it this far with probability roughly $\rho$.  Now, $M$ rewinds
$P^*$ to Step 5, and using knowledge of $b$, decommits to
a new randomly chosen query vector, and gives the same $c$
as before.  Again by assumption, $P^*$ again gives a correct
Step 6 response with probability roughly $\rho$.  Now,
with all but negligible probability, there is some query bit
position which is different in the second query vector than it
was in the first.  In order for $P^*$ to have answered correctly both
times on this bit, it must have revealed some edge differently
in response to the first query than in the second.  From this,
$M$ can recover $a$, and terminate.  Thus, we have shown that
with probability roughy $\rho^2$, $M$ can break the DLA.

The proof of soundness above essentially relies on the fact that
Steps 1-5 of Protocol \ref{protII'} are zero-knowledge for the Verifier
with respect to $a$.  The simulator is essentially contained in
the machine $M$ described above.

\paragraph{Concurrent Perfect Zero-Knowledge.}
} %end of remove of 7-round from proceeding


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Cynthia2: Added 5-round Protocol II' and its proof here.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent
{\bf Protocol \ref{protII'}}  %A 5-round protocol.
In the sequel, the primes $p_P$ and $p_V$ are $k$ bits long
and hence are in the interval $[2^{k-1}, 2^k-1]$.
The strong-receiver commitment protocol $K$ used in the protocol
has been described in the Introduction.
%cynthia2: this can be relaxed if it is a problem.
%The restriction makes one of the arguments simpler.  Choosing a random $k$-bit
%number instead (permitting a leading 0) would still have the
%effect that with overwhelming probability $p_P$ and $p_V$ are
%polynomially related, which is all that the proof really needs.

\begin{proto}
\label{protII'}
{\bf Concurrent (Perfect) ZK with Timing}\\
\begin{enumerate}
\item
$\PtoV$  Choose random primes $p_P,q_P$, and $g_P$ of order $q_P$ in
            $\Z_{p_P}^*$.
            Choose random $b \in \Z_{q_P}$.
            Set $K_P = (p_P,g_P,g_P^b \bmod p_P)$.
            Send $K_P, K_P(r_P)$ for $r_P \in_R \Z_{q_P}$.
\item
$\VtoP$  Choose random primes $p_V,q_V$, and $g_V$ of order $q_V$ in
            $\Z_{p_V}^*$.
            Choose random $g_V$ of order $q_V$ in $\Z_{p_V}^*$.
            Choose random $a,a' \in \Z_{q_V}$.
            Set $h_V = g_V^a \bmod p_V$, $h'_V = g_V^{a'} \bmod p_V$.
            Set $K_V = (p_V,g_V,h_V)$.
            Send $K_V$, $h'_V$, $K_P(r_V)$ where $r_V \in_R \Z_{q_V}$.
\item
$\PtoV$  $K_V(graphs)$; open $r_P$
\item
$\VtoP$  Open $r_V$; Also, set $r := r_V + r_P \bmod q_V$ and
            send $(ra + a') \bmod q_V$ and a vector $\vec{q}$ of queries.
\item
$\PtoV$  Check $(h_V)^r\cdot(h_V') = (g_V)^c \bmod p$.
            Reply to queries and send $b$.
\end{enumerate}
\end{proto}


\noindent
{\it Timing Constraints:}
\begin{enumerate}
\item
 $P$ requires the Step 4 message be received within $\alpha$
local time from receipt of the Step~1 message;
\item
 $P$ delays the Step~5 message until at least $\beta$ local
time has elapsed since the receipt of the verifier's Step~4 message.
\end{enumerate}
See Figure \ref{time_per}.
\begin{figure}[t]
\epsfbox{time_per.eps}
\caption{The timing requirements for the (Perfect) ZK protocol.}
\label{time_per}
\end{figure}
 For the proof to be zero-knowledge
we require that the adversary be constrained by the
$(\alpha,\beta)$-constraint.


\begin{theorem}
\label{theorem: II'}
Protocol \ref{protII'} is sound and (perfect) concurrent zero knowledge.
\end{theorem}

\begin{proof}
As usual, completeness follows by inspection.
\paragraph{Ordinary Zero Knowledge.}
Before proving concurrent zero knowledge we
outline the simulation technique for proving ordinary zero knowledge
in the standard model, without timing.
The (traditional) simulation works as follows.

\noindent
Step 1.  The simulator executes Step~1 of the protocol.  There is no
difference in the message composed by the simulator at this step and the
message composed by the real prover.
Note that the simulator knows the trapdoor $b$ for the
scheme $K_P$ that it has chosen.

\noindent
Step 2. The verifier replies with a scheme $K_V$, having trapdoor $a$
(which may or may not be known to the verifier), and $h_V'$.
Let $p_2$ be the conditional
probability with which the verifier responds to the
Step~1 message in the simulation.  Clearly, $p_2$ is also exactly the
probability with which the verifier responds in real executions.
If the verifier fails to respond then the simulator outputs the
simulated Step~1 message and halts.

\noindent
Step 3. The simulator commits to a random string using $K_V$ and opens $r_P$.
Again, the simulator's message at this step is distributed exactly
as the prover's Step~3 message.
Indeed, the entire simulated transcript up to this point
is distributed exactly as a real 3-step transcript is distributed.
Let $T$ denote the simulated transcript of the first 3 steps.

\noindent
Step 4. The verifier opens $r_V$ and sends $(r_P a + a') \bmod q_V$
with exactly the same conditional
probability that it does in real executions (the conditioning is on $T$).
A {\em valid} Step~4 message is a syntactically correct message
that passes the test in Step~5.
If the verifier sends no message or sends an invalid message,
then output the transcript (including the invalid Step~4 message,
if any) and halt.

\noindent
{\bf Extraction:}
Rewind $V^*$ to just after Step~2 and interleave the following
two procedures until the first one halts.
\begin{enumerate}
\item
Repeat until the verifier replies with a
{\em different} valid Step~4 message:
\begin{list}{}
\item
Open $K_P(r_P)$ to any $r'_P \in_R Z_{q_P} \setminus \{r_P\}$
using trapdoor $b$ chosen in the simulation of Step~1.
Note that even though $r_P$ and $r'_P$ are
drawn from $Z_{q_P}$, rather than from $Z_{q_V}$, it is very
likely that $r_P a + a' \not= r'_P a + a' \bmod q_V$.
\end{list}
Solve  $(r'_Pa + a') \bmod q_V$ and $(r_Pa + a') \bmod q_V$
for $a \bmod q_V$.
\item
Find $a$ by brute force.
\end{enumerate}

\noindent
Step 5: open replies to Step 4 queries at will using trapdoor $a$ for $K_V$.

This completes the description of the simulator.
We now compute the running time.
Let $\eta$ be the probability  conditioned on the transcript
through Step~2, that the verifier
will send a valid Step~4 message in an execution of the protocol,
that is, that the Extraction procedure is executed.
Let $\xi$ be the probability that the verifier responds with a
valid Step~4 message during extraction given $r'_P \not\equiv r_P \bmod q_V$.
Let $r_0 = r_P \bmod q_V$.
\begin{enumerate}
\item Case $p_P \le q_V$;
This case cannot occur because $p_V < 2p_P$ and $q_V | (p_V - 1)$.
Together with the fact that $p_V$ and $q_V$ are both prime
(so $q_V \not= p_V -1$),
the second condition implies that $q_V < \frac{p_V}{2}$.
Together with the first condition this yields $q_V < p_P$.
\remove{ %wrong calculation
 then the probability
of choosing an $r \equiv r_0 \bmod q_V$ is at most $\frac{1}{p_P}$.
We consider two subcases:
\begin{itemize}
\item{$\eta > \frac{2}{p_V}$}:
In this case, $\frac{\eta}{2} > \frac{1}{p_V}$ and so
$\eta - \frac{1}{p_V} > \frac{\eta}{2}$.
Thus, $\xi \ge \eta - \frac{1}{p_V} \ge \frac{\eta}{2}$, so
the expected number of trials in the extraction procedure
is at most $\frac{2}{\eta}$, yielding an overall expected
running time of $\eta \cdot \frac{2}{\eta} \cdot 2c$ steps.
Here $c = O(1)$ is the number of steps to carry out a trial.
The factor of 2 comes from the interleaving with the brute force
search for~$a$.

\item{$\eta \le \frac{2}{p_V}$}:
In this case the brute force search succeeds in some $c'p_V$ steps,
where $c'$ is the $O(1)$ number of steps needed to test an
individual guess of the trapdoor.
Finally, since $p_V \le 2p_P$, we have that the total expected
number of steps in this case is at most
$\eta \cdot 4c'p_V \le 8 c' p_P$.
\end{itemize}
}
\item
Since $p_P > q_V$, the probability
of choosing an $r \equiv r_0 \bmod q_V$ is at most $\frac{2}{q_V}$.
We consider two subcases:
\begin{itemize}
\item{$\eta >\frac{3}{q_V}$}:
In this case $\eta - \frac{2}{q_V} > \frac{\eta}{3}$
and so $\xi \ge \frac{\eta}{3}$ and the expected number of trials
during extraction is at most $\frac{3}{\eta}$.
Thus the overall expected number of trials is at most
$\eta \frac{3}{\eta} = 3$, leading to an
expected $O(1)$ steps overall.
\item{$\eta \le \frac{3}{q_V}$}:
In this case the brute force search succeeds in $O(q_V)$
steps, for a total of an expected $O(\eta q_V) = O(1)$ steps.
\end{itemize}
\end{enumerate}


\paragraph{Concurrent Zero Knowledge}
The proof of concurrent zero knowledge is almost exactly the same
as the proof for ordinary zero knowledge.
We redefine a {\em valid} Step~4 message to specify that the message must
also satisfy the timing constraint.
For a verifier $V_i$,
we redefine $\eta$ to be the probability, conditioned on the transcript
$T$ through the Step~2 message of $V_i$, that the extraction procedure
will be executed.
This transcript $T$ involves messages between
the prover and other verifiers , and the probability is over
all possible extensions of $T$.
Finally, we note that the timing constraints ensure that
during the interaction with any verifier $V_i$
the prover never needs to provide a Step~5 message to any
$V_j$ that sent its Step~4 message after $V_i$ did.

Thus, the simulation is constructed message by message.
If in some $(P,V_i)$ interaction the adversary sends a valid
Step~4 message for $V_i$, then the extraction procedure is
executed for $V_i$'s trapdoor information $a_i$.
The timing constraints ensure that the extraction procedure can be
carried out.
This completes the proof of concurrent zero knowledge.

\paragraph{Soundness.}
There is no
need to argue in the concurrent setting, since the parameters to $K$
are used only once.
The proof relies on the fact that, if $P^*$ convinces $V$ of
a false statement with non-negligible probability, then by exploring
the answers to two different query vectors (Steps 4 and~5),
it is possible to obtain two different openings of a ``committed'' value.

Assume for the sake of contradiction
that some probabilistic polynomial time bounded
cheating $P^*$ can convince $V$ of a false theorem
with non-negligible probability $\rho$.
We argue that there exists a probabilistic polynomial time
bounded $M$ that, by interacting with $P^*$,
can break the DLA with probability $\Omega(\rho^4)$, which
is also non-negligible.

On input $p,q,g,h=g^a$, where $g$ generates an order $q$ subgroup of
$\Z_p^*$, $M$ interacts with $P^*$ as follows.

\noindent
1. $P^*$ sends $K_P$, $K_P(r_P)$ to $M$.

\noindent
2. $M$ sets $p_V = p$, $q_V = q$, $g_V = g$.
$M$ chooses $c,r \in_R \Z_{q_V}$.
$M$ sends $K_V = (p,g_V,h)$, $h'_V = g_V^c h^{-r}$, and
$K_P(r_V)$ to $P^*$, where $r_V \in_R \Z_{q_V}$.


\noindent
3. $P^*$ sends $K_V(graphs)$ and opens $r_P$.
At this point $M$ rewinds $P^*$ to just after Step 1,
sets $r_V = r - r_P \bmod q_V$, and $M$ re-sends its original
Step~2 message, modified so that the commitment
$K_P(r_V)$ is to the new value of $r_V$.

\noindent
2'. $M$ sends $K_V = (p,g_V,h)$, $h' = g_V^c h^{-r}$, and $K_P(r_V$ to $P^*$),
    where $r_V = r - r_P \bmod q_V$.

Assuming that $P^*$ responds to the Step~2' message,
one of two things can happen:
either $P^*$ changes the way it opens its Step~1 commitment to $r_P$ or not.
We examine the two cases separately.

\paragraph{Case $P^*$ opens $r'_P \not= r_P$.}
In this case $P^*$'s message is:

\noindent
3'. $P^*$ sends $K_V(graphs')$ and opens $r'_P \not= r_P$.
In this case $M$ has extracted $b$ (from 3' and 3).

\noindent
4. Using the trapdoor $b$, $M$ opens $r_V$ to $r - r'_P \bmod q_V$.
$M$ also chooses a random query vector $\vec{q}\in_R\{0,1\}^n$ and
gives to $P^*$ the queries $\vec{q}$.

\noindent
$P^*$'s check succeeds by definition of $h'_V$.
$P^*$ replies to the queries and sends $b$ (which is already known).
$M$ then rewinds $P^*$ to just before Step 4.

\noindent
4'. Once again, using the trapdoor $b$,
$M$ opens $r_V$ to $r - r'_P \bmod q_V$.
$M$ choose a random $\vec{q'} \in_R\{0,1\}^n$ and
gives to $P^*$ the queries $\vec{q'}$.
Note that with overwhelming probability $q' \not= q$.

\noindent
5. Once again, $P^*$'s check succeeds by definition of $h'_V$.
$P^*$ replies to the queries and sends $b$.
$M$ now has the reply to two different queries and hence the opening
of some commitment under $K_V$ (made in Step 3') to two different values.
 From this $M$ can extract $a$.
This completes the case $P^*$ opens $r'_P \not= r_P$ in Step 3'.

\paragraph{Case $P^*$ does not change $r_P$.}
Recall that in Step 2', $M$ committed using $K_V$ to $r_V = r- r_P \bmod q_V$.

\noindent
3'. $P^*$ sends $K_V(graphs')$ and opens $r_P$.

\noindent
4. $M$ opens $r_V$ and sends a query vector $\vec{q} \in_R \{0,1\}^r$.

\noindent
5. $P^*$'s check succeeds by definition of $h'_V$.
   $P^*$ replies to the queries and sends $b$.
$M$ rewinds $P^*$ to just before Step 4.

\noindent
4'. $M$ opens $r_v$ to $r - r'_P \bmod q_V$
(it can do this because it has $b$).
$M$ then chooses a new $\vec{q'} \in_R \{0,1\}^n$ and sends
$\vec{q'}$ to $P^*$.

\noindent
5. $P^*$'s check succeeds by definition of $h'_V$.
   $P^*$ replies to the queries and sends $b$.
As in the previous case,
$M$ now has the reply to two different queries and hence the opening
of some commitment under $K_V$ (made in Step 3') to two different values.
 From this $M$ can extract $a$.


We now analyze the probability of success of the extraction procedure.
The $(P^*,M)$ interaction can be viewed as a tree with
probability $\rho$ of success (``success'' is
when $P^*$ answers all its questions correctly).
After $P^*$ sends its Step~1 message, with probability
at least $1/2$ (over $P^*$'s choices in the the first message)
the resulting node $v_1$ has probability at least $\rho/2$ of
success.
Assume we are in this ``good'' case.
After $M$ sends the Step~2 message, with probability at most $1 - \rho/2$
there is immediate failure ($P^*$ refuses to respond correctly), so with
probability at least $\rho/2$, $M$ will
choose a Step~2 message to which $P^*$ will respond correctly.
Thus, the probability that $M$ chooses two Step~2 message
(once before and once after rewinding) to which $P^*$ responds correctly
is at least $\rho^2/4$, conditioned on being in a probability $\rho/2$
node after Step~1.

Assume $P^*$ has answered correctly in both Step~3 and Step~3'
and that the probability of success at $v_1$ is at least $\rho/2$.
With probability at least $1/2$ the node $v_3$ reached after
$P^*$ sends its Step~3 message has probability at least $\rho/4$
of success.
Arguing as above, the probability that $M$ chooses two Step~4 message
to which $P^*$ responds correctly is at least $\rho^2/16$.
Thus, the overall probability of extracting $a$ is
$$\frac{1}{2} \frac{\rho^2}{4} \frac{1}{2} \frac{\rho^2}{16} = \Omega(\rho^4)$$
minus a negligible probability that $\vec{q} = \vec{q'}$ during the
$(P^*, M)$ interaction.
\end{proof}




%PPP moved the remarked from here

\subsection{Concurrent Zero-Knowledge Under General Assumptions}
\label{general}

%cynthia Added 12-round protocol here
In this section we present protocols that rely on the existence
of one-way functions.
The first protocol in this section requires twelve rounds of communication.
As written, this protocol requires that the prover be restricted
to probabilistic polynomial time.
We first recall the strong-sender commitment scheme of Naor~\cite{N},
modified slightly so that all strings are of length $5n$ instead of
length $3n$.
Thus, the protocol requires a pseudo-random generator $G$ that
stretches $n$-bit seeds into pseudo-random strings of length $5n$.
\begin{itemize}
\item
The \commit{} protocol:
\begin{enumerate}
\item
The receiver chooses a random $5n$-bit {\em pad} $r$ and sends $r$ to
the sender.
\item
To commit to a bit $B$,
the sender chooses an $n$-bit seed $s$,
and sends to the receiver
the $5n$-bit long string $d = d_1 d_2 \dots d_{5n}$,
where
\[
d_i =
        \left\{         \begin{array}{ll}
                        [G(s)]_i & \mbox{if $r_i = 0$}\\
                        \lbrack G(s)\rbrack_i \oplus B & \mbox{if $r_i=1$}
                        \end{array}
        \right.
\]
\end{enumerate}
\item
The \reveal{} protocol:
The sender sends $s$ and $B$; the receiver
computes $G(s)$ and verifies that
$d$ is consistent with these values.
\end{itemize}

A pair of strings $s_1$ and $s_2$ {\em fools} a $5n$-bit string $r$
if
\begin{enumerate}
\item
For all $i$ such that $r_i = 0:~[G(s_1)]_i = [G(s_2)]_i$.
\item
For all $i$ such that $r_i = 1:~[G(s_1)]_i \not= [G(s_2)]_i$.
\end{enumerate}
It follows immediately from the
definition that the pair $(s_1,s_2)$ fools $r$ if and only if
$r = G(s_1) \oplus G(s_2)$.
Thus, each pair of seeds can fool at most one pad $r$.


\begin{claim}(\cite{N})
\label{commitment claim}
The probability, over choice of $r$, that there exists a pair of
seeds $s_1$ and $s_2$ that fools $r$ is at most $2^{-3n}$.
\end{claim}



Protocol
\ref{protII''} is based on several techniques:
\begin{itemize}
\item
{\bf Equivocal Commitment}.
This is
a property of the strong-sender commitment scheme of \cite{N}
first suggested in
\cite{DIO}:
If the simulator has control over the pad in the \commit{} protocol,
 then the ``commitment'' can be opened at the \reveal{} stage
 either as a zero or as a one.
Using this, the simulated prover can
``commit"  to an adjacency matrix
and then can open the commitments as needed to carry out the simulation.
The protocol is designed so that there exists a simulator
that controls the pad.
When we write $C_r(x)$ we mean commitment with pad $r$ to value $x$.
The pad used in committing the graphs
will be the exclusive-or of $r_1$,
chosen by $V$, and $r_2$, chosen by $P$.


\item
%* Another technique is the one
%we used in the OLD protocol III, which we can actually
%make efficient - without NIZK proofs of  consistency.
{\bf Extraction of $r_1$.}
Suppose Alice wants to commit to $r_1$ of length $\ell$.
She chooses a random $p_1$ of length $\ell$, sets $p_2 = r_1 \oplus p_1$,
and commits to $p_1$ and to $p_2$.
Bob asks to see either $p_1$ or $p_2$.
In the context of Protocol \ref{protII''}, Alice is the {\em verifier}
and Bob is the {\em simulator}.
If the simulator obtains both $p_1$ and $p_2$,
then it can extract $r_1$.
The simulator will use its knowledge of $r_1$ to control the
outcome of the pad, as discussed above.

To assure extraction with very high probability
this must be be
repeated many times in parallel with different pairs
$p^j_1, p^j_2$ in each execution (where always $p^j_1 \oplus p^j_2 = r_1$).
Here, it is possible to save on communication by employing good
{\em erasure-correcting} codes.
Alice should encode the string $r_1$ so that it is  sufficient  to
obtain,  say, $1/4$th of the indices in order to reconstruct $r_1$
(we don't care about errors, since they will result in  aborting  the
protocol  anyway). Now each bit is split at random  into two bits
(so that the Xor of the two bits is the  original)  and  the  $j$th
commitment  is  to  those bits. The prover gets to chose which of
the two he gets.  With high probability, when the  extraction  is
done  two different execution will be different in at least $1/4$th
of the places (even for the closest pair) and  using the  erasure
correction procedure $r_1$ can be reconstructed.

\item
We add another level of equivocal commitments to force soundness.
\end{itemize}

In the sequel,
$r_1$ and $r_2$ are strings of length $5nk$, where $k$ is the total
number of bits committed to in Step~\ref{graph commitments}, and
$d_1$, $d_2$, $e_1$, and $e_2$ are each strings of length $25n^2k$.
Each $d_i$ and $e_i$ is conceptually broken into a sequence
$5nk$ blocks of length $5n$.
In Step~\ref{commit to d_1}, each of the
$50n^2k$ bit commitments is performed using the same pad $r$.
However, in Step~\ref{commit to p}, the commitment to the $i$th
bit of $p_1$ (respectively, $p_2$) is performed using the
$i$th consecutive block of $5n$ bits of $d_1 \oplus d_2$
(respectively $e_1 \oplus e_2$).
Similarly,
in Step~\ref{graph commitments} the commitment to the
$i$th bit is done using the $i$th consecutive block of $5n$
bits of $r_1 \oplus r_2$.

For simplicity we describe the protocol with a single $p$.

\begin{proto}
\label{protII''}
{\bf Concurrent Perfect ZK  - General Assumptions}\\
\begin{enumerate}
\item
\label{initial pad}
$\VtoP$ $r \in_R \zo^{5n}$

\item
\label{commit to d_1}
$\PtoV$ $C_r(d_1)$ and $C_r(e_1)$ for $d_1,e_1 \in_R \zo^{25n^2k}$

\item
$\VtoP$ $d_2,e_2 \in_R \zo^{25n^2 k}$

\item
\label{send d_1}
$\PtoV$ $d_1,e_1$.  These are {\em not} openings, just the sending of strings.

\item
\label{commit to p}
$\VtoP$  Choose $r_1,p_1 \in_R \zo^{5nk}$.  Set $p_2 = r_1 \oplus p_1$.
Send commitments
$C_{d_1 \oplus d_2}(p_1)$ and $C_{e_1 \oplus e_2}(p_2)$.
%(the  pad  for this commitment is  d_1\oplus d_2)

\item
$\PtoV$ $i \in_R {1,2}$

\item
\label{open p(i)}
$\VtoP$ open $p_i$

\item
\label{choose r_2}
$\PtoV$ $r_2$

\item
\label{open r_1}
$\VtoP$ Open the other commitment $p_{3-i}$; $r_1 =_{\rm def} p_1 \oplus p_2$.

\item
\label{graph commitments}
$\PtoV$ $C_{r_1 \oplus r_2} (Graphs)$

\item
$\VtoP$ the queries $\vec{q}$

\item
\label{replies}
$\PtoV$ answer the queries and give all the information
to ``open'' $d_1$ and $e_1$, whose values were sent in Step~\ref{send d_1}.
$V$ should verify the consistency with Step 4.
\end{enumerate}

\noindent
{\it Timing Constraints}:
\begin{enumerate}
\item
The Step~\ref{open p(i)} message must be received within time $\alpha$
of receipt of the Step~{commit to p} message.
\item
The Prover waits until at least time $\beta$ has elapsed since
receipt of the Step~\ref{open p(i)} message before sending the
Step~\ref{replies} message.
\end{enumerate}
\end{proto}

\begin{theorem}
Protocol \ref{protII''} is sound and concurrent zero knowledge.
\end{theorem}

\begin{proof}
We argue ordinary (sequential) zero knowledge (without timing constraints).
The extension to concurrent zero knowledge (with timing constraints)
is straightforward using the technique from the proof of Protocol \ref{protII'}
.

The intuition is that the simulator will extract both
$p_1$ and $p_2$ in order to compute $r_1$.
It will then choose $r_2$ so that the Step~\ref{graph commitments}
commitment is equivocal.
This will permit the simulator to ``answer'' arbitrary queries.

There is one subtlety: we must ensure that a cheating verifier $V^*$
cannot choose $d_2$ and $e_2$ in some bizarre way as a function of the
commitments to $d_1$ and $e_1$,
so that the commitments with pad $d_1 \oplus d_2$ or $e_1 \oplus e_2$
are equivocal.  If $V^*$ could do this, then the simulation might
fail, since, for example, the value for $p_{3-i}$ obtained
in the extraction may differ from the one obtained in Step~\ref{open r_1}
in the simulation.
This would result in the ``wrong'' value of $r_1$ being computed in
from the extraction, and a consequent ``wrong'' value of $r_2$
being selected in Step~\ref{choose r_2}.  In this case the
simulator's commitments
in Step~\ref{graph commitments} may not be equivocal, and the simulation
would fail.

It is to avoid this problem that the actual {\em opening} of $d_1$ and $e_1$
(as opposed to just the sending of the strings) is delayed until
Step~\ref{replies}, as we next explain.
We will use $V^*$'s (presumed) ability to equivocate to violate
the semantic security of the commitment in Step~\ref{commit to d_1}.

In the sequel, we focus on $d_1$ and $d_2$.  An identical argument
holds for $e_1$ and $e_2$.
The argument will show that $V^*$ cannot equivocate on even one
bit of $p_1$ (the analogous argument for the $e$'s shows
that $V^*$ cannot equivocate on any bit of $p_2$).
Recall that $d_1$ and $d_2$ are strings of length $25n^2k$, and that
we use the $i$th consecutive block of $5n$ bits to commit
to the $i$th bit of $p_1$.
The next discussion applies to any block of length $5n$.
To simplify terminology, we just let
$d_1$, $d_2$, and $d_1'$ be 5n-bit long strings.
The discussion applies to each block of this length.

Let $d_1, d_1' \in_R \zo^{5n}$.
We argue that with overwhelming probability over choice of
$d_1$ and $d_1'$, there does not
exist $d_2$ such that both
\begin{itemize}
\item
$d_1 \oplus d_2$ is ``bad'':
$\exists s_1, s_2 \in \zo^n$ such that
        $G(s_1) \oplus G(s_2) = d_1 \oplus d_2$;
\item
$d_1' \oplus d_2$ is ``bad'':
$\exists s_1', s_2' \in \zo^n$ such that
        $G(s_1') \oplus G(s_2') = d_1' \oplus d_2$.
\end{itemize}
Suppose for the sake of contradiction that there exists $d_2$ satisfying
the conditions above.
Then
\begin{eqnarray}
g(s_1) \oplus g(s_2) \oplus g(s_1') \oplus g(s_2') = d_1' \oplus d_1
\label{sum}
\end{eqnarray}
There are only $2^{4n}$  choices of the four seeds,
and $2^{5n}$ choices for
$d =_{\rm def} d_1 \oplus d_1'$, so
with overwhelming probability over choice of $d$
there do not exist seeds $s_1,s_2,s_1',s_2'$ satisfying Equation~\ref{sum}.

Let $S$ be a sender and $R$ a receiver.
$R$ will use $V^*$ to break the commitment scheme.
First, $R$ runs $V^*$ and obtains its Step~\ref{initial pad} message $r$.
$R$ sends $r$ to $S$.
$S$ chooses one of the two messages and commits to it.
Without loss of generality, we will {\em call} the one committed to $d_1$,
and the other one $d_1'$.

$R$ will now interact with $V^*$, simulating $P$ and running the
simulation through Step~\ref{open r_1}.
The presumed ability of $V^*$ to cheat on opening its commitments is something
that the simulator can test for (opening something differently during
extraction than during the main branch of the simulation).
Thus $V^*$ can be used as a distinguisher: its ability
to equivocate when given $d_1$ in Step~\ref{send d_1}
will differ from its ability to equivocate when
given $d_1'$ in Step~\ref{send d_1}.
This violates the semantic security of the commitment scheme.

Thus, using standard techniques
the simulator can indeed extract $r_1$ from $V^*$
in expected polynomial time, assuming that $V^*$ replies with its
Step~\ref{open p(i)} message with polynomial probability.
As usual, if $V^*$ does not send the
Step~\ref{open p(i)} in the main branch of
the simulation, then the simulation halts.

The only difference between the simulated conversations and the
actual conversations with the honest
prover $P$ is that $r_1 \oplus r_2$ is truly random in the real
conversations while it is pseudo-random in the simulation.


\medskip

Soundness is straightforward if the prover cannot equivocate in
Step~\ref{graph commitments}.
This is immediate if $r_1 \oplus r_2$ is truly random.
The problem here is analogous to the problem solved in proving
zero knowledge: we must show that a cheating $P^*$ cannot
choose $r_2$ so that $r_1 \oplus r_2$ permits equivocation.

Suppose for the sake of contradiction that $P^*$ can indeed
prove false theorems with non-negligible probability; colloquially,
$P^*$ can cheat.
The intuition for our proof strategy is to
interact with $P^*$, including rewinding,
to extract $d_1$ and $e_1$, and then to choose $d_2$
and $e_2$ so that $d_1 \oplus d_2$ and $e_1 \oplus e_2$
permit $V$ to equivocate in Steps \ref{open p(i)} and~\ref{open r_1}.
Once $V$ can equivocate, it can force $r_1$ to be independent
of $r_2$ by opening $p_{3-i}$ (and hence $r_1$)
at random in Step~\ref{open r_1}.
$P^*$ cannot equivocate in this case and so it will ``get stuck''
when trying to prove a false theorem (or a theorem to which it
has no witness).
(It is because we wish to be able to equivocate, so as to trap $P^*$
as just described,
that each bit of $p_1$ and $p_2$ is committed to independently,
since otherwise the equivocation could be detected.)
We will show that if $P^*$ can cheat in real executions
%PPP added be
then it can be used to distinguish random pads $d_1 \oplus d_2$ and
$e_1 \oplus e_2$ from pseudo-random pads.

%PPP Changed to property since it is rather informal
%
We use the following well known property (see, for example,~\cite{GGM}).
of pseudo-random sequences.
{\em
The ability to efficiently distinguish a polynomial-sized
collection of
%polynomial-sized sequences
of pseudo-random strings from a polynomial-sized collection of
of truly random strings can be used to construct an efficient
distinguisher for single pseudo-random strings from single
truly random strings.
}
Note that in normal executions, assuming $V$ does not cheat,
$d_1 \oplus d_2$ and $e_1 \oplus e_2$ are both sequences of
$5n$-bit long truly random strings.


Consider three scenarios.
\begin{list}{}
\item{A.}
Real $(P^*,V)$ executions:
the pads $d_1 \oplus d_2$ and $e_1 \oplus e_2$ are
truly random; $V$ opens $p_1$ and $p_2$ to the values chosen
in Step~\ref{commit to p}.
\item
{B.}
Executions arranged by rewinding $P^*$, so that
the pads $d_1 \oplus d_2$ and $e_1 \oplus e_2$ are pseudo-random,
with $d_2, e_2$ chosen to permit arbitrary equivocating,
but the values $p_1$ and $p_2$ that are revealed are the
ones chosen in Step~\ref{commit to p}.
\item
{C.}
The ``trapping'' executions, arranged by rewinding $P^*$
so that
the pads $d_1 \oplus d_2$ and $e_1 \oplus e_2$ are pseudo-random,
the value opened in Step~\ref{open p(i)} is the one chosen in
Step~\ref{commit to p}, but the value opened in Step~\ref{open r_1}
is chosen at random on the fly.
\end{list}

The only difference between Scenarios A and B is that
the pads are truly random in the former and pseudo-random in the
latter.  Thus, any difference in ability of $P^*$ to cheat in these
two scenarios can be used to distinguish sequences of truly random
strings from sequences of pseudo-random strings.

The only difference between Scenarios B and C is that in the
former the ``real'' value chosen in Step~\ref{commit to p},
before $P^*$ chose $r_2$,
is the one revealed in Step~\ref{open r_1}, while in the latter
the value revealed is randomly chosen {\em after} $r_2$ is fixed.
Note that the two scenarios are {\em identical} before $r_2$
is chosen, so $r_2$ is chosen in exactly the same way in both
scenarios (however $P^*$ wants to choose it).
Thus, $r_1 \oplus r_2$ is distributed identically in these two
scenarios.  Since in Scenario~C it is uniform, $P^*$ cannot cheat
in Scenario~C because with overwhelming probability
$r_1 \oplus r_2$ does not permit equivocation;
thus equivocation by $P^*$ is impossible in Scenario~B and
$P^*$ cannot cheat in this scenario.
By the indistinguishability of truly random and pseudo-random pads,
$P^*$ must not be able to cheat in Scenario~A either.
\end{proof}

%%PPP No need for that
\remove{

We remark that
it is possible to turn Protocol \ref{protII''} into a 10-round protocol using N
IZKs:
use $r_1 \oplus r_2$ as the common string in a NIZK system.
At Step~\ref{graph commitments} $P$ sends the NIZK proof.
}



\section{Protocols for Concurrent Deniable Authentication}
\label{examples}

%PPP rewrote
The problem of achieving concurrent \pka{} is
solved by the general techniques of the Section \ref{czkproofs}.
These techniques can be adapted to give deniable
authentication protocols.
However,
a further exploration of the problem yields
several  ``special purpose'' solutions that can be
implemented at a low computational cost.
We describe two such protocols in this Section.
The timing constraints in one of them is different
than in previous protocols, since {\em both}
parties are involved in the enforcement.

\subsection{Timed Proof of Knowledge}

In Protocol~\ref{protIII}
 below we modify Protocol~\ref{protI} by adding timing constraints.
These are essentially the same constraints that were used for
the generic protocol (Protocol \ref{protII}), the goal being to ensure
%Timing constraints: $P$ requires
that in all executions the total
time exceeds the maximum time of the
first 3 steps in any concurrent execution.

The prover  $P$ has a public-key
$E$, chosen from  a non-malleable
cryptosystem secure against chosen ciphertext attacks
in the post-processing mode.
$P$  wishes to authenticate a message $m$ to the Verifier $V$.
\begin{proto}
\label{protIII}
%PPP Changed label
{\bf  Concurrent \PKA}\\
\begin{tabbing}
XXX \= xxx\= \kill
\> 1. $\VtoP$   Choose $r \in_R \{0,1\}^n$ and send $E(m \circ r)$\\
\> 2. $\PtoV$ $E(r)$\\
\> 3. $\VtoP$ $s,r$, where $s$ is the string of random \\
\>\> bits used for the encryption in Step~1\\
\> 4. $\PtoV$ open $E(r)$
\end{tabbing}
\end{proto}

%I changed the reference to the figures.

\noindent
{\it Timing Constraints}:
\begin{enumerate}
\item
 $P$ requires the Step~3 message be received within
$\alpha$ local time from receipt of the Step~1 message;
\item
 $P$ delays Step~4 until
the entire interaction, from the receipt of the Step~1
message to the sending of the Step~4 message, takes at least $\beta$
local time.
\end{enumerate}
 This is as in Figure \ref{time_zk}.
We assume that the adversary is constrained by the
$(\alpha,\beta)$ constraint.
%where the bounds $\alpha$ and $\beta$ are chosen to satisfy:
%the real time elapsed in all concurrent measurements by (copies of) $P$
%of $\alpha$ is less than
%the real time elapsed in every measurement by $P$ of $\beta$.







\remove{
Conceptually, the modified protocol becomes:

\noindent
{\bf Protocol III: CoZK \PKA{}}\\
1. $\VtoP$ Commitment to $r$\\
2. $\VwithP$ proof of knowledge of $r$ with timing\\
3. $\VtoP$ $E(m \cdot r)$ and NIZK proof of consistency\\
4. $\PtoV$ $r$

{\it Timing Constraints}:
(1) $P$ requires the Step~3 message be received within
$\alpha$ (local) time from receipt of the Step~1 message;
(2) $P$ delays Step~4 until
the entire interaction, from the receipt of the Step~1
message to the sending of the Step~4 message, takes at least $\beta$
local time; where
the bounds $\alpha$ and $\beta$ are chosen to satisfy:
the real time elapsed in all concurrent measurements by (copies of) $P$
of $\alpha$ is less than every measurement by $P$ of $\beta$.
}




\begin{theorem}
\label{IIIczk}
Protocol \ref{protIII} is sound and is concurrent $\varepsilon$-knowledge.
\end{theorem}

\begin{proof}
%%PPP changed proof to fit the new protocol
The proof of soundness follows from
the security  of $E$, that it is non-malleable
against a chosen ciphertext Post-processing
attack, as was shown in Lemma 3.6 of~\cite{DDN}.

The proof of concurrent $\varepsilon$-knowledge
is essentially identical to the proof of
 of Theorem~\ref{IIczk}.
%PPP Should we give more details?
\end{proof}

%PPP Is it interesting to give a zk deniable protocol (As opposed to
%epsilon knowledge?

Given the elegant and efficient
non-malleable encryption scheme of Cramer and Shoup~\cite{CS}, based on the
Decisional Diffie-Hellman assumption,
Protocol \ref{protIII}
 is also efficient.

\remove{
Note that if $V$ knows the inner product of $r$ with $2n/3$ random strings
then $r$ is extractable from $V$, since by rewinding and
obtaining the inner product of $r$ with $2n/3$ new random strings
the simulator has enough information to reconstruct $r$.
This will be the strategy of the simulator: to obtain the
inner product of $r$ with $n$ random strings,
using the techniques of the proof of Theorem~\ref{IIczk}.

As in the proof of Theorem~\ref{IIczk}, we consider \tce s.
Consider an arbitrary interaction, say with $V_i$.
$V_i$ sends $C(r_i)$.
In the process of trying to extract $r_i$
the simulator is willing to start (at $\A$'s request)
up to $t-1$ additional concurrent interactions.
In each of these concurrent interactions
it sends only commitments to vectors of randomly chosen
bits and, as needed, opens these commitments.
Because of the $(\alpha,\beta)$ requirement the simulator
never has to issue the Step~4 message ($r_j$ for any $j>i$).
If, even after running up to $t$ concurrent
interactions and waiting until time $\alpha$ has elapsed, the simulator
has not received the Step~3 message from $V_i$,
then the simulator rewinds $V_i$ to just after Step~1 and tries
again to obtain the Step~3 message.
As above, if a conditionally delinquent verifier opens
its queries during an extraction attempt, the attempt is not
counted and the trial is repeated.
If after $t^2/\ve$ %counted
trials the Step~3 message
is not received from $V_i$, then $V_i$ is classified as
conditionally delinquent.
However,
if $V_i$ sends the Step~3 message during one of the trials
then the computation is rewound to just after Step~1, and the
simulator sends to $V_i$ a new vector of random bits in Step~2.
Everything proceeds as in the first attempt to obtain the
Step~3 message from $V_i$,
except that the attempt continues until it is successful.
%(With all but negligible probability this will occur within $O(t^2)$
%trials.)
At this point the simulator knows the inner product of $r$ with
$4n/3 = 4|r|/3$ randomly chosen strings and hence, with overwhelming
probability, knows $r$.
The rest of the argument follows the proof of Theorem~\ref{IIczk}.
} %end of lackofspace

%cynthia: merged into previous theorem to save space
%\begin{theorem}
%\label{IIIsound}
%Protocol III is sound.
%\end{theorem}
%The proof of Theorem~\ref{IIIsound} follows from
%the non-malleability of $E$, much in the same way as in \cite{DDN}.

\remove{
Let us re-write Protocol~III using a slightly different format.
\begin{tabbing}
xxx\= xxxxxx\= xxxx\= \kill
{\bf Protocol III': (Re-formatted) Concurrent ZK \PKA with Timing}\\
A: \> 1.  \> $\VtoP$ Commitment to $r$ \\
   \> 2a. \> $\VtoP$ Commitments to $r_0^1,r_1^1, \dots,
                                r_0^n r_1^n$ (\MBC 1) \\
B: \> 2b. \> $\PtoV$ \> $b^1, \dots, b^n$ (\MBC 2)\\
C: \> 2c. \> $\VtoP$ \> $r \oplus r_{b^1}$, \dots, $r \oplus r_{b^n}$\\
                     \> NIZK proofs of consistency with commitment to $r$\\
                     \> open $r_{1-b^1}, \dots, r_{1-b^n}$\\
   \> 3.  \> $\VtoP$ \> $E(m \cdot r)$ and NIZK proof of consistency with
                                        $r$\\
D: \> 4.  \> $\PtoV$ $r$
\end{tabbing}
}










\subsection{On-Line \PKA}

\begin{figure}[ht]
\epsfbox{time_da.eps}
\caption{Timing requirements for the
On-Line Deniable Authentication  ZK protocol.}
\label{time_da}
\end{figure}

The next protocol does not achieve zero-knowledge;
indeed there will be digitally signed evidence that a conversation
has taken place.  However, the protocol ensures that
the signature is only on random noise and a commitment to
(different) random noise.
Other than the signatures on random noise, the protocol
%achieves zero-knowledge by having
achieves deniability  by having
%\mn{Changed zk to deniability}
the prover eventually release what is essentially
a ``session key'' a short while after the end of the ``session.''
Therefore the weakened form of deniability obtained is as follows:
suppose that the  prover is willing to authenticate
some sequence of messages $m_1, m_2,  \ldots m_{\ell}$.
Then for any verifier $V'$ there is a simulator that communicates
with the above prover and
produces a transcript that is
indistinguishable from the transcript obtained
by $V'$ communicating with
an authenticator willing to authenticate
%cynthia: changed; CHECK!
%any message.
this sequence.
The above notion is satisfactory in that apart from the fact
that the prover authenticated some messages, no other information
is leaked and no receipt is left with the verifier.
This relaxation allows us to obtain an efficient protocol for the task.



In Protocol~\ref{protIV}
 the function $auth_k$ can be any keyed authentication
function or MAC, such as DES.  The important property is that for a random
$k$ the adversary  cannot guess with non-negligible probability
$auth_k(m)$ given $auth_k(m')$ even if
$m \neq m'$ are chosen by the adversary, provided $k$ is chosen at random
and not known to the adversary.
The signature function $sign$ must be existentially unforgeable (see
\cite{gmri} for definitions and \cite{CD,dn2} for efficient constructions).
The protocol ensures that (eventually)
the session key used will be shared by $P$ and $V$.
%moved the next sentence here from after the timing constraints
Note that $V$ cannot {\em check} the Step~3 authentication
until it receives $r_1$ in Step~4.
\remove{
An essential assumption of the $auth$ function is that,
knowing $(m_1,auth_k(m_1)), \dots, (m_n,auth_k(m_n))$
does not in any way help
an adversary construct a valid $(m',auth_k(m'))$ for
$m' \notin \{m_1, \dots, m_n\}$.
}

The prover  $P$ has a public-key
$E$, chosen from  an existentially unforgeable
signature scheme.
$P$  wishes to authenticate a message $m$ to the Verifier $V$.
\begin{proto}
\label{protIV}
{\bf  On-Line \PKA  Using Signatures}\\
\begin{tabbing}
xxx\= xxxxxx\= xxxx\= \kill
\>1. $\PtoV$  Choose $r_1 \in_R \{0,1\}^n$  and send $C(r_1)$\\
\>2. $\VtoP$ Choose $r_1 \in_R \{0,1\}^n$  and send $r_2$\\
\>3. $\PtoV$ $auth_{r_1 \oplus r_2}(m)$\\
\>4. $\PtoV$ $sign(C(r_1) \circ r_2)$, $r_1$
\end{tabbing}
\end{proto}


\noindent
{\it Timing Constraints}:
\begin{enumerate}
\item
$P$ delays Step~4 until more than $\beta$ time has elapsed on $P$'s
local clock since $r_2$ is received in Step~2.
\item
$V$ accepts the authentication
received in Step~3 only if it is received within time
$\alpha$ on $V$'s local clock from when $r_2$ is sent in Step~2.
\end{enumerate}
See Figure \ref{time_da}.
The adversary is constrained by the
$(\alpha,\beta)$ constraint.
Here the constraint is needed for the security of {\em both} parties.
%so that the real time
%in any concurrent execution elapsed
%while $\beta$ passes on $P$'s clock exceeds in all concurrent
%executions the real time required for $\alpha$ to elapse on $V$'s clock.


%Note that the timing constraints here differ a bit in flavor from
%the timing constraints on Protocols I--III in that they refer to the
%clocks of {\em both} participants.








\begin{theorem}
\label{IVsound}
Protocol \ref{protIV} is sound.
\end{theorem}

\begin{proof}
Let $P^*$ try to impersonate $P$.
Suppose $P^*$ sends $C(r_1)$ at time $s$ in an interaction with
a particular $V$.
Either $C(r_1)$ appeared as a message sent
in some  previous execution by the real $P$ or not.
If not, then $P^*$ will with all but
negligible probability never get a signature from $P$ on
a string with prefix $C(r_1)$.
So assume such a message was sent by the real prover $P$, necessarily
at some time before $s$. (This allows us to concentrate on one
particular execution and ignore all the rest.)
Let $V$ respond with $r_2$ at time $s' > s$.
  The only signature that $V$ will accept at Step~4 is on $C(r_1) \circ r_2$,
  so $P^*$ must get from $P$ a signature on $C(r_1) \circ r_2$.
This forces $P^*$ to send $r_2$ to $P$ at some time $s'' > s'$.
But then $P$ will not release $r_1$ before $s'' +$ the time
for $\beta$ to elapse on $P$'s local clock.
Without knowing $r_1$, $P^*$ cannot guess $auth_{r_1 \oplus r_2} (m')$
for  any message $m'$
other than the message $m$ that $P$ authenticates with $r_1 \oplus r_2$.
Thus, the only message that $P^*$ can authenticate to $V$ with
$r_1 \oplus r_2$ in a timely fashion (by time $s'+$ the time for
$\alpha$ to elapse on $V$'s local clock)
is the message $m$ authenticated by $P$.
\end{proof}

Protocol~\ref{protIV} {\em cannot be} zero-knowledge
because of the signature on $C(r_1) \circ r_2$.
However, we prove the weakened form of deniability defined above:
\begin{theorem}
For any polynomial time adversary controlling verifiers $V_1, V_2,
\ldots V_k$ there exists a polynomial time simulator
$\S$ such that if $\S$ is communicating
with a prover willing to authenticate {\em some} sequence of messages
$m_1, m_2, \ldots m_{\ell}$, then $\S$
can produce a transcript indistinguishable
from an actual transcript.
\end{theorem}
\begin{proof}
$\S$ will play a person-in-the-middle between the
verifiers and the true prover. Following each Step 2 of a verifier $V_i$ the
simulator $\S$
 freezes $\A$ until it receives $r^i_1$ in Step 4 as well as the signature
from the real prover. Once it has this information
 $\S$ can  compute $auth_{r_1^i \oplus r_2^i}( \cdot)$ for any message and
 and $V_i$ will accept the proof.
\end{proof}


\begin{remark}
%As in the case of Protocol~II,
The use of timing can be partially
replaced by employing moderately
hard functions.
In the case of Protocol~\ref{protIV}
we could use moderately hard functions for commitment
in Step~1 or  for signing in Step~4.
For the latter we should use the
shortcut in the terminology of~\cite{dn} and in this case we can actually
make the protocol zero-knowledge.
For soundness the verifier would require the Step~4 message
to be received within a reasonably short time after the Step~2 message
was sent: the delay should be considerably less than $\tau$, the time to
generate a ``signature'' without the short-cut information.
Thus, the real time required for $\alpha$ to elapse on $V$'s
clock in any concurrent execution must be less than the real
time required for $\beta$ to elapse on $P$'s clock in any execution; and
the time for $\beta$ to elapse in any concurrent
execution on $P$'s clock must
be less than $\tau$.
\end{remark}


\remove{
%%%PPP Removed since it is less interesting given current protocol III
%Cynthia: added the new protocol V
The security of  Protocol~V below is
similar to that of Protocol~IV; however, it uses
a non-malleable encryption function $E$ in place of a signature.
Given the elegant and extremely efficient
non-malleable encryption scheme of~\cite{CS}, based on the
Decisional Diffie-Hellman assumption,
this scheme is also efficient.
\begin{tabbing}
xxx\= xxxxxx\= xxxx\= \kill
{\bf Protocol V: On-Line \PKA{}  Using Non-Malleable PKC}\\
\>1. $\PtoV$ $C(r_1)$\\
\>2. $\VtoP$ $r_2$, $E(r_2  \circ C(r_1) \circ r_3)$ \\
\>3. $\PtoV$ $auth_{r_1 \oplus r_2}(m)$\\
\>4. $\PtoV$ $r_3$, $r_1$
\end{tabbing}

\noindent
{\it Timing Constraints}:
$P$ delays Step~4 until more than $\beta$ time has elapsed on $P$'s
local clock since $r_2$ is received in Step~2.
$V$ accepts the authentication
received in Step~3 only if it is received within time
$\alpha$ on $V$'s local clock from when $r_2$ is sent in Step~2.
The adversary is constrained by the
$(\alpha,\beta)$ constraint.
Here the constraint is needed for the security of {\em both} parties.


}%remove


\remove{
\subsection{On-Line \PKA{} With No Paper Trail}

The next protocol strongly resembles Protocol~IV.
However, in Protocol~V the signature by $P$ is
only on a completely random string (rather than on a string
whose prefix is a commitment to a random string).
\begin{tabbing}
xxx\= xxxxxx\= xxxx\= \kill
{\bf Protocol V:}\\
\>1. $\VtoP$ $K(r_2)$\\
\>2. $\PtoV$ $C(r_1)$\\
\>3. $\VtoP$ $r_2$\\
\>4. $\PtoV$ $auth_{r_1 \oplus r_2}(m)$\\
\>5. $\PtoV$ $r_1, sign(r_1 \oplus r_2)$
\end{tabbing}
%\noindent
%{\it Timing constraints}: $V$ requires the Step~4 message within $\delta$ of
%Step~3.  $P$ waits more than $\delta$ time between Steps~4 and~5.

\noindent
{\it Timing Constraints}:
$P$ delays Step~5 until more than $\beta$ time has elapsed on $P$'s
local clock after Step~4.
$V$ accepts the authentication
received in Step~4 only if it is received within time
$\alpha$ on $V$'s local clock from when $r_2$ is sent in Step~3.
The adversary is constrained by the $(\alpha,\beta)$ constraint.
% so that the real time
%in any concurrent execution elapsed
%while $\beta$ passes on $P$'s clock exceeds in all concurrent
%executions the real time required for $\alpha$ to elapse on $V$'s clock.



\begin{theorem}
\label{Vsound}
Protocol V is sound.
\end{theorem}

\begin{proof}
(Sketch)
Let $P^*$ be a cheating prover trying to impersonate $P$,
let $k = r_1 \oplus r_2$, where $r_1$ was committed to by $P^*$
in Step~2 and $r_2$ was committed to by $V$ in Step~1.
Let $m'$ be the message that $P^*$ is trying to authenticate.
Let $P^*$ receive its Step~3 message at time $s$.
If $m'$ is a message that $P$ does not wish to authenticate then
$P^*$ must learn $k$ before time $s+$ the time
for $\alpha$ to pass on $V$'s local clock, and must
eventually obtain a signature on $k$.
The only way to meet the second requirement is to
arrange an interaction with $P$ in which a cheating verifier
controlled by the adversary $\A$
commits to $x$ to $P$ and $P$ responds with
a commitment to $y$, where
$x \oplus y = k$.
Clearly, since $y$ is chosen by the good prover, $y$ is
independent of $r_2$.
We claim $x$ must depend on $r_2$.  Suppose otherwise.
Then $P^*$ would have to be able to commit to $r_1$ satisfying
$r_1  = r_2 \oplus x \oplus y$, which it cannot do without
knowing $r_2$.
By the semantic security of the commitment scheme, $P^*$ cannot
know $x$ before it learns $r_2$.
Similarly, we claim that $r_1$ depends on $y$.
For otherwise $x \oplus y$ would be independent of
$r_1 \oplus r_2$.
Putting these requirements together, we see that $P^*$ cannot
learn $r_1$, and hence $x$, before time $s$,
and therefore the adversary cannot
arrange for $P$ to receive $x$ before
time $s'>s$; hence $P$ will not release $y$ (and hence $k$) before
time $s' +$ the time for $\beta$ to elapse on $P$'s
local clock.  This sum exceeds $T = s + $ the time for $\alpha$ to
elapse on $V$'s local clock.
However, in order to compute $auth_k(m')$ in a timely fashion, the adversary
must learn $k$ before $T$.
\end{proof}


We say a digital signature scheme is {\em pair-forgeable}
if, without the secret signing information,
it is easy to construct valid random $(m,sign(m))$ pairs,
for example, when $m$ is
randomized by first choosing $sign(m)$ at random and then
computing $m$ from its signature,
but it is hard to find $sign(m)$ given a random {\em target} $m$.
For example, the (vanilla) RSA digital signature scheme \cite{rsa}
has this property, assuming that ``RSA assumption" holds
(See~\cite{dn2} and \cite{gmri} for discussion).


\begin{theorem}
\label{Vczk}
If the digital signature scheme used in Protocol~V
is pair forgeable, then Protocol~V is concurrent zero-knowledge.
\end{theorem}

\begin{proof}
The proof follows essentially the same lines as the proof of
Theorem~\ref{IIczk}.
As each new execution is initiated by $\A$,
the simulator creates a valid $(k,sign(k))$ pair, proceeds
with extraction of $r_2$ in order to choose $r_1 = k \oplus r_2$, rewinds,
and commits to $r_1$.
\end{proof}



\begin{remark}

%1. Like Protocol~IV,
%Protocol~V admits re-casting of the timing constraints in
%terms of moderately hard functions.

 Protocol~V can be modified in exactly the same way as Protocol~II
to yield Protocol~V$'$, for which there exists a simulator that
produces simulated transcripts with a distribution
computationally indistinguishable from the real distribution on transcripts.

\end{remark}



\lackofspace{
\begin{tabbing}
XXX \= XXXXX \= XXXXX \= \kill
{\bf Protocol V':}\\
1. \> $\VtoP$ $K(r_2)$\\
\>\> $g = g_1^a \bmod p $ and $g' = g_1^{a'}$ for $a,a' \in_R \Z_q$\\
2. \>$\PtoV$ Information-theoretic commitment using $K_{g_1,g,p}$ to $r_2$ \\
\>\> $r \in_R \Z_q$\\
3. $\VtoP$ $r_2$ and $a + ra' \bmod q$\\
4. $\PtoV$ $auth_{r_1 \oplus r_2}(m)$\\
5. $\PtoV$ $r_1, sign(r_1 \oplus r_2)$
\end{tabbing}
} %end of lackofspace



}%of remove


\section{Recent Work}
\label{additional}

The existence of a Trusted Center
considerably simplifies the design and proof
of many concurrent zero-knowledge arguments, including
arguments for all of NP,
{\em without recourse to timing}.
Dwork and Sahai have designed a timing-based preprocessing
to simulate the trusted center for the purposes
of achieving concurrent zero-knowledge~\cite{DS}.
Once a particular prover and verifier have executed the
preprocessing protocol, any polynomial number of subsequent
executions of a rich class of protocols will be concurrent zero-knowledge.
Thus, all use of timing is moved into a
preprocessing
phase, executed once for each $(P,V)$ pair, whenever in real time
they choose to do it.
%, and serving all their (polynomially many) future
%interaction needs
%for protocols in this class.

%cynthia: removed open questions.

% \cd{Add stuff about the two different notions of
% simulability.  Directions for future research, etc.}

% \as{Ask if we can move from DLA to more general assumption
% for II'?}
\op{
The most interesting research direction is whether timing techniques can
be used in order to obtain non-malleability.
The current non-malleable protocols
are rather cumbersome and require many rounds.
}








%\cd{for which protocol?}
%commitment is fast\\
%opening/verification is fast\\
%offline it can be broken moderately quickly (i.e. semantic security is
%violated)

\medskip
\noindent
{\bf Acknowledgment}
%\cd{reworded so that we are all thanking everybody.  OK, Amit?}
The authors are indebted to Russell Impagliazzo for motivating discussions,
and to Oded Goldreich, Mihir Bellare, and Shafi Goldwasser
for several valuable discussions.



\begin{thebibliography}{}
{%\footnotesize


\bibitem{BG}
 M. Bellare and S. Goldwasser. {\em Encapsulated key escrow.}  Manuscript,
      November 1996.
Earlier version was MIT Laboratory for Computer Science Technical
      Report 688, April 1996.

\bibitem{BIJ}
M. Bellare, R. Impagliazzo, and
M. Jakobsson, {\sl private communication}

\bibitem{BJY}
  M. Bellare, M. Jakobsson and M. Yung. Round-optimal zero-knowledge
      arguments based on any one-way function.  Advances
      in Cryptology- EUROCRYPT '97 Proceedings,
Lecture Notes in Computer Science Vol. 1233,
      %Fumy ed,
Springer-Verlag, 1997, pp.\ 280--305.

\bibitem{BR}
 M. Bellare and P. Rogaway,
{\em Provably Secure Session Key Distribution - The Three Party Case},
Proc. 27th STOC, 1995, pp 57--64.

\bibitem{BY} M. Bellare and M. Yung.
{\em Certifying permutations: Noninteractive zero-knowledge based
on any trapdoor permutation},
Journal of Cryptology, 9(3):149-166, 1996.


\bibitem{BGW}
M.\ Ben-Or, S.\ Goldwasser, and A.\ Wigderson,
{\em Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed
Computation},
{Proc.\ 20th ACM Symp.\ on Theory of Computing},
1988, pp.\ 1--10.

\bibitem{BD} T. Beth and E. Desmedt,
 Identification Tokens - or: Solving the Chess Grandmaster Problem.
Advances in Cryptology--CRYPTO '90,
 Lecture Notes in
Computer Science, Vol. 537,
Springer-Verlag, 1991, pp.\ 169--177.


\bibitem{Blum} M. Blum. {\em
Coin flipping by telephone: A protocol for solving impossible
problems}. In Allen Gersho, editor, Advances in Cryptology: A Report on
CRYPTO 81, pages 11-15, 24-26 August 1981. Department of Electrical and
Computer Engineering, U. C. Santa Barbara, ECE Report 82-04, 1982.


\bibitem{Bl}
M. Blum,
{\em How to Prove a Theorem So No One Else Can Claim It},
Proc. of the International Congress of Mathematicians, Berkeley, California,
USA, 1986, pp. 1444-1451.


\bibitem{BDMP} M. Blum, A. De Santis, S. Micali, and G.
Persiano. {\em Noninteractive zero-knowledge},
SIAM Journal on Computing, 20(6):1084-1118, 1991.


  \bibitem{BFM} Blum M., P. Feldman  and S. Micali,
  {\em Non-Interactive Zero-Knowledge Proof Systems},
  Proc. 20th ACM Symposium on the Theory of Computing,
  Chicago,  1988, pp 103-112.

\bibitem{BCY}
 G. Brassard, C.   Crepeau
and M.  Yung,
{\em Constant-Round Perfect Zero-Knowledge Computationally Convincing Protocols
}. Theoretical Computer Science 84, 1991.

\bibitem{BC}
S. Brands and D.  Chaum, {\em Distance-Bounding Protocols}
Advances in Cryptology -- EUROCRYPT`93, 1993,
Lecture Notes in Computer
Science, Vol. 765, Springer Verlag, 1994,
pp.\ 344--359.
%\bibitem{cdno}
%R. Canetti, C. Dwork, M. Naor, R. Ostrovsky,
%{\em Deniable Encryption,}
%``Security in
%Communication Networks'' workshop, Amalfi, Italy 1996
%and CRYPTO'97



\bibitem{CVA}
D. Chaum and H. van Antwerpen, {\em Undeniable Signatures},
Advances in Cryptology--CRYPTO '89,
 Lecture Notes in Computer
Science, Vol. 435,
 Springer-Verlag, 1990, pp.\ 212--216.

\bibitem{chp}
D. Chaum, E. van Heijst and B. Pfitzmann,
{\em Cryptographically strong undeniable signatures, unconditionally
secure for the signer},
Advances in Cryptology - Crypto '91, Lecture Notes in
Computer Science  576, Springer Verlag, 1992,
pp. 470--484.


\bibitem{CD}
R. Cramer and I. Damgard
{\em  New Generation of Secure and Practical RSA-Based Signatures},
Advances in Cryptology--CRYPTO '96. Springer-Verlag, 1996.

\bibitem{CS}
R. Cramer and V. Shoup
{\em A Practical Public Key Cryptosystem
Provably Secure against Adaptive Chosen Ciphertext Attack},
private communication, 1998.

%\bibitem{DY} A. De Santis and M. Yung.
%{\em Cryptographic Applications of the Metaproof and Many-prover Systems},
%Proc. CRYPTO'90, Springer-Verlag, 1990.

\bibitem{DIO}
G.\ Di Crescenzo, Y. Ishai and R. Ostrovsky,
{\em Non-Interactive and Non-Malleable Commitment},
Proc.\ 30th Annual ACM Symposium on the Theory of Computing,
  Dallas, 1998, pp.\ 141--150.


\bibitem{DDN}
D. Dolev, C. Dwork and M. Naor,
{\em Non-malleable Cryptography},
Preliminary version: Proc. 21st STOC, 1991. Full version:
to appear, Siam J.\ on Computing. Available:
http://www.wisdom.weizmann.ac.il/~naor

\bibitem{dn}
C. Dwork and M. Naor,
{\em
Pricing via Processing -or- Combatting Junk Mail},
Advances in Cryptology -- CRYPTO'92,
Lecture Notes in Computer Science
\bibitem{dnpatent}
C. Dwork and M. Naor,
{\em  Method for message authentication from non-malleable crypto systems},
US Patent No.\ 05539826, issued Aug. 29th 1996.




\bibitem{dn2}
C. Dwork and M. Naor,
{\em
An Efficient Existentially Unforgeable Signature Scheme and its
Applications},
{Journal of  Cryptology}, vol 11, 1998, pp.\ 187--208.

\bibitem{DS}
C. Dwork and A. Sahai, {\em Concurrent Zero-Knowledge: Reducing the
Need for Timing Constraints},  Lecture Notes in Computer
Science, Vol. 1462, Springer Verlag, 1998, 442--457.

 \bibitem{ffs}  U. Feige, A. Fiat and A. Shamir,
  {\em  Zero Knowledge Proofs of Identity},
 J. of Cryptology 1 (2), 1988, pp.\ 77-94. %(Preliminary version in STOC 87).

 \bibitem{fs}  U. Feige  and A. Shamir,
{\em  Witness Indistinguishable and Witness Hiding Protocols}
Proc. 22nd STOC, 1990, pp. 416--426.

  \bibitem{FLS}  U. Feige, D. Lapidot and A. Shamir,
  {\em  Multiple Non-Interactive Zero-Knowledge Proofs
Based on a Single Random String},
Proceedings of 31st Symposium on
  Foundations of Computer Science, 1990, pp. 308-317.


\bibitem{GKR}
R. Genaro, H. Krawczyk and T. Rabin,
{\em RSA-Based Undeniable Signatures},
Advances in Cryptology -- CRYPTO'97,
Lecture Notes in Computer Science 1294,  Springer-Verlag,
1997, pp.\ 132--149.


\bibitem{Gold} O. Goldreich, {\bf Foundations of Cryptography}
(Fragments of a Book), 1995.
Electronic publication:
http://www.eccc.uni-trier.de/eccc/info/ECCC-Books/eccc-books.html
(Electronic Colloquium on Computational Complexity).
  \bibitem{GGM} O. Goldreich S. Goldwasser and S. Micali,
  {\em How to Construct Random Functions },
  J. of the ACM 33 (1986), pp. 792-807.



\bibitem
{GK}  O.~Goldreich and H.~Krawczyk. {\em On the Composition of Zero Knowledge
Proof Systems}. SIAM J.~on Computing, Vol.~25, No.~1, pp.~169--192, 1996.

 \bibitem{gmw1} O. Goldreich, S. Micali and A. Wigderson,
  {\em Proofs that Yield Nothing But their Validity, and a Methodology of
  Cryptographic Protocol Design},
  J. of the ACM 38, 1991, pp. 691--729.

\bibitem{GMR}
 S. Goldwasser, S. Micali and C. Rackoff,
  {\em The Knowledge Complexity of Interactive Proof-Systems},
Siam J. on Computing, 18(1) (1989), pp 186-208.


\bibitem{GMW2}
O.\ Goldreich, M.\ Micali, A.\ Wigderson,
{\em How to play any mental game},
Proc.\ 19th ACM Symp.\ on Theory of Computing, 1987, pp.\ 218--229.

\bibitem{GP}
O. Goldreich and E. Petrank,
{\em Quantifying Knowledge Complexity},
Proc. 31st FOCS, pp. 59--68, 1991

\bibitem{gm} S.~Goldwasser and S.~Micali. {\em Probabilistic
Encryption}, Journal of Computer and System Sciences, Vol.~28,
April 1984, pp.~270--299.

\bibitem{gmr} S. Goldwasser, S. Micali, and C. Rackoff,
{\em The Knowledge Complexity of Interactive Proof Systems,}
SIAM Journal on Computing, Vol. 18, 1 (1989), pp. 186-208.

  \bibitem{gmri} S. Goldwasser, S. Micali and R. Rivest,
  {\em A Secure Digital Signature Scheme},
  SIAM Journal on Computing, Vol. 17, 2 (1988), pp. 281-308.

\bibitem{KP1}
J. Kilian and E. Petrank,
{\em An Efficient Non-Interactive Zero-Knowledge Proof System for
NP with General Assumptions},
Journal of Cryptology, Vol.\  11(1), 1998, 1-27.

\bibitem{KPR} J. Kilian, E. Petrank and C. Rackoff,
{\em Lower Bounds for Zero Knowledge on the Internet},
Proceedings of 39th Symposium on
  Foundations of Computer Science, 1998, pp.\ 484--492.



\bibitem{Kocher} P. Kocher,
{\em Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS and
Other Systems},
Advances in Cryptology - CRYPTO '96,
 Lecture Notes in Computer
Science, Vol. 1109, Springer-Verlag,
 1996,  pp.\ 104--113.

\bibitem{KR}
H. Krawczyk and T. Rabin,
{\em Chameleon Hashing Signatures},
{\sl manuscript}

%\bibitem{micali} S. Micali. {\em CS proofs} (extended abstract).
%Proc. 35th Annual Symposium on Foundations of Computer Science,
%pages 436-453, Santa Fe, New Mexico, 1994. IEEE.


\bibitem{N}
M. Naor, {\em Bit Commitment Using Pseudo-Randomness},
Journal of Cryptology, vol 4, 1991, pp.\ 151--158.

\bibitem{RS}
C. Rackoff and D. Simon,
{\em Non-Interactive Zero-Knowledge Proof of Knowledge and
Chosen Cipherext Attack},
Advances in Cryptology - CRYPTO '91,
 Lecture Notes in Computer
Science, Vol. 576, Springer-Verlag, 1992,
 pp.\ 433--444.


\bibitem{rsw}
R. L. Rivest, A. Shamir and D. A. Wagner,
{\em Time-lock puzzles and time-release Crypto}, manuscript 1996.
Available:
http://theory.lcs.mit.edu/~rivest/RivestShamirWagner-timelock.ps


 \bibitem{rsa} R. Rivest, A. Shamir and L. Adleman,
  {\em  A Method for Obtaining Digital Signature and Public Key Cryptosystems},
  Comm. of ACM, 21 (1978), pp 120-126.

\bibitem{RK} R. Richardson and  J. Kilian,
{\em On the Concurrent Composition of Zero-Knowledge Proofs},
Advances in Crytology - EUROCRYPT '99
 Proceeding, Lecture Notes in Computer Science, Vol. 1592, Springer-Verlag, 199
9,
 pp.\ 415--431.






} %end footnotesize
\end{thebibliography}{}

\appendix

Here is a six round non-efficient
protocol based on the Feige Shamir idea of ORing with
a  (presumed) bogus statement. It is an adaptation of the
4-round protocol of Bellare Jacobson and Yung.

Suppose the the "basic" proof is for circuit satisfiability
and it is a proof of knowledge of a satisfying assignment to the circuit.
Let $f$ be one-way function. We will OR the original circuit
with a circuit $\phi_y$ that is satisfied when the prover knows $x$ such
that $y=f(x)$. If $x$ is chosen by the verifier and not known to the
prover, then this shouldn't help him.
Note that commitment are used only in step 4, so the prover has plenty of
time to send the pad for the commitment.


1)Verifier: Choose pairs
i$(x_1^0, x_1^1), (x_2^0, x_2^1), \ldots  (x_n^0, x_n^1)$
  and compute and send $(y_1^0, y_1^1), (y_2^0, y_2^1), \ldots
 (y_n^0, y_n^1)$
  where $y_i^b = f(x_i^b)$.

2) Prover: choose $n$ random bits $b_1, b_2, \ldots b_n$ and send them.

3) Verifier: open $x_i^{b_i}$

4) Prover Commit to a circuit representing the original circuit ORed
   with  $\phi_i$ where $\phi_i$ is the circuit satisfiability  for
   $y_i^{1-b_i} = f(x_i^{1-b_i})$.

5)  verifier sends challenge for the above commitments

6) Prover opens commitment

 Timing Constraints:
(1) $P$ requires the Step~3 message be received within
$\alpha$ (local) time from receipt of the Step~1 message;
(2) $P$ delays Step~4 until
the entire interaction, from the receipt of the Step~1
message to the sending of the Step~4 message, takes at least $\beta$
local time.

Soundness follows from the proof of knowledge - either you extract
one of the unopened $x_i$'s or the original proof.
You can do the extraction, since in step 5 the verifier has
complete freedom in choosing the challanges.
Zero-knowledge follows  from the  fact that you can extract whp at least
one $x_i$ that wasn't opened in the main branch.


\end{document}


%cynthia2: Amit's stuff is here
\appendix
\begin{tabbing}
XXX\= XXX\= XXXXX\= \kill
{\bf Protocol II': Generic Perfect CoZKA with Timing}\\
\>0. $\PtoV$ primes $p_P$,$q_P$, and $g_P,h_P \in \Z_{p_P}^*$, where\\
\>\>    $ord(g_P)=q_P$, and $h_P=g_P^b \bmod p_P$, for $b \in_R \Z_{q_P}$.\\
\>1. $\VtoP$ $K_{g_P,h_P,p}(\vec{q})$ to all $n$ queries, \\
\>\>    primes $p_V, q_V$, and  $g_V, h_V, h_V' \in \Z_{p_V}$,\\
\>\>    where $ord(g_V) = q_V$, $h_V = (g_V)^{a} \bmod p_V$,\\
\>\>    and $h_V' = (g_V)^{a'} \bmod p_V$, for $a,a' \in_R \Z_{q_V}$\\
\>2. $\PtoV$  commitment using $K_{g_V,h_V,p_V}$ to all $n$\\
\>\> graphs, and $K_{g_V,h_V,p_V}(r_P)$, for $r_P \in_R \Z_{q_V}$\\
\>3. $\VtoP$ $r_V \in_R \Z_{q_V}$\\
\>4. $\PtoV$ Open $r_P$.  Set $r := r_V + r_P \bmod q_V$\\
\>5. $\VtoP$ Reveal $\vec{q}$ and $c=ra + a' \bmod q_V$ \\
\>6. $\PtoV$ Check $(h_V)^r\cdot(h_V') = (g_V)^c \bmod p_V$.\\
\>\>      Reply to queries, and reveal $b$.\\
\end{tabbing}
\noindent
{\it Timing Constraints}:
%cynthia: reworded slightly
(1) $P$ requires the Step~5 message be received within
$\alpha$ (local) time from receipt of the Step~1 message;
(2) $P$ delays Step~6 until
%the entire interaction, from the receipt of the Step~1
%message to the sending of the Step~6 message, takes
at least $\beta$
local time has elapsed since the receipt of the Verifier's
Step~5 message; for the proof to be zero-knowledge
we require that the adversary be constrained by the
$(\alpha,\beta)$-constraint.
For completeness we must assume that $V$ can send the required messages
in local time $\alpha$.
%the bounds $\alpha$ and $\beta$ are chosen to satisfy:
%the real time elapsed in all concurrent measurements by (copies of) $P$
%of $\alpha$ is less than every concurrent
%measurement by $P$ of $\beta$.


In Step 2 the prover commits to the graphs and then
initiates a random string selection subprotocol for choosing the
string $r$ used in Step~5 (explained below).
Steps 3 and~4 are part of the string selection protocol.
We prove the following theorem.

\begin{theorem}
\label{II'zk}
Protocol~II' is sound and is concurrent perfect zero-knowledge.
%That is,
%for every polynomial time adversary $\A$
%there exists an expected polynomial time simulator that
%outputs a distribution identical to the distribution of actual
%transcripts of $P$ interacting with $\A$.
\end{theorem}

\remove{
Since $\Z_q$ is a field, the value of the function $f(r) =
a+ra'$ at two distinct points
yields $a$ and $a'$.  Thus, if we view $r$ as a challenge to $V$'s
knowledge of $a$, then by obtaining the reply by $V$ to two different
challenges we can extract $a$.  Given $a$ it is possible to
arbitrarily decommit the graphs committed to in Step~2.
To argue that this proof of knowledge of $a$ does not help
the prover to cheat (that is, does not endanger soundness),
we prove that Steps 1--5 constitute
a zero-knowledge proof of knowledge {\em on the part of the verifier}
of $a = \log_{g_V}(h_V)$.
%Furthermore, knowledge of a single $(r,c)$ pair for a randomly
%chosen $r \neq 0$
%reveals nothing about $a$ since all possible values of $a$
%remain possible, with $a'=(c-a)/r$.


We use the extraction of $a$ for the proof of concurrent zero-knowledge.
In the simulation, if the simulator
ever receives a valid Step~5 reply from $V_i$, it saves the transcript
and rewinds, repeating Step~2 for $V_i$ as many times as needed to
receive a second valid response from $V_i$.  From these two responses
the simulator obtains $a$, and resumes the saved simulation
since now the simulator's commitment in Step~2 can be opened
as needed.  Intuitively, if the probability that $V_i$ gives
a valid Step~5 response is $p_i$, one expects that $1/p_i$
trials will be needed to get a second valid Step~5 response
from $V_i$.  Thus, the total number of simulations expected
for $V_i$ is only $p_i(1+1/p_i) \le 2$, and the simulation remains
polynomial time.  This basic idea allows us to achieve
perfect zero-knowledge and yields
a formal proof for the following theorem, whose proof is omitted
for lack of space.
%The proof
%is given in Appendix~\ref{proofII':sec}.

%During extraction, the simulator attempts to get $V$'s reply
%to two different challenges.  If it succeeds then the
%commitment can be decommitted as desired.
%If $\A$ causes a conditionally delinquent verifier, say $V_i$, to
%wake up (other than during an extraction), we can
%save the current simulation, rewind, and resimulate until
%$V_i$ replies a second time, yielding the reply to a
%second challenge to $V_i$'s knowledge of $a$, and thus obtain $a$.
%The saved simulation can then be resumed, since the
%simulator's commitment in Step~2
%of $E_i$ can now be opened as needed.

}  %%END \remove

\begin{proof}
We give only a sketch of the proof of soundness; a complete
proof appears in the full version.
The proof of perfect concurrent zero knowledge is given in full.

\paragraph{Soundness.}
%We give a sketch of the proof of soundness for this protocol.  A
%complete proof appears in the full version of the paper.
%
First, observe that if a commitment using $K_{g,h,p}$
is revealed in two different ways, say $g^{r_1}h^{s_1}=g^{r_2}h^{s_2}$,
then the discrete log of $h$ with respect to $g$ can easily
be recovered; in this case it would be $(r_1-r_2)/(s_2-s_1)$.

Formally, to argue soundness, we show
that if any \ppt{} $P^*$ can convince $V$ of a false
statement with probability $\rho$, then there exists a \ppt{}
machine $M$ that can break the DLA with probability $\rho^2-\mu(n)$,
for some negligible function $\mu$.  Here, we give an informal argument
to this effect.
Note that there is no need to argue this in a concurrent setting,
since all parameters to the commitment scheme $K$ are used
only once for each $(P,V)$ interaction.
On input primes $p,q$, generator $g$ of a $q$-order subgroup of
$\Z_p^*$, and $h=g^a$, $M(p,q,g,h)$ proceeds as follows:
$M$ chooses $c,r \in_R \Z_q$, and lets $h'=g^c\cdot h^{-r}$.
$M$ uses $P^*$ as a subroutine, interacting with $P^*$
through Steps 0 and 1, using $p_V=p$, $q_V=q$, $h_V=h$, and
$h'_V=h'$.  $M$ proceeds through Steps 2-4 with $P^*$,
and receives $r_P$ in $P^*$'s Step 4 message.
$M$ then rewinds $P^*$ to Step 3, and sends $r_V=r-r_P$.
If $P^*$ then in Step 4 opens its commitment to something
other than $r_P$, then $M$ can immediately extract $a$
and terminate.  If $P^*$'s Step 4 response is the same as
before, then $M$ proceeds to Step 5, revealing its random
queries and sending the value of $c$ that it had chosen
in the beginning.  Note that $P^*$'s Step 6 check will pass
by construction of $h'$, and $P^*$ will reply correctly to all queries,
and supply $b$ such that $g_P^b=h_P$.  By assumption, we make
it this far with probability roughly $\rho$.  Now, $M$ rewinds
$P^*$ to Step 5, and using knowledge of $b$, decommits to
a new randomly chosen query vector, and gives the same $c$
as before.  Again by assumption, $P^*$ again gives a correct
Step 6 response with probability roughly $\rho$.  Now,
with all but negligible probability, there is some query bit
position which is different in the second query vector than it
was in the first.  In order for $P^*$ to have answered correctly both
times on this bit, it must have revealed some edge differently
in response to the first query than in the second.  From this,
$M$ can recover $a$, and terminate.  Thus, we have shown that
with probability roughy $\rho^2$, $M$ can break the DLA.

The proof of soundness above essentially relies on the fact that
Steps 1-5 of Protocol II' are zero-knowledge for the Verifier
with respect to $a$.  The simulator is essentially contained in
the machine $M$ described above.

\paragraph{Concurrent Perfect Zero-Knowledge -- overview.}

\newcommand{\threshold}{{t^6}}
\newcommand{\keystep}{{5}}
\newcommand{\firstPK}{{1}}
\newcommand{\Pcommitstep}{{2}}
\newcommand{\Pstep}{{6}}
\newcommand{\Vsecret}{{a}}
\newcommand{\Vkey}{{c}}
\newcommand{\keychallenge}{{r}}
\newcommand{\bruteforcetime}{{q}}  %%% Which we assume is also number of
                                   %%% possible \keychallenge's!!!!!
\newcommand{\ie}{{\it i.e.}}

In the simulation of Protocol II, the simulator builds the
output transcript step by step, calling an extraction
procedure whenever it needs information in order to produce
some message.  This extraction procedure works by simulating
the future: more precisely, for any verifier $V$, in order
to produce a Step~2 message for the output transcript, the simulator must
see the Step~3 message of the Verifier in order
to extract the Verifier's queries.
This leads to complications in the case where the Verifier, with some
probability, refuses to produce a valid Step 3 message.  This can create
problems because there is a "backwards time" dependency:  only if the
Verifier produces a valid Step 3 message in the output transcript, must
the simulator's Step 2 message in the output transcript be specially
prepared.  Because of this problem, we were not able to prove that
Protocol II is zero-knowledge, but rather $\ve$-knowledge.

Thus, we design Protocol II' to remove this "backwards time" dependency.
The simulation of Protocol II' has the same overall structure as
the simulation of Protocol II, with some important differences.
In Protocol II', observe that
the simulator can simulate any interaction perfectly up
to (but excluding) Step~\Pstep~ without access to any special information.
However, to simulate a proper Step~\Pstep~ response, the simulator needs
some secret information known only to the Verifier.  However this
information can be extracted from any two distinct valid Step~\keystep~
messages of the Verifier.  Hence, the dependency is that if the Verifier
produces a valid Step~\keystep~ message in the output transcript, then the
simulator must specially prepare the Step~\Pstep~ message in the output
transcript.  This is a "forwards time" dependency, and hence can be dealt
with roughly as follows:  If the simulator sees that the Verifier has
produced one valid Step~\keystep~ message, then it saves this transcript
(for use in the output), and rewinds to try to get the Verifier to produce
another valid Step~\keystep~ message.  Now if the Verifier produces a
valid Step~\keystep~ message with probability $p$, we expect to have to
try $1/p$ times to get another valid Step~\keystep~ message.  Hence, the
expected number of trials is $p \cdot 1/p = 1$.  Thus, the expected
running time of the procedure will be polynomial.

\paragraph{Concurrent Perfect Zero-Knowledge -- proof.}

We now turn the above intuition into a formal proof.
We will present a probabilistic simulation strategy constructed so
that its output distribution is identical to the one produced
in actual interactions.  We will then show that the simulation
has polynomially bounded expected running time
(more precisely, we will show that for any probabilistic polynomial time
adversary, for each interaction initiated by the advsersary,
the simulation will make an expected polynomial number
of queries to the adversary, and use an expected polynomial
amount of additional processing time.)

We first discuss the basic strategy of the simulation.
Protocol II' is designed along the same principles as the standard
constant-round zero-knowledge protocols for Graph Hamiltonicity,
with the main exception being that, to commit to its graphs, the
prover uses a {\em perfect information-theoretically} hiding
commitment scheme -- {\it i.e.} one where the distribution $D(x)$
of commitments to $x$ is independent of $x$.  Furthermore, this commitment
scheme is a {\em trapdoor} scheme -- one where if the committer knows
some trapdoor information, then it can decommit any commitment to any
value.  In the protocol, the verifier gives what is essentially
a zero-knowledge proof of knowledge of the trapdoor information
in Steps~\firstPK-\keystep.  In the proof of soundness, we showed
that this does not jeapordize the commitment scheme for the actual
prover.  We now show that the simulator can use this proof of knowledge
to extract the trapdoor information and use it to complete the simulation.
\\

We define a {\em valid} Step~\keystep~message to be one which is
received within time $\alpha$ of Step 1 and for which $P$'s
Step~\Pstep~check succeeds,
%%WARNING: DISCRETE-LOG SPECIFIC TEXT:
{\it i.e.}, $h_V \cdot (h'_V)^r = g_V^c \bmod p_V$.
%%END OF DISCRETE-LOG SPECIFIC TEXT:
The simulation proceeds by building an output transcript step by step
with the adversary.  Note that the simulator can simulate up to
Step~\Pstep~of any interaction with a Verifier $V_i$
without any special information, by commiting to an arbitrary value
in Step~\Pcommitstep.  At Step~\Pstep~, however,
the simulator must open the commitments made in Step~\Pcommitstep~according
to the Verifier's query.  {\em After} seeing the Verifier's queries,
the simulator can generate the exact distribution of graphs that would
arise in an interaction with a real Prover.
The only question is how the simulator can
decommit to these values, when the commitments it made in
Step~\Pcommitstep~were to arbitrary values.

This is made possible by the trapdoor property of the
information-theoretic commitment scheme: if the simulator knows the
Verifier's trapdoor information $\Vsecret$, then it can decommit to
any value.
Note that the adversary can only
require that the simulator provide a Step~\Pstep~message for $V_i$
if it has already furnished a valid Step~\keystep~message for $V_i$.
Hence, whenever the adversary provides a $(\Vkey,\keychallenge)$ pair
from a valid Step~\keystep~message for any verifier $V_i$, the simulator calls
{\tt Extract}$(V_i,T,\keychallenge,\Vkey)$,
where $T$ is the prefix of the output transcript up to and including
the Step~\firstPK~message of $V_i$, and then continues as before with
the simulation.
This call to {\tt Extract} results (as will be shown shortly)
in the determination of the trapdoor information of Verifier $V_i$,
which allows the simulator to simulate the Step~\Pstep~message for
$V_i$ if it is ever required to do so.
Note that this maintains the invariant that when any call to
{\tt Extract}$(V_i,T,\keychallenge,\Vkey)$ is made,
the simulator knows the trapdoor information of all
Verifiers $V_j$ that have given valid Step~\keystep~messages
in the partial transcript $T$.
In this manner, the simulation proceeds until the adversary terminates
all interactions, at which point the output transcript is output.

By construction, the simulator always produces prover messages according
to the same rules used by a real prover, except in the commitments
made in Step~\Pcommitstep, which in the simulation are commitments
to arbitrary values.  However, we use a perfect information-theoretically
hiding commitment scheme, so the distribution of commitments in
Step~\Pcommitstep~is the same regardless of the value being commited to.
Hence, the joint distribution of all simulated prover responses
is identical to the joint distribution of actual prover responses.
In conclusion, assuming that the {\tt Extract} procedure works
as claimed above, we have constructed a simulation whose output
distribution is indeed identical to the distribution of transcripts
produced by actual interactions of true provers with the adversary.
\\

We now describe the {\tt Extract} procedure.  On input
$(V_i,T,\keychallenge_0,\Vkey_0)$, where the partial transcript $T$
ends with the Step~\firstPK~message of $V_i$, the simulator
redoes the simulation starting at $T$, using new random coins.
It proceeds until either $V_i$ provides another valid
Step~\keystep~message, $V_i$ produces an invalid such message,
or the time limit $\alpha$ expires.  Such a partial simulation is called
a {\em trial}.  As before, the simulator can simulate up to
Step~\Pstep~of any interaction
without any special information, by commiting to an arbitrary value
in Step~\Pcommitstep.
If some verifier $V_j$ requires a Step~\Pstep~message, however,
the simulator must open the commitments made in Step~\Pcommitstep~according
to the Verifier's query.  We claim that this can only happen if
the Step~\keystep~message of $V_j$ is already in the
partial transcript $T$, which implies that the simulator has already
extracted the trapdoor information of $V_j$,
and hence the proper distribution of decommitments
can be produced by the simulator.  This claim follows from the
timing requirements of Protocol II'; in particular, we have the
following Interleaving Constraint (which clearly suffices):

\begin{center}
\fbox{
\begin{minipage}{5in}
\noindent
{\bf Interleaving Constraint:} During the interaction of any verifier $V$
from Step~\firstPK~through Step~\keystep, a prover could
need to give a Step~\Pstep~response only to those verifiers $V'$ which
provided their Step~\keystep~message before $V$'s Step~\firstPK~message was
received.
\end{minipage}
}
\end{center}

\noindent
{\bf Proof:} To see that this is true, suppose that the while $V$ was between
Steps 1 through ~\keystep~ with prover $P$,
a prover $P'$ needed to furnish the Step~\Pstep~response
to verifier $V'$.  Note that Steps 1 through ~\keystep~for $V$
must be completed within time $\alpha$ on $P$'s local clock.
By the $(\alpha,\beta)$-assumption, since all provers are assumed to
be honest, this means that
at most time $\beta$ could have elapsed
on the local clock of $P'$ during Steps 1-\keystep~of $V$ and $P$.
But $P'$ must wait time $\beta$ after receiving the Step~\keystep~message
of $V'$ before sending its Step~\Pstep~response.
Hence, the Step~\keystep~message of $V'$
must have been received by $P'$ before the Step 1 message of $V$ was
received by $P$. $\qed$

We now complete the description of {\tt Extract} procedure:
If $V_i$ provides a valid
Step~\keystep~message for a value of $\keychallenge \neq \keychallenge_0$,
then the simulator can use the two pairs of $(\keychallenge,\Vkey)$
values to extract the trapdoor information $\Vsecret$ of $V_i$,
%%WARNING: DISCRETE LOG SPECIFIC:
by solving for $\Vsecret$ in the system of two equations derived from
the constraint that $c=ra+a'$.
%%END SPECIFIC TEXT
Otherwise, the simulator conducts as many independent trials as necessary
until this happens.
In order to guarantee that {\tt Extract} will eventually produce
the trapdoor information of $V_i$, we must deal with the possibility that
there is only one value of $\keychallenge$ for which $V_i$ produces
a valid Step~\keystep~response.  (Note that this value of $\keychallenge$
occurs with extremely low probability.)  To handle this case, in parallel
with each trial, the simulator does one step of
a systematic brute-force attack to
determine the trapdoor information
%%WARNING: DISCRETE LOG SPECIFIC-TEXT:
(in this case, trying to guess each of the $\bruteforcetime$ possible
values for the discrete log of $h_V$ with respect to $g_V$).
%%END SPECIFIC TEXT
Thus after at most $\bruteforcetime$ trials, the trapdoor information of
$V_i$ will be discovered.

\paragraph{Running Time.}  To conclude the proof, we must show that the
expected running time of the simulator is polynomially bounded.  We
will show that, for any probabilistic polynomial time adversary
whose running time is bounded by $t(n)$,
for each prover--verifier interaction initiated by the adversary,
the simulation makes an expected polynomial $(O(t(n))$ number of queries to
the adversary, and uses an expected polnomial $(poly(n)\cdot t(n))$
amount of additional processing time.
Since a polynomially bounded adversary may only
initiate a polynomial $(O(t(n))$ number of interactions, by linearity of
expectations, the total expected running time will be polynomial
$(O(poly(n) \cdot t^2(n)))$ as well.

Let $V_i$ denote the $i$'th verifier created by the adversary during
simulation.
We will charge to $V_i$ any time and oracle queries required to produce
messages for it in the output transcript.  Hence, some constant number of
queries and polynomial amount of processing time is required during
the main simulation, but we must also count the expected amount of time
and number of oracle queries used in case {\tt Extract} is called for
extracting the trapdoor information of $V_i$.

Let $T$ be any transcript up to the Step~\firstPK~message of $V_i$.
Conditioned on $T$, the adversary will have some probability $p$, over
all possible executions after $T$, of providing a valid
Step~\keystep~message from $V_i$.  We consider two cases:
\begin{enumerate}
\item $p>2/\bruteforcetime$:  Here we note that in {\tt Extract},
the probability over any trial that $V_i$ provides a valid
Step~\keystep~message for a value of $\keychallenge \neq \keychallenge_0$
is at most $p-1/\bruteforcetime > p/2$.  Hence the expected number of
trials until this occurs is at most $2/p$.  The event that {\tt Extract} is
called on $V_i$, however, occurs only with probability $p$.  Thus,
conditioned on $T$,
the expected number of {\tt Extract} trials for $V_i$ is at most
$p \cdot 2/p = 2$.
\item $p\le2/\bruteforcetime$:  Note that this means that $V_i$ is extremely
unlikely to provide valid Step~\keystep~messages.  Thus, we upper bound
the number of trials needed in {\tt Extract} by the number of steps required
for the brute-force attack on the trapdoor information to succeed, which
is $\bruteforcetime$.  Hence, conditioned on $T$,
the expected number of {\tt Extract}
trials for $V_i$ is at most $p \cdot \bruteforcetime \le 2$.
\end{enumerate}
Note that the expected number of trials for $V_i$ is always bounded by
$2$ regardless of which transcript $T$ we conditioned on.  Since the
sum of the probabilities of each possible transcript $T$ is exactly $1$,
this implies that the expected number of trials for $V_i$ is bounded
by $2$.
In each {\tt Extract} trial, at most $t(n)$ oracle calls to the adversary
are made, and certainly no more than $poly(n)\cdot t(n)$ processing time
is required, where $poly(n)$ is some fixed polynomial in $n$.

Hence, we see that the simulation runs in expected polynomial time for any
probabilistic polynomial-time adversary.  Thus, Protocol II' is
Concurrent Perfect Zero-Knowledge.
\end{proof}




\end{document}

