%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Version 2 (started on 19/09/2003): % Changing black-box concurrent ZK protocol to be that of % Richardson-Kilian, instead of PRS. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Version 1 (started on 08/09/2003): % This is the full journal version containing the upper % bound only from the STOC'03 paper on bounded-concurrent % secure 2-party computation (conc2party.tex) % In the middle of changing to STRICT-POLY simulation % with the PRS protocol. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentstyle[11pt,fullpage]{article} \title{{\bf Protocols for Bounded-Concurrent Secure Two-Party Computation in the Plain Model}} \author{Yehuda Lindell\thanks{Much of this work was carried out while the author was at IBM T.J.Watson, New York.}} \date{Department of Computer Science\\ Bar-Ilan University\\ Ramat Gan, 52900, {\sc Israel}\\ {\tt lindell@cs.biu.ac.il}\\ ~\\ \today} \newcommand{\smaller}{} \newcommand{\ynote}[1]{{(\sf Yehuda's Note:} {\sl{#1}} {\sf EON)}} \def\ni{\noindent} \def\etal{{et~al.}} \newcommand{\eqref}[1]{Eq.~(\ref{#1})} \renewcommand{\ni}{\noindent} \newcommand{\ms}{\medskip} \renewcommand{\(}{{\em (}} \renewcommand{\)}{{\em )}} \newcommand{\eqdef}{\stackrel{\rm def}{=}} \newcommand{\indist}{\stackrel{\rm c}{\equiv}} \newcommand{\bitset}{\{0,1\}} \newcommand{\rnd}{\in_R} \renewcommand{\th}{{\rm th}} \newcommand{\ov}{\overline} \newcommand{\e}{\epsilon} % \newcommand{\da}{d} % \newcommand{\SD}{\bigtriangledown} %--- \newtheorem{thm}{Theorem}%[section] % A counter for Theorems etc \newcommand{\BT}{\begin{thm}} \newcommand{\ET}{\end{thm}} \newtheorem{dfn}[thm]{Definition} % \newcommand{\BD}{\begin{dfn}} \newcommand{\ED}{\end{dfn}} %\newtheorem{corr}[thm]{Corollary} % %\newcommand{\BCR}{\begin{corr}} \newcommand{\ECR}{\end{corr}} \newtheorem{prop}[thm]{Proposition} \newcommand{\BP}{\begin{prop}} \newcommand{\EP}{\end{prop}} %--- \newtheorem{Ithm}{Theorem} % A counter for Theorems in Intro \newcommand{\BIT}{\begin{Ithm}} \newcommand{\EIT}{\end{Ithm}} \newtheorem{Icorr}[Ithm]{Corollary} % A counter for Theorems in Intro \newcommand{\BICR}{\begin{Icorr}} \newcommand{\EICR}{\end{Icorr}} %--- \newtheorem{lem}{Lemma}[section] % A counter for Lemmas etc \newcommand{\BL}{\begin{lem}} \newcommand{\EL}{\end{lem}} \newtheorem{clm}[lem]{Claim} % \newcommand{\BCM}{\begin{clm}} \newcommand{\ECM}{\end{clm}} \newtheorem{corr}[thm]{Corollary} % \newcommand{\BCR}{\begin{corr}} \newcommand{\ECR}{\end{corr}} \newtheorem{fact}[lem]{Fact} % \newcommand{\BF}{\begin{fact}} \newcommand{\EF}{\end{fact}} %--- \newtheorem{rem}{Remark}[section] % A counter for Theorems etc \newcommand{\BR}{\begin{rem}} \newcommand{\ER}{\end{rem}} %--- \newlength{\saveparindent} \setlength{\saveparindent}{\parindent} \newlength{\saveparskip} \setlength{\saveparskip}{\parskip} %--- \newenvironment{enum}{% \begin{list}{{\rm (\arabic{ctr})}\hfill}{\usecounter{ctr}\labelwidth=17pt% \labelsep=6pt \leftmargin=23pt \topsep=2pt% \setlength{\listparindent}{\saveparindent}% \setlength{\parsep}{\saveparskip}% \setlength{\itemsep}{2pt}}}{\end{list}} %--- \newenvironment{newitemize}{% \begin{list}{$\bullet$}{\labelwidth=8pt% \labelsep=5pt \leftmargin=15pt \topsep=3pt% \setlength{\listparindent}{\saveparindent}% \setlength{\parsep}{\saveparskip}% \setlength{\itemsep}{6pt} }}{\end{list}} %--- \newenvironment{newdescription}{% \begin{list}{$\bullet$}{\labelwidth=8pt% \labelsep=7pt \leftmargin=15pt \topsep=3pt% \setlength{\listparindent}{0pt}% \saveparindent}% \setlength{\parsep}{3pt} %\saveparskip}% \setlength{\itemsep}{3pt} }}{\end{list}} \newcommand{\BDE}{\begin{newdescription}} \newcommand{\EDE}{\end{newdescription}} %--- \newcommand{\BE}{\begin{enumerate}} \newcommand{\EE}{\end{enumerate}} \newcommand{\BI}{\begin{newitemize}} \newcommand{\EI}{\end{newitemize}} \def\blackslug {\hbox{\hskip 1pt\vrule width 8pt height 8pt depth 1.5pt\hskip 1pt}} \def\qed{\quad\blackslug\lower 8.5pt\null\par} \def\qqed{$\Box$} \newcommand{\dist}{{\rm dist}} \newcommand{\A}{{\cal A}} \newcommand{\F}{{\cal F}} \newcommand{\U}{{\cal U}} \newcommand{\B}{{\cal B}} \renewcommand{\S}{{\cal S}} \newcommand{\D}{{\cal D}} \newcommand{\R}{{\sf R}} \newcommand{\N}{{\sf N}} \newcommand{\Z}{{\sf Z}} \newcommand{\vol}{{\rm vol}} \newcommand{\prob}{{\rm Pr}} \newcommand{\poly}{{\rm poly}} \newcommand{\union}{{\cup}} \newcommand{\GapCVP}{{\tt GapCVP}} \newcommand{\GapSVP}{{\tt GapSVP}} \newcommand{\NP}{{\cal NP}} \renewcommand{\P}{{\cal P}} \newcommand{\qP}{{\widetilde\P}} \newcommand{\coNP}{{\rm co}{\cal NP}} \newcommand{\AM}{{\cal AM}} \newcommand{\BPP}{{\cal BPP}} \newcommand{\coAM}{{\rm co}{\cal AM}} \newcommand{\yes}{{\sc yes}} \newcommand{\no}{{\sc no}} \newtheorem{prot}{Protocol} % A counter for Protocols \newcommand{\BPR}{\begin{prot}} \newcommand{\EPR}{\end{prot}} \newtheorem{construct}{Construction} % A counter for Protocols \newcommand{\BCT}{\begin{construct}} \newcommand{\ECT}{\end{construct}} \newenvironment{proof}{\noindent{\bf Proof:~~}}{\qed} \newcommand{\BPF}{\begin{proof}} \newcommand {\EPF}{\end{proof}} \newenvironment{proofsketch}{\noindent{\bf Proof Sketch:~~}}{\qed} \newcommand{\BPFS}{\begin{proofsketch}} \newcommand {\EPFS}{\end{proofsketch}} \newcommand{\remove}[1]{} \newcommand{\RK}{{\sf RKZK}} \newcommand{\POK}{{\sf POK}} \newcommand{\BZK}{{\sf BZK}} \newcommand{\ideal}{\mbox{\sc ideal}} \newcommand{\real}{\mbox{\sc real}} \newcommand{\zkhybrid}{\mbox{\sc zk-hybrid}} %\newcommand{\memberzk}{\mbox{{\footnotesize\sc member}{\sc zk-hybrid}}} \newcommand{\memberzk}{\mbox{\sc memberzk-hybrid}} \newcommand{\tpi}{\tilde \Pi} \newcommand{\ta}{\tilde \A} \newcommand{\hpi}{\hat \Pi} \newcommand{\ha}{\hat \A} \newcommand{\adv}{{\sf adv}} \begin{document} \begin{titlepage} \maketitle \begin{abstract} Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of {\em bounded-concurrent self-composition}, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that {\em any}\/ two-party functionality can be securely computed under bounded-concurrent self-composition, in the {\sf plain model} (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, {\em for any model of concurrency}. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. Subsequent to this work, constant-round protocols and protocols for the multiparty case were presented by Pass and Rosen (FOCS 2003) and by Pass (STOC 2004). We remark that this paper contains the full version of the upper-bound portion of the extended abstract presented by the author at STOC 2003 \cite{L03b} (the lower bound from \cite{L03b} appears in \cite{L06} together with other lower bounds from \cite{L04a}). \end{abstract} \vfill \paragraph{Keywords:} secure two-party computation, concurrent self-composition, setup assumptions. \thispagestyle{empty} \end{titlepage} \section{Introduction} \ni In the setting of two-party computation, two parties with respective private inputs $x$ and $y$, wish to jointly compute a functionality $f(x,y) = (f_1(x,y),f_2(x,y))$, such that the first party receives $f_1(x,y)$ and the second party receives $f_2(x,y)$. This functionality may be probabilistic, in which case $f(x,y)$ is a random variable. Loosely speaking, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). These security requirements must hold in the face of a malicious adversary who controls one of the parties and can arbitrarily deviate from the protocol instructions (i.e., in this work we consider static adversaries). Powerful feasibility results have been shown for this problem, demonstrating that {\em any}\/ two-party probabilistic polynomial-time functionality can be securely computed, assuming the existence of trapdoor permutations~\cite{Y,GMW2}. \paragraph{Security under concurrent composition.} The above-described feasibility results relate only to the stand-alone setting, where a single pair of parties run a single execution. A more general (and realistic) setting relates to the case that many protocol executions are run concurrently within a network. Unfortunately, the security of a protocol in the stand-alone setting does not necessarily imply its security under concurrent composition. Therefore, an important research goal is to re-establish the feasibility results of the stand-alone setting for the setting of concurrent composition. We stress that the need for security under concurrent composition is not merely an issue of efficiency. Specifically, one cannot claim that in order to ensure security, all executions should just be carried out sequentially (recall that security under sequential composition is guaranteed by the stand-alone definitions~\cite{C00}). This is because the honest parties must actively coordinate their executions in order to ensure sequentiality. However, the honest parties may not even know of each other's existence. Therefore, they cannot coordinate their executions, and a dishonest adversary that interacts with a number of parties can schedule the executions concurrently. The protocol being used must therefore be secure under concurrent composition. The study of concurrent composition of protocols was initiated by~\cite{FS90} in the context of witness indistinguishability, and was next considered by~\cite{DDN} in the context of non-malleability. The majority of the work that followed on concurrent composition was for the problem of concurrent zero-knowledge~\cite{DNS}. In this scenario, a prover runs many copies of a protocol with many verifiers, and zero-knowledge must be preserved. The feasibility of concurrent zero-knowledge in the {\em plain model}\/ (where no trusted setup or preprocessing phase is assumed) was first demonstrated by~\cite{RK}. In general, the issue of concurrent zero-knowledge has received much attention, resulting in a rather exact understanding of the round-complexity of black-box concurrent zero-knowledge~\cite{KPR,R00,CKPR,KP,PRS}. Other specific problems that have been studied in the context of concurrent composition are oblivious transfer~\cite{GM} and authenticated Byzantine agreement~\cite{LLR}. In all of the above-mentioned work, the setting that is considered is that of {\sf concurrent self-composition}, where a {\em single}\/ protocol is run concurrently any polynomial number of times in a network (we stress, that the secure protocol in question is the only protocol being executed). Furthermore, all the executions are run by the same set of parties, and each party plays the same role throughout all of these executions (e.g., for zero knowledge, one party always plays the prover and the other party always plays the verifier).% \footnote{Actually, such a setting should be called {\sf concurrent self-composition with a single set of parties}. See~\cite{L03d} for a full taxonomy of types of protocol composition. \label{foot1}} % A different notion, called {\sf general composition}, considers a very broad setting where many sets of (possibly different) parties run many protocols, and secure protocols may run concurrently with arbitrary other protocols.% \footnote{According to the taxonomy of~\cite{L03d}, this should actually be called {\sf concurrent general composition with arbitrary sets of parties}.} % Such a setting realistically models the security needs of modern networks like the Internet, where many different arbitrary protocols are executed by many different sets of parties (with possibly related inputs). The first definition and composition theorem for concurrent general composition was presented by~\cite{PW00} who considered the case that a secure protocol is executed {\em once}\/ concurrently with another arbitrary protocol.% \footnote{An earlier reference to this problem with general ideas about how to define security appeared in~\cite[Appendix A]{C97}.} % The unbounded case, where a secure protocol can be run any polynomial number of times in an arbitrary network, was then considered by the framework of universal composability~\cite{C01}. Loosely speaking, universal composability is a specific security definition with the important property that any protocol that is proven secure under this definition is guaranteed to remain secure under (unbounded) concurrent general composition. Due to the robust security guarantees that are provided, universally composable protocols are highly desirable. Fortunately, such protocols exist. In fact, it has been shown that assuming an honest majority, {\em any}\/ multi-party functionality can be securely computed in a universally composable way~\cite{C01}. Furthermore, in the {\em common reference string model}, any two-party or multi-party functionality can be computed under this definition, for {\em any}\/ number of corrupted parties. (In the common reference string model, all parties are given access to a string that is ideally chosen from some predetermined distribution.) On the negative side, in the plain model and without an honest majority (as in the two-party case), there exist large classes of functionalities that cannot be securely computed according to the definitions of universal composability~\cite{CF,C01,CKL}. Note that these impossibility results relate specifically to the definition of universal composability and not necessarily to the possibility of obtaining protocols that are secure under concurrent general composition by some other definition. Nevertheless, impossibility results have also been demonstrated for any definition achieving concurrent {\em general}\/ composition~\cite{L03c}, and even for concurrent {\em self}\/ composition~\cite{L04a}, where impossibility holds in the plain model and in the case of no honest majority. (We note that the classes of functionalities that cannot be securely computed are not exactly the same for all these impossibility results. However, large classes of functionalities are ruled out in each case.) \paragraph{Bounded versus unbounded concurrency.} As we have described above, broad impossibility results exist for both concurrent general and self-composition. However, the impossibility results in~\cite{L04a} for concurrent self-composition rely inherently on the fact that the secure protocol in question can be run concurrently {\em any}\/ polynomial number times; this property is called {\sf unbounded concurrency}. In contrast, a more limited model of concurrency, first considered by~\cite{B}, restricts the number of concurrent executions to be some fixed, predetermined polynomial in the security parameter. Furthermore, the protocol design can depend on this number (i.e., if the bound is $n^2$, then the protocol can be designed so that it is secure for at most $n^2$ concurrent executions, and no more). This model is called {\sf bounded concurrency}, and when $m$ is the maximum number of concurrent executions, we talk about {\sf $m$-bounded concurrent composition} (note that $m=m(n)$ is a fixed polynomial in the security parameter). Importantly, the possibility of obtaining protocols that are secure under $m$-bounded concurrent self composition was not ruled out in~\cite{L04a}. \paragraph{The model of concurrency.} Before proceeding to describe our results, we describe the model of concurrency considered here in more detail. In this work, we consider self-composition of two-party protocols, where a single pair of parties run the same protocol many times concurrently. This is actually equivalent to the case where many different pairs of parties run a protocol concurrently, with the following adversarial limitation. Each party is designated to be either a first party $P_1$ or a second party $P_2$ (this defines the role that it plays in the protocol execution). The adversary is then only allowed to corrupt a subset of the parties playing $P_1$ or a subset of the parties playing $P_2$, but cannot simultaneously corrupt parties playing $P_1$ and parties playing $P_2$. Such a scenario can model some real-world scenarios, like a number of servers concurrently interacting with many clients (and where we assume that there is no simultaneous corruption of a server and a client). As we have mentioned above, this is the exact model considered in the entire body of work on concurrent zero-knowledge. Note that this is a rather limited model, both because self-composition (rather than general composition) is considered, and because only a single set of parties is considered (equivalently, the adversary is severely limited in its corruption capability). However, we stress that no general feasibility results have been shown for {\em any}\/ model of concurrency, without assuming some trusted setup phase (beyond that required for authenticated channels) or an honest majority. This therefore serves as a good first step. In addition, studying more limited models deepens our understanding of exactly where the line between feasibility and infeasibility lies, thus providing an ``explanation'' of sorts as to the source of the impossibility results for concurrent composition. (We note that the fact that we consider self, rather than general, composition is also very limiting. However, this is essential due to the impossibility results of~\cite{L03c} that hold even when the secure protocol is executed only once in the setting of concurrent general composition.) \paragraph{Our results.} In this work, we show that any two-party functionality can be securely computed under bounded-concurrent self-composition and in the plain model. More specifically, we prove the following theorem: \BIT Assume that enhanced trapdoor permutations% \footnote{Enhanced trapdoor permutations have the property that a random element generated by the domain sampler is hard to invert, even given the random coins used by the sampler; see~\cite[Appendix C]{GoldreichBook2}. We note that the construction of~\cite{GMW2} for secure two-party computation in the stand-alone model also assumes the existence of enhanced trapdoor permutations.} % and collision resistant hash functions exist. Then, for any probabilistic polynomial-time two-party functionality $f$ and for any $m$, there exists a protocol\, $\Pi$ that securely computes $f$ under $m$-bounded concurrent composition in the plain model. \label{thm:informal-upper} \EIT \ni We now provide a very brief and informal outline of the proof of the theorem. We begin by observing that secure two-party computation that composes concurrently can be obtained in a hybrid model where the parties have (concurrent) access to a trusted party computing the ideal zero-knowledge functionality. This was formally demonstrated in~\cite{CLOS}. Given this observation, the question is whether or not one can transform protocols that use this ideal zero-knowledge functionality into protocols that run in the real model (without any trusted help). Of course, this transformation must preserve the concurrent composition, or bounded-concurrent composition, of the protocol. A naive implementation of the above idea is to replace the ideal zero-knowledge calls with any concurrent zero-knowledge protocol. However, two problems arise with this idea. First, as we have mentioned, concurrent zero-knowledge considers a scenario where the protocol is run concurrently with itself only. Thus, it is not clear that the zero-knowledge simulation can be accomplished if the protocol is run concurrently to other protocols as well. Second, a problem relating to the malleability of protocols arises. That is, during the concurrent executions, the adversary may simultaneously verify and prove zero-knowledge proofs. Thus, it can execute a man-in-the-middle attack on the zero-knowledge proofs. This is a problem because when some of the zero-knowledge protocols are simulated, we are no longer guaranteed that the protocol proven by the adversary remain sound. In particular, the adversary may be able to prove false statements in this setting, and this would cause the simulation of the secure protocol to fail. This second problem is solved by having the parties use fundamentally different zero-knowledge proofs.% \footnote{We note that the recent result of~\cite{B02} for ``non-malleable coin-tossing'' does not solve this problem. This is because \cite{B02} relies on a very specific scheduling which can be enforced in their scenario, but cannot be enforced here.} % Specifically, one party proves statements with the black-box zero-knowledge protocol of~\cite{RK}, while the other party proves statements with the non black-box zero-knowledge protocol of~\cite{B,BG}. It turns out that a careful choice of parameters for these protocols solves the problem of malleability. However, the first problem (of concurrency with other protocols) still remains. This is solved as follows. The protocol of~\cite{B} can easily be modified so that it remains zero-knowledge when run concurrently with other protocols (intuitively, this is the case because there is no rewinding). However, the protocol of~\cite{RK} is more problematic. We therefore devise a {\em new}\/ black-box simulation strategy for~\cite{RK} in the setting of $m$-bounded concurrency, that enables it to be used directly as a sub-protocol of another protocol. Having solved these problems, we are able to replace the ideal zero-knowledge calls in any protocol with the specific $m$-bounded concurrent zero-knowledge protocols described above. Putting this transformation together with a protocol that is secure when given access to the ideal zero-knowledge functionality, we obtain a protocol that is secure under $m$-bounded concurrent composition in the real model. The number of rounds of communication in our protocol is $O(m\cdot\kappa(n))$, where $n$ is the security parameter and $\kappa(\cdot)$ is any super-constant function (e.g., $\kappa(n)=\log\log n$). We note that a lower bound of $m$ rounds for protocols that are proven using only black-box simulation has been proven in~\cite{L03b}. Nevertheless, our protocol is proven using both black-box and non black-box techniques (and is thus not a ``tight'' upper-bound). We conclude with a remark about {\em efficiency}. Our protocol requires $O(m\kappa(n))$ rounds to obtain security for $m$ concurrent executions. It is therefore far from being ``reasonably efficient''. Nevertheless, the focus of this paper is {\em not}\/ efficiency. Rather, we believe that establishing the feasibility of obtaining secure computation in any reasonable model of concurrency is of great importance, irrespective of efficiency. Furthermore, our constructions may lead to more efficient protocols (see below in subsequent work). \paragraph{Discussion: setup assumptions and authenticated channels.} The {\sf plain model} classically refers to a scenario where the honest parties communicate via authenticated channels, but no additional setup is assumed. In most works, the assumption on the existence of authenticated channels is not articulated as a ``setup assumption'', but rather as part of the network model. However, in reality, some sort of setup assumption is also required for achieving authenticated channels. We argue that this assumption should be explicitly treated as such. We note that despite the fact that authenticated channels {\em is}\/ a setup assumption, it is a strictly weaker one than that required for obtaining a common reference string, for example. Specifically, in order to achieve authenticated channels, it suffices to have a certificate authority who reliably posts keys on a bulletin board~\cite{C04}. (We stress that there is no need for the certificate authority to run any protocol with the parties posting keys and, in particular, proofs of knowledge are not necessary.) Furthermore, upon inspection of the lower bounds for concurrent self-composition of~\cite{L04a}, it is easy to see that they extend to a model where such a ``secure bulletin board'' exists. Thus, a common reference string cannot be generated from the same assumption used for authenticated channels (or else the lower bounds of~\cite{L04a} would not hold). \paragraph{Subsequent and related work.} Subsequent to this work, a {\em constant-round}\/ protocol for bounded-concurrent secure two-party computation was presented in~\cite{PR}. This result was later improved and extended in~\cite{P04} to provide a protocol that {\bf (a)} works for multiparty functionalities, and {\bf (b)} can be extended to the general setting where arbitrary sets of parties run the protocol (and any subset of parties may be corrupted). The high-level framework developed in this paper has been adopted in this subsequent work of~\cite{PR,P04}, which makes use of the following observations made here in our work: \BE \item The problem of general secure computation in the setting of concurrent self-composition can be reduced to a zero-knowledge proof of membership functionality (rather than a seemingly more stringent zero-knowledge proof of knowledge functionality). \item The bounded-concurrent zero-knowledge protocol of~\cite{B,BG} remains secure irrespective of the other protocols being run in the network (as long as the communication complexity is appropriately bounded). \item The problem of malleability (and man-in-the-middle attacks) in general secure computation under concurrent self-composition can be solved more easily by having the different parties run different zero-knowledge protocols. \EE Specifically, the works of~\cite{PR,P04} focus on constructing improved versions of the zero-knowledge proof of membership functionality used here. Instead of using two completely different zero-knowledge protocols as we do (something which turns out to be a great limitation), these latter works show how variants of the zero-knowledge protocol of~\cite{B,BG} can be used by all parties involved, while setting the parameters differently for every participating party so that man-in-the-middle attacks are prevented. This solves both the problem of large round complexity (because the protocol of~\cite{B,BG} has only a constant number of rounds) and the limitation to two parties (because it is possible to have many parties, each with a different setting of the parameters). The latter work of~\cite{P04} (that builds also on~\cite{PR}) achieves the best one could hope for in the setting of bounded concurrency -- constant round complexity and multiparty computation. We conclude by noting that both our protocol and the protocols of~\cite{PR} and~\cite{P04} suffer from very high communication complexity in bandwidth. Specifically, for $m$ concurrent executions, the bandwidth of the protocols are at least $\Omega(mn^2)$, where $n$ is the security parameter. We note that a linear dependence of the bandwidth on $m$ is actually inherent. That is, it has been shown that there exist many functionalities such that any protocol that securely computes these functionalities under $m$-bounded concurrent self-composition must have communication complexity of at least~$m$~\cite{L04a}. %\paragraph{Open questions.} Our protocol (and the protocol %of~\cite{PR}) only solve the problem of {\em two}-party %computation. It is not known how to achieve {\em multi}-party %secure computation for the setting of bounded concurrent self %composition. In addition, our protocol only works for the case %that each party plays the same role in each execution. Thus it %cannot be used in a network where different pairs of parties run %the protocol, and any individual party may sometimes play the role %of party~1 and sometimes the role of party~2. (In the taxonomy %of~\cite{L03d}, this would be called bounded concurrent self %composition with {\em arbitrary sets of parties}.) In this %context, it would also be interesting to consider the case of %adaptive corruptions (we only consider static corruptions here). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Definitions: \boldmath{$m$}-Bounded Concurrent Secure Computation\label{sec:secure-comp}} \ni In this section we present the definition for $m$-bounded concurrent secure two-party computation. The basic description and definition of secure computation follows~\cite{GoLe,MR,Be1,C00}. We denote computational indistinguishability by $\indist$, and the security parameter (and, for simplicity, the lengths of the parties' inputs) by $n$. All parties and the adversary run in time that is polynomial in $n$. \paragraph{Two-party computation.} A two-party protocol problem is cast by specifying a random process that maps pairs of inputs to pairs of outputs (one for each party). We refer to such a process as a {\sf functionality} and denote it $f:\bitset^*\times\bitset^*\to\bitset^*\times\bitset^*$, where $f = (f_1,f_2)$. That is, for every pair of inputs $(x,y)$, the output-pair is a random variable $(f_1(x,y),f_2(x,y))$ ranging over pairs of strings. The first party (with input $x$) wishes to obtain $f_1(x,y)$ and the second party (with input $y$) wishes to obtain $f_2(x,y)$. We often denote such a functionality by $(x,y) \mapsto (f_1(x,y),f_2(x,y))$. Thus, for example, the zero-knowledge proof of knowledge functionality for a relation $R$, is denoted by $((x,w),x) \mapsto (\lambda,R(x,w))$. In the context of concurrent composition, each party actually receives a vector of inputs of polynomial length, and the aim of the parties is to jointly compute $f(x_i,y_i)$ for every $i$. (According to this description, all the honest party's inputs are fixed at the onset. However, our protocols are also secure when the honest party's inputs may be chosen adaptively throughout the execution. This will be discussed later.) The fact that $m$-bounded concurrency is considered relates to the allowed scheduling of messages by the adversary in the protocol executions; see the description of the real model below. We note that our results here also apply to {\em reactive functionalities}\/ where inputs and outputs are supplied over a number of stages. Such a functionality can be modeled by a probabilistic polynomial-time interactive machine who receives inputs and supplies outputs. This machine can keep state and thus the inputs from previous computations can influence the outputs of later ones. \paragraph{Adversarial behaviour.} In this work we consider a malicious, static adversary. That is, the adversary controls one of the parties (who is called corrupted) and may then interact with the honest party while arbitrarily deviating from the specified protocol.% \footnote{We follow the approach of~\cite{GoldreichBook2} by defining the two-party case as one where the adversary controls exactly one of the parties. This is in contrast to a more general approach in which the adversary may control zero, one or both parties. This approach somewhat simplifies the presentation, without weakening the results. Specifically, assuming {\em authenticated channels}, any protocol that is secure when exactly one party is corrupted can be transformed into a protocol that is secure when any number (i.e., 0, 1 or 2) of the parties are corrupted, in the following way. First, using the given authenticated channels, the two parties establish secure channels for private and reliable communication. Next, the original protocol is executed over this private channel. It follows that if no parties are corrupted, then the adversary learns nothing (except for the length of the messages and so the length of the inputs). Furthermore, if one party is corrupted, then the effect is exactly the same as for the original protocol, where security is guaranteed. Finally, the case of both parties corrupted is always straightforward. We conclude that the resulting protocol is secure in the more general case, as required.} % The focus of this work is not on fairness. We therefore present a definition where the adversary always receives its own output and can then decide when (if at all) the honest party will receive its output. The scheduling of message delivery is decided by the adversary. \paragraph{Security of protocols (informal).} The security of a protocol is analyzed by comparing what an adversary can do in the protocol to what it can do in an ideal scenario that is trivially secure. This is formalized by considering an {\em ideal}\/ computation involving an incorruptible {\em trusted third party}\/ to whom the parties send their inputs. The trusted party computes the functionality on the inputs and returns to each party its respective output. Unlike in the case of stand-alone computation, here the trusted party computes the functionality many times, each time upon different inputs. Loosely speaking, a protocol is secure if any adversary interacting in the real protocol (where no trusted third party exists) can do no more harm than if it was involved in the above-described ideal computation. %\paragraph{\boldmath{$m$}-bounded execution in the ideal model.} \paragraph{Concurrent execution in the ideal model.} Let $p(n)$ be a polynomial in the security parameter. Then, an ideal execution with an adversary who controls either $P_1$ or $P_2$ proceeds as follows: \begin{description} \item[\em Inputs:] The honest party and adversary each obtain a vector of $p(n)$ inputs each of length $n$; denote this vector by $\ov w$ (i.e., $\ov w=\ov x$ or $\ov w=\ov y$). \item[\em Honest party sends inputs to trusted party:] The honest party sends its entire input vector $\ov w$ to the trusted party. \item[\em Adversary interacts with trusted party:] For every $i=1,\ldots,p(n)$, the adversary can send $(i,w_i')$ to the trusted party, for any $w_i'\in\bitset^n$ of its choice. Upon sending this pair, it receives back its output based on $w_i'$ and the input sent by the honest party. (That is, if $P_1$ is corrupted, then the adversary receives $f_1(w_i',y_i)$ and if $P_2$ is corrupted then it receives $f_2(x_i,w_i')$.) The adversary can send the $(i,w_i')$ pairs in any order it wishes and can also send them {\em adaptively}\/ (i.e., choosing inputs based on previous outputs). The only limitation is that for any $i$, {\em at most one pair}\/ indexed by $i$ can be sent to the trusted party.% \footnote{The fact that the adversary can query the trusted party once for each execution is essential for obtaining meaningful security. Otherwise, the adversary (controlling $P_2$) could obtain a series of values $f_2(x,y),f_2(x,y'),f_2(x,y''),\ldots$ for a single input value $x$ belonging to the honest party. Furthermore, it may choose $y,y',y''$ etc.\ adaptively based on previous outputs. This may reveal much more information than intended. For example, if $f$ is the ``less than'' function, then the adversary could conduct a binary search on the input range and find the exact value of $x$.} % \item[\em Trusted party answers honest party:] Having received all of its own outputs, the adversary specifies which outputs the honest party receives. That is, the adversary sends the trusted party a set $I\subseteq\{1,\ldots,p(n)\}$. Then, the trusted party supplies the honest party with a vector $\ov v$ of length $p(n)$ such that for every $i\not\in I$, $v_i=\bot$ and for every $i\in I$, $v_i$ is the party's output from the $i^\th$ execution. (That is, if $P_1$ is honest, then for every $i\in I$, $v_i=f_1(x_i,w_i')$ and if $P_2$ is honest, then $v_i=f_2(w'_i,y_i)$ .) \item[\em Outputs:] The honest party always outputs the vector $\ov v$ that it obtained from the trusted party. The adversary may output an arbitrary (probabilistic polynomial-time computable) function of its initial input and the messages obtained from the trusted party. \end{description} Let $f:\bitset^*\times\bitset^*\mapsto\bitset^*\times\bitset^*$ be a functionality, where $f = (f_1,f_2)$, and let $\S$ be a non-uniform probabilistic polynomial-time machine (representing the ideal-model adversary). Then, the {\sf ideal execution of $f$} (on input vectors $(\ov x,\ov y)$ of length $p(n)$ and auxiliary input $z$ to $\S$), denoted $\ideal_{f,\S}(\ov x,\ov y,z)$, is defined as the output pair of the honest party and $\S$ from the above ideal execution. We note that the definition of the ideal model does not include any reference to the bound $m$ on the concurrency. This is because this bound is relevant only to the scheduling allowed to the adversary in the real model; see below. However, the fact that a concurrent setting is considered can be seen from the above-described interaction of the adversary with the trusted party. Specifically, the adversary is allowed to obtain outputs in any order that it wishes, and can choose its inputs adaptively based on previous outputs. This is inevitable in a concurrent setting where the adversary can schedule the order in which all protocol executions take place. \paragraph{Execution in the real model.} We next consider the real model in which a real two-party protocol is executed (and there exists no trusted third party). Let $p(n)$ and $m=m(n)$ be polynomials, let $f$ be as above and let $\Pi$ be a two-party protocol for computing $f$. Furthermore, let $\A$ be a non-uniform probabilistic polynomial-time machine that controls either $P_1$ or $P_2$. Then, the {\sf real $m$-bounded concurrent execution of $\Pi$} (on input vectors $(\ov x,\ov y)$ of length $p(n)$ and auxiliary input $z$ to $\A$), denoted $\real^m_{\Pi,\A}(\ov x,\ov y,z)$, is defined as the output pair of the honest party and $\A$, resulting from $p(n)$ executions of the protocol interaction, where the honest party always inputs its $i^\th$ input into the $i^\th$ execution. The scheduling of all messages throughout the executions is controlled by the adversary. That is, the execution proceeds as follows. The adversary sends a message of the form $(i,\alpha)$ to the honest party. The honest party then adds $\alpha$ to the view of its $i^\th$ execution of $\Pi$ and replies according to the instructions of $\Pi$ and this view.% \footnote{Notice that the honest party runs each execution of $\Pi$ obliviously to the other executions. Thus, this is stateless composition.} % The adversary continues by sending another message $(j,\beta)$, and so on. When {\sf unbounded concurrency} is considered, {\em any}\/ scheduling of the messages by the adversary is allowed. In contrast, in the setting of {\sf $m$-bounded concurrency}, the scheduling by the adversary must fulfill the following condition: for every execution $i$, from the time that the $i^\th$ execution begins until the time that it ends, messages from at most $m$ different executions can be sent. (Formally, view the schedule as the ordered series of messages of the form $({\sf index,message})$ that are sent by the adversary. Then, in the interval between the beginning and termination of any given execution, the number of different indices viewed can be at most $m$.) We note that this definition of concurrency covers the case that $m$ executions are run simultaneously. However, it also includes a more general case where many more than $m$ executions take place, but each execution overlaps with at most $m$ other executions. \paragraph{Security as emulation of a real execution in the ideal model.} Having defined the ideal and real models, we can now define security of protocols. Loosely speaking, the definition asserts that a secure two-party protocol (in the real model) emulates the ideal model (in which a trusted party exists). This is formulated by saying that for every real-model adversary there exists an ideal model adversary that can simulate an execution of the secure real-model protocol. \BD{\em($m$-bounded concurrent secure computation):} \label{def:conc-security} Let $m=m(n)$ be a polynomial and let $f$ and $\Pi$ be as above. Protocol\, $\Pi$ is said to {\sf securely compute $f$ under $m$-bounded concurrent composition} if for every real-model non-uniform probabilistic polynomial-time adversary $\A$ controlling party $P_i$ for $i\in\{1,2\}$, there exists an ideal-model non-uniform probabilistic polynomial-time adversary $\S$ controlling $P_i$, such that for every polynomial $p(n)$, $$\left\{\vphantom{2^{2^2}}\ideal_{f,\S}(\ov x,\ov y,z)\right\} _{n\in\N;\ov x,\ov y\in(\bitset^n)^{p(n)};z\in\bitset^*} \stackrel{\rm c}{\equiv} \left\{\vphantom{2^{2^2}}\real^m_{\Pi,\A}(\ov x,\ov y,z)\right\} _{n\in\N;\ov x,\ov y\in(\bitset^n)^{p(n)};z\in\bitset^*} $$ \ED %Definition~\ref{def:conc-security} follows a liberal %interpretation of ``efficient simulation'' in that it allows the %ideal-model simulator/adversary to run in {\em expected}\/ %polynomial-time. Formally, an interactive machine $M_1$ is {\sf %expected polynomial-time} if there exists a (single) polynomial %$q(\cdot)$ such that for {\em every}\/ (possibly unbounded) %machine $M_2$, the expected running time of $M_1$ (upon input of %length $n$) when interacting with $M_2$ is bounded by $q(n)$. \paragraph{Remark -- adaptively chosen inputs.} Definition~\ref{def:conc-security} is overly simplistic and limited in that it assumes that the honest party's inputs are fixed before any execution begins. However, our protocol also works for a more general definition where inputs for later executions can depend on outputs of earlier executions; see~\cite{L04a} for such a definition. We present this simpler definition for the sake of clarity and because the issue of adaptively chosen inputs versus a-priori fixed inputs actually has no effect on our construction. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Tools for our Protocol -- Zero-Knowledge} In this section, we develop the basic tools needed for proving Theorem~\ref{thm:informal-upper}. As we have described in the Introduction, this involves the construction of zero-knowledge proofs that can be used as subprotocols within any other protocol, in the setting of bounded concurrency. We use the standard definitions for zero-knowledge and proofs of knowledge, see~\cite{oded-book}, and assume familiarity with these notions. \subsection{The Zero-Knowledge Arguments of Knowledge of \protect\cite{BL}} \label{sec:zkpok} The zero-knowledge arguments of knowledge of \cite{BL} have the interesting property that {\em both}\/ simulation and extraction take place by simulating zero-knowledge proofs (that are used as subprotocols). That is, the argument system is such that both the prover and verifier prove zero-knowledge proofs of membership during the protocol.% \footnote{In a {\em proof of membership}, the verifier is convinced that a certain statement is correct. However, in a {\em proof of knowledge}, the verifier is also convinced that the prover actually holds a witness for this statement.} % Then, the simulator strategy essentially just involves the simulation of the subproof given by the prover to the verifier. Likewise, the extraction strategy essentially just involves the simulation of the subproof given by the verifier to the prover. This is helpful because we can focus on the one issue of simulating zero-knowledge within our setting, and we obtain both zero-knowledge simulation {\em and}\/ knowledge extraction. The remainder of this section describes how this is achieved. \paragraph{Commit-with-extract commitment schemes.} A central tool in the construction of the zero-knowledge arguments of knowledge of~\cite{BL} is a perfectly-binding commitment scheme with the following {\em extraction}\/ property: for every committer, there exists a commitment {\em extractor}\/ who is able to extract the value being committed to by the committer. As we will see below, the extractor for the commit-with-extract scheme of~\cite{BL} works by simulating a zero-knowledge proof of membership. We begin by describing how such a commitment scheme helps in obtaining zero-knowledge arguments of knowledge: \paragraph{Zero-knowledge arguments of knowledge using commit-with-extract.} Given a commit-with-extract commitment scheme, a zero-knowledge argument of knowledge can be constructed as follows. The prover commits to a witness using the commit-with-extract scheme, and then proves that it committed to a valid witness using a zero-knowledge proof of membership. Intuitively, a knowledge extractor for the argument of knowledge simply uses the extractor of the commit-with-extract scheme. By the soundness of the proof of membership provided by the prover in the second stage of the argument of knowledge, we are guaranteed that the value obtained will be a correct witness with probability only negligibly less than the probability that the verifier accepts the proof. A simulator for this protocol is also easily obtained: just commit to garbage in the commit-with-extract scheme and then simulate the proof of membership in the second stage. See~\cite{BL} for more details. The protocol description is as follows: \BPR \label{prot:zkpok} {\em (zero-knowledge argument of knowledge for $R \in \NP$):} \BI \item {\bf Common Input:} $x$ \item {\bf Auxiliary input to prover:} $w$ such that $(x,w) \in R$. \item {\bf Part~1: } $P$ and $V$ run a commit-with-extract protocol in which $P$ commits to the witness $w$. \item {\bf Part~2: } $P$ proves to $V$ that it committed to a valid witness $w$ in the previous step, using a zero-knowledge proof \(or argument\) of membership.% \footnote{Formally, let {\sf trans} be the transcript of the commit-with-extract execution of part~$1$, and let $d$\/ be the decommitment message that $P$ would use to decommit. Then, $P$ proves the NP-statement that there exists a value $d$\/ such that $({\sf trans},d)$ defines the value $w$, and $(x,w) \in R$.} % \EI \EPR \ni We note that \cite{BL} also demonstrate the existence of a {\sf witness-extended emulator} for Protocol~\ref{prot:zkpok}, as defined by~\cite{Lin}. Loosely speaking, a witness-extended emulator is a machine that not only outputs a witness with the required probability (as is required from a knowledge extractor), but also outputs a simulated transcript of the interaction between the prover and the verifier. Furthermore, whenever the transcript of the interaction is such that the verifier accepts, then the witness that is obtained is valid. To explain this further, consider a case that the prover convinces the verifier in a real interaction with probability $p$. Then, with probability negligibly close to $p$, the above-described machine should output an accepting transcript and a valid witness. Furthermore, with probability negligibly close to $1-p$, the machine should output a rejecting transcript (and we don't care about the witness). We note that the transcript that is obtained is also {\em publicly verifiable}, meaning that the verifier's accept or reject decision can be efficiently obtained from the transcript. Witness-extended emulation is often needed when a proof of knowledge is used as a {\em subprotocol}\/ within a larger protocol; as is the case for our constructions. See~\cite{BL} for more discussion on witness-extended emulation. \paragraph{The commit-with-extract scheme of \protect\cite{BL}.} The scheme is based on the following non-interactive commitment scheme that uses one-way permutations: Let $f$ be a one-way permutation and let $b$ be a hard-core predicate of $f$. Then, in order to commit to a bit $\sigma$, the committer chooses $r\rnd\bitset^n$, lets $y=f(r)$ and sends $\langle y,v\rangle$ to the receiver, where $v=b(r) \oplus \sigma$. Loosely speaking, the commit-with-extract scheme is defined in the same way except that the value $y=f(r)$ is chosen jointly by the committer and the receiver using a coin-tossing protocol. By the security of the coin-tossing protocol, $y$ is pseudorandom. Therefore, the hiding property remains essentially the same as in the original scheme. Likewise, because $f$ is a permutation, any $y$ defines a unique value $b(f^{-1}(y))=b(r)$ and thus the scheme remains perfectly binding (i.e., given any pair $(y,v)$, the committed value is uniquely defined by $v\oplus b(f^{-1}(y))$). The novelty of the scheme is that the extractor can {\em bias}\/ the outcome of the coin-tossing protocol so that it knows the preimage $f^{-1}(y)$ of $y$. In this case, the extractor can easily obtain the commitment value $\sigma$, as desired. We now describe the protocol: \BPR {\em (commit-with-extract bit commitment scheme):} \BI \item {\bf Input:} The committer has a bit $\sigma$ to be committed to. \item {\bf Commit phase:} \BE \item {\sf The committer chooses an enhanced trapdoor permutation:}% \footnote{See~\cite[Appendix C]{GoldreichBook2} for the definition of {\em enhanced}\/ trapdoor permutations. For the sake of understanding the protocol here, it suffices to think of the case that the domain of the permutation is $\bitset^n$.} The committer chooses an enhanced trapdoor permutation $f$ along with its trapdoor $t$ and sends $f$ to the receiver.% \footnote{For the sake of simplicity, we assume that the protocol uses {\em certified}\/ \cite{FLS} enhanced trapdoor permutations (for which the receiver can efficiently verify that $f$ is indeed a permutation). However, actually any enhanced trapdoor permutation can be used; see~\cite{BL}.} % \item {\sf The parties run a coin-tossing protocol:} \BE \item \label{step1} The receiver chooses a random string $r_1 \rnd \bitset^n$ and sends $c = {\sf Commit}(r_1;s)$ to the committer {\em (}using any perfectly-binding commitment scheme $\sf Commit$ and a random string $s${\em )}. \item The committer chooses a random string $r_2 \rnd \bitset^n$ and sends $r_2$ to the receiver. \item The receiver sends $r_1$ to the committer {\em (}without decommitting{\em )}. \item \label{step2} The receiver proves that $r_1$ is the value that it indeed committed to, using a zero-knowledge argument system. Formally, the receiver proves that there exists a string $s$ such that $c = {\sf Commit}(r_1;s)$. \item The output of the coin-tossing phase is $r_1 \oplus r_2$. \EE \item {\sf The actual commitment:} The committer computes $r= f^{-1}(r_1 \oplus r_2)$ and sends the value $v = b(r) \oplus \sigma$ to the receiver. \EE \medskip \item {\bf Reveal phase:} \BE \item The committer sends the receiver the string $r$. \item The receiver checks that $f(r) = r_1 \oplus r_2$. If this is the case, then it computes $b(r) \oplus v$ obtaining $\sigma$. Otherwise, it outputs $\bot$. \EE \EI \label{prot:commitextract} \EPR First note that if the coin-tossing protocol ensures that $r_1 \oplus r_2$ is pseudorandom, then the hiding property of the commitment scheme is preserved. This is because the receiver cannot predict $b(r)$ from a (pseudo-)randomly chosen $f(r)$ with probability greater than $1/2$. We remark that as long as the proof given by the receiver is {\em sound}, the security of the coin-tossing protocol holds. We conclude by briefly describing how a commitment extractor $CK$ can obtain the value $\sigma$ committed to by the committer. $CK$ works by biasing the outcome $r_1 \oplus r_2$ of the coin-tossing protocol, so that it knows the preimage under $f$. More specifically, $CK$ chooses a random string $r$, computes $f(r)$ and then makes the output $r_1 \oplus r_2$ equal $f(r)$. This is clearly not possible for a real receiver to do (as the coin-tossing protocol ensures that $f(r)$ is pseudorandom). However, $CK$ can run the {\em simulator}\/ for the proof that the receiver provides in step~\ref{step2} of the protocol. Thus, $CK$ sends a commitment to garbage in step~\ref{step1} of the protocol and waits to receive the string $r_2$ from the committer. Upon receiving $r_2$, extractor $CK$ computes $r_1 = f(r) \oplus r_2$ and sends $r_1$ to the committer (where $f(r)$ is obtained by choosing a random $r$ and applying $f$ to $r$). Now, with overwhelming probability, this is not the string that $CK$ committed to earlier. Thus $CK$ cannot honestly prove the proof of step~\ref{step2}. Instead, it runs the simulator for it (and by the hiding property of commitments, this looks indistinguishable from a real execution). The key point is that at the conclusion of the protocol, the committer defines $f(r) = r_1 \oplus r_2$ and sends $v=b(r) \oplus \sigma$. However, $CK$ knows the string $r$ and can therefore obtain $\sigma$ by computing $v \oplus b(r)$. Notice that the extraction strategy relies only on the ability to simulate the zero-knowledge proof of membership in step~\ref{step2}. See~\cite{BL} for a formal definition of commit-with-extract schemes and for a full proof of Protocol~\ref{prot:commitextract}. \paragraph{Summary.} Consider the system of zero-knowledge arguments of knowledge of Protocol~\ref{prot:zkpok} where the commit-with-extract scheme that is used is that of Protocol~\ref{prot:commitextract}. Then, it holds that the {\em simulation}\/ of the combined protocol works by simulating the zero-knowledge proof of membership of Part~2 that is provided by $P$. Furthermore, the {\em extraction}\/ strategy of the combined protocol works by simulating the zero-knowledge proof of membership of Part~1 that is provided by $V$. Actually, both the simulation and extraction strategies also involve other instructions, as described above. However, these instructions do not require any ``rewinding'' or involved simulation strategies; rather they can be generated using one-pass black-box simulation (specifically, these instructions can be generated independently of the internal simulation of the subproofs and based solely on the transcript of the other messages). Due to this fact, we have that if the zero-knowledge subproofs can be simulated under {\em concurrent composition}\/ (even with arbitrary other protocols), then both simulation and extraction of Protocol~\ref{prot:zkpok} can be carried out under {\em concurrent composition}\/ (even with arbitrary other protocols). This important property is summarized in the following informal lemma: \pagebreak \BL {\em (informal lemma):} Let $(P,V)$ be the protocol obtained by plugging the commit-with-extract scheme of Protocol~\ref{prot:commitextract} into Protocol~\ref{prot:zkpok}. Furthermore, assume that the subproofs of membership \(in Protocol~\ref{prot:commitextract} and in part~2 of Protocol~\ref{prot:zkpok}\) constitute zero-knowledge proof or argument systems with negligible soundness error, even when run concurrently with each other and arbitrary other protocols. Then, \BE \item $(P,V)$ is a zero-knowledge argument system, even when run concurrently with itself and arbitrary other protocols. \item $(P,V)$ is an argument of knowledge with negligible knowledge error, even when run concurrently with itself and arbitrary other protocols. Furthermore, there exists a witness-extended emulator for $(P,V)$ in this setting. \EE \label{lem:subproofs} \EL The proof of this lemma follows directly from the proofs that Protocol~\ref{prot:commitextract} is a commit-with-extract commitment scheme and that Protocol~\ref{prot:zkpok} is a system of zero-knowledge proofs of knowledge, as shown in~\cite{BL}. A formal version of Lemma~\ref{lem:subproofs} is stated and proved in the Appendix. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Black-Box Bounded Concurrent ZK} \label{sec:rk} In this section we describe the concurrent zero-knowledge protocol of Richardson and Kilian~\cite{RK}, with a certain setting of parameters relating to the number of rounds. It has been shown that the protocol of~\cite{RK} with a poly-logarithmic number of rounds is (unbounded) concurrent zero-knowledge \cite{KP}. In contrast, we extend the protocol to have $O(m\!\cdot\!\kappa(n))$ rounds, where $m$ is the maximum number of concurrent executions and $\kappa(\cdot)$ is any super-constant function; i.e., $\kappa(n)=\omega(1)$.% \footnote{Actually, we will assume that $\kappa(n)$ is at most polynomial in $n$; therefore, it cannot be {\em any}\/ super-constant function.} % We then show that this extended protocol is secure under $m$-bounded concurrent composition. Although this is a far weaker claim (i.e., requiring more rounds and achieving only bounded concurrency), the simulation strategies of~\cite{RK,KP} are problematic when the protocol is used as a module within another larger protocol (as will be the case here). We therefore increase the number of rounds and provide a {\em new}\/ simulation strategy that also succeeds when the protocol is plugged into another (larger) protocol. Before presenting the actual protocol of~\cite{RK}, we describe it on an informal level. The idea behind the protocol is to provide the simulator with many opportunities to rewind the verifier. This is achieved by having a preamble of many iterations, where rewinding in just one of the iterations suffices for simulating the entire proof. To demonstrate this idea, we consider the case that the preamble consists of just one iteration. Then, the protocol begins with the verifier sending a perfectly-hiding commitment to a random string $r\rnd\bitset^n$. Next, the prover sends a perfectly-binding commitment $c={\sf Commit}(0^n)$, after which the verifier decommits to $r$. (Note that ${\sf Commit}(0^n)$ is actually a randomized computation.) Finally, the prover proves a zero-knowledge (or witness-indistinguishable~\cite{FS90}) proof to the verifier that either the statement in question is true, or that its commitment $c$ equals ${\sf Commit}(r)$. Now, the honest prover will always prove that the statement in question is true. Furthermore, due to the fact that the verifier's commitment is perfectly-hiding, a cheating prover has no information on $r$ when it sends $c$ to the verifier. Therefore, except with negligible probability, it will not be the case that $c={\sf Commit}(r)$. Thus, if the verifier is convinced, the statement in question must be true (by reduction to the soundness of the zero-knowledge or witness-indistinguishable proof provided at the end). The fact that the proof is zero-knowledge can be seen as follows: The simulator is able to rewind the verifier after obtaining the decommitment value $r$. Then, it can continue the proof by providing a commitment $c$ such that indeed $c={\sf Commit}(r)$. In this case, the simulator can prove the proof at the end using the fact that its commitment is to $r$ and without having any witness to the fact that the statement in question is true. In the actual proof system, this preamble is repeated many times, presenting many opportunities for rewinding the verifier. We now present the proof system: \medskip \BPR {\em (Protocol \RK\ -- concurrent ZK proof for a language $L$):} \BI \item {\bf Common input:} $x\in L$ and a security parameter $n$. \item {\bf Auxiliary input to the prover:} a witness $w$ for $x\in L$. \item {\bf Preamble length:} $\ell$ \item {\bf Part~1 -- the preamble:} \BE \item $P$ sends $V$ the first message of a two-round perfectly hiding commitment scheme. \item $V$ chooses $\ell$ random strings $r_1,\ldots,r_\ell\rnd\bitset^n$. Then, $V$ sends $P$ perfectly-hiding commitments to $r_1,\ldots,r_\ell$. \item Repeat $\ell$ times \(for $j = 1,\ldots,\ell${\em ):} \BE \item $P$ computes a perfectly-binding commitment $c_j={\sf Commit}(0^n)$ and sends it to $V$. \item $V$ decommits, revealing $r_j$. \EE \EE \item {\bf Part~2 -- the proof:} \BE \item $P$ and $V$ run any \(efficient-prover\) zero-knowledge or witness-indistinguishable proof for $\NP$ for the following statement: \begin{quote} Either $x\in L$ or there exists a $j$ $(1\leq j\leq \ell)$ such that $c_j = {\sf Commit}(r_j)$. \end{quote} \EE \EI \label{prot:RK} \EPR \ni Let $\RK(\ell)$ denote the instantiation of Protocol \RK\ for the case that the number of iterations in the preamble is $\ell$. Now, as we have mentioned above, it has been shown that $\RK(\tilde O(\log^2n))$ is unbounded concurrent zero-knowledge~\cite{KP}. Below, we will prove that $\RK(m\kappa(n))$ is $m$-bounded concurrent zero-knowledge. This is a far weaker claim than that of~\cite{KP}. However, as we have mentioned, we prove this in order to demonstrate our new simulation technique, that enables us to later use \RK\ as a subprotocol in another, different protocol. We remark that our proof that $\RK(m\kappa(n))$ is $m$-bounded concurrent zero-knowledge is far simpler than all known proofs for the unbounded concurrency case. (Of course this is facilitated by the fact that in the model of bounded concurrency we can make the protocol depend on the number of concurrent executions.) Loosely speaking, our simulation strategy works as follows. In general, it is difficult to construct concurrent zero-knowledge protocols because rewinding one execution may force the simulator to rewind many other executions (that may even have already been successfully simulated). The idea behind our simulation strategy is to always rewind only the first execution that provides a rewinding opportunity, and to let all other executions run their course at this point. This strategy yields the result that the rewinding in a given execution results in a potential loss of at most one rewinding possibility for every other execution. Since each protocol has more than $m$ rewinding possibilities and there are only $m$ executions, we have that each execution can be simulated (i.e., there is always guaranteed to be a ``spare'' rewinding point in each execution). The actual simulation is slightly more complicated because we wish to obtain strict polynomial-time simulation. Furthermore, later we will need to simulate the zero-knowledge protocol when run together with other protocols (in order to obtain our result for general secure computation). This also adds complications, but is dealt with in a similar way to the strategy shown here. \BP Let $\kappa(\cdot)$ be any super-constant function. Then, assuming the security of the prescribed commitment schemes, Protocol\, $\RK(m\kappa(n))$ is an $m$-bounded \(black-box\) concurrent zero-knowledge proof system for the language $L$. Furthermore, the zero-knowledge simulator runs in strict polynomial-time. \label{prop:cZK} \EP \BPF In order to prove this proposition, we need to show completeness, soundness and $m$-bounded concurrent zero-knowledge. Completeness follows immediately from the completeness of the zero-knowledge proof of part~2. We proceed to prove soundness: \medskip\ni{\bf Soundness:} By the soundness of the proof in part~2, it suffices to show that the probability that there exists a $j$ such that $c_j={\sf Commit}(r_j)$ is negligible. However, this follows immediately from the fact that $V$ commits using a perfectly-hiding commitment scheme. Therefore, $P$ has no information about $r_j$ when it generates its commitment $c_j$. See more details in~\cite{RK}. \medskip\ni{\bf \boldmath{$m$}-bounded concurrent zero-knowledge:} We begin by presenting some notation and terminology. Denote by $\Pi_k$ the $k^\th$ execution of the protocol and by $\Pi_k^j$ the $j^\th$ iteration of the preamble in the $k^\th$ execution. We say that iteration $\Pi_k^j$ {\sf opens} when the prover $P$ sends the perfectly-binding commitment $c_j$ in $\Pi_k$, and that it {\sf closes} when the verifier $V^*$ decommits to $r_j$ in $\Pi_k$. An execution is said to have been {\sf satisfied} by the simulator $S$ if $V$ aborts the execution (by say, refusing to decommit in some iteration), or if there exists a $j$ such that $c_j={\sf Commit}(r_j)$. Notice that once an execution has been satisfied, the simulator can complete the simulation without any rewinding. (In the case of an aborted execution, this is immediate. In the case that $c_j={\sf Commit}(r_j)$, the simulator can use this fact instead of a witness for $x\in L$ in part~2 of the proof.) Therefore, the simulation strategy is basically for $S$ to satisfy every execution before it reaches part~2 of the proof. Loosely speaking, the simulator $S$ works by playing the honest prover until the first iteration of an unsatisfied execution closes. Assume that this iteration is $\Pi_k^j$, and let $r_j$ be the string decommitted to by the verifier $V^*$. Then, $S$ rewinds $V^*$ to the point in execution~$k$ that iteration~$j$ opened and sends a new perfectly-binding commitment $c_j={\sf Commit}(r_j)$. Next, $S$ continues forward (playing the honest prover) hoping that once again $\Pi_k^j$ is the first iteration to close. If this occurs and $V^*$ decommits, then with overwhelming probability execution~$k$ is satisfied. (Execution~$k$ may not be satisfied in the case that $V^*$ now decommits to a different string $r'_j\neq r_j$. However, due to the computational binding of the commitment scheme used by the verifier, this happens with only negligible probability.) If $\Pi_k^j$ is not the first iteration to close, then $S$ repeats the process again for a fixed polynomial number of times. If success is not obtained in any of these rewinding attempts, then $S$ abandons this attempt to satisfy the execution and continues in the same manner as above. This strategy is used for all executions, and we show that eventually, all executions are satisfied except with negligible probability. This high-level strategy is what also lies behind the simulators of~\cite{RK,KP}. The novelty of our strategy is that the simulator will iteratively fix the transcript throughout the simulation, thereby limiting the rewinding (to the part not yet fixed). Thus, we obtain a strategy which uses rewinding, but in a significantly more restricted way than for previous simulators. This will be crucial for using the zero-knowledge proof as a subprotocol. We now proceed to formally define the simulator: \medskip\ni{\sc The simulator $S$:} We describe the simulation strategy of $S$ for the remaining set of unsatisfied executions (initially this set contains all executions). $S$'s high-level strategy is to satisfy an execution, permanently fix the transcript until the point that the execution was satisfied (without any further rewinding behind this point), and then continue to satisfy another execution from that point on. Before continuing, we introduce some terminology. We call the point at which $S$ fixes the transcript a {\sf fixed point}.% \footnote{Formally, ``fixing the transcript'' means fixing the prefix of all future oracle calls to $V^*$.} % Furthermore, the {\sf current fixed point} is the last fixed point to be set by $S$. Now, $S$ holds a list of unsatisfied executions and attempts to satisfy an execution from this list without rewinding behind its current fixed point. According to this strategy, only iterations that were opened after the current fixed point may be rewound. Thus, we call an iteration {\sf potential} if it {\em opened}\/ after the current fixed point. Now, $S$ interacts with verifier $V^*(x,z,r)$ in a black-box manner, playing the honest prover strategy for part~1 of the proof and waiting for one of the following two events: \BE \item {\em $V^*$ aborts an unsatisfied execution:} When this occurs, the execution is satisfied. Therefore, $S$ sets a fixed point at the ``abort'' message, removes this execution from the set of unsatisfied executions and continues as described above. We note that an abort message is just any detectably illegal message sent by $V^*$. \item {\em A potential iteration closes:} Let this iteration be $\Pi_k^j$ and let $r_j$ be the string decommitted to by the verifier when $\Pi_k^j$ closed. Furthermore, let $r_S$ be the random coins used by $S$ in the simulation since the last fixed point was set. Now, $S$ rewinds $V^*$ back to the point at which iteration $\Pi_k^j$ opened and sends $c_j={\sf Commit}(r_j)$, instead of a commitment to $0^n$. Then, $S$ continues in the simulation with the hope that $\Pi_k^j$ will be the first iteration to close again. We stress that $S$ uses fresh random coins in this continuation (i.e., coins that are independent from the coins used previously). Now, as we have mentioned, $S$'s aim in this rewinding is to once again have $\Pi_k^j$ be the first potential iteration to close. Therefore, if $V^*$ aborts an execution or closes a different potential iteration {\em before}\/ $\Pi_k^j$ closes, then $S$ rewinds back to the point at which $\Pi_k^j$ opened and tries again (with new random coins). $S$ attempts this rewinding $2mn^2$ times. If in all of these attempts $\Pi_k^j$ does not close before another event causing a fixed point occurs, then $S$ abandons this attempt at satisfying $\Pi_k$. Instead, $S$ rewinds $V^*$ to the current fixed point and replays the honest prover strategy using the random coins $r_S$ that it used the first time that $\Pi_k^j$ closed. Then, $S$ fixes the transcript at the point that $\Pi_k^j$ closes and continues as above. In such a case, we say that the fixed point set by $S$ is a {\sf failed fixed point}. If at any point during the simulation it turns out that $\kappa(n)$ {\em consecutive}\/ fixed points are failed, then $S$ outputs {\sf failure} and halts. Now, if in one of the $2mn^2$ rewinding attempts, $\Pi_k^j$ {\em is}\/ the first iteration to close (without the other events occurring), then $S$ does the following. Let $r_j'$ be the decommitment of $V^*$ in the second time that $\Pi_k^j$ is the first iteration to close. If $r_j'\neq r_j$, then $S$ outputs {\sf failure} and halts. Otherwise, the execution is satisfied (because $c_j={\sf Commit}(r_j)$. Having satisfied $\Pi_k$, simulator $S$ fixes the transcript at the point that $\Pi_k^j$ closes, removes $\Pi_k$ from the set of unsatisfied executions and continues as above. \EE In addition to the above, whenever part~2 of a satisfied (and non-aborted) execution is reached, $S$ proves the proof using the witness to the fact that $c_j={\sf Commit}(r_j)$ for some $j$. In contrast, if part~2 of an {\em unsatisfied} execution is reached, then $S$ outputs a special {\sf unsatisfied} symbol and halts. (In such a case $c_j \neq {\sf Commit}(r_j)$ for every $j$, and so $S$ cannot prove the proof of part~2.) $S$ continues in this way until $V^*$ concludes the interaction. This completes the description of $S$. \medskip\ni{\sc Proof of the simulation strategy:} We first comment that the simulator runs in time that is polynomial in $n$. This follows from the fact that the overall number of rewinding attempts in all of the $p(n)\cdot m\kappa(n)$ iterations (over all executions) is at most $2mn^2 \cdot p(n) \cdot m\kappa(n)=\poly(n)$. (Recall that $m=m(n)$ equals the number of executions that are run simultaneously and $p(n)$ equals the total number of executions.) Next, we demonstrate that $S$ outputs a distribution that is computationally indistinguishable from a real execution between $P$ and $V^*$. We first bound the probability that $S$ outputs a special {\sf failure} or {\sf unsatisfied} symbol. \BCM The probability that $S$ outputs {\sf failure} is negligible. \label{clm:failure} \ECM \BPF There are two events that can cause $S$ to output {\sf failure}. We separately show that each of these events can occur with at most negligible probability: \BE \item {\em Event 1 -- $V^*$ decommits to some $r_j' \neq r_j$ in one of the rewinding attempts:} The fact that $V^*$ decommits to the same $r_j$ before and after rewinding is due to the computational binding of the commitment scheme. The proof of this is standard and is therefore omitted. %(A similar argument has been shown in %\cite[Claim 3]{GoKa}.) %(A similar argument is shown in \cite[Claim 3]{GoKa}.) %Next, we show that the probability that $V^*$ decommits to $q' %\neq q$ is negligible by reducing this to the computational %binding of the commitment scheme. We call such an event an %``ambiguous opening''. Assume by contradiction that there exists a %polynomial $p(\cdot)$ such that for an infinite series of input %graphs $G$, simulator $S$ sees an ambiguous opening during the %simulation. Then, we construct a machine $M$ that generates %commitments and ambiguous openings as follows. $M$ receives the %first message of a perfectly hiding commitment scheme and runs the %same strategy as $S$, feeding $V^*$ this first message. $M$ then %waits to see if an ambiguous opening occurs. If yes, $M$ outputs %the appropriate commitment and its two decommitments. The only %problem with this argument is that this $M$ runs in expected %polynomial-time, whereas the security of the commitment scheme is %with respect to strict polynomial-time machines. This is easily %overcome by having $M$ truncate the simulation if it exceeds %$q(t(n),p(n))$ for some fixed polynomial $q(\cdot)$, where $t(n)$ %is the expected running-time of $M$ on input $G$ ($n=|G|$). The %resulting $M$ now runs in strict polynomial-time and succeeds for %an infinite number of $n$'s with probability that is at most %negligibly smaller than $1/p(n)$. In particular, for an %appropriate choice of $q(\cdot)$, it succeeds with probability %greater than $1/2p(n)$. This contradict the binding of the %commitment scheme. \item {\em Event 2 -- $\kappa(n)$ consecutive fixed points are failed:} In order to bound the probability that this occurs, we first consider the probability that a single fixed point is failed. Let $\Pi^j_k$ be a potential iteration that closed first, and let $p^j_k$ be the probability that given the transcript until the point that $\Pi_k^j$ opens, iteration $\Pi^j_k$ closes before any other event causing a fixed point occurs. Then, there are two possibilities: \BE \item $p^j_k \geq \frac{1}{mn}$: In this case, the probability that $\Pi^j_k$ will {\em not}\/ be the first to close in all of the $2mn^2$ rewinding attempts is negligible. This can be seen as follows. Denote by $\tilde p^j_k$, the probability that given the transcript until $\Pi_k^j$ opened, iteration $\Pi^j_k$ is the first iteration to close during a rewinding attempt. Now, $p^j_k$ and $\tilde p^j_k$ may differ because the perfectly-binding commitment provided by $S$ before rewinding is to $0^n$ and after rewinding is to $r_j$. However, by the computational hiding of the commitment, this difference can be at most negligible. (The formal reduction to breaking the hiding of the scheme is standard and is therefore omitted.) It therefore follows that $\tilde p^j_k > \frac{1}{2mn}$. In other words, the probability that $\Pi^j_k$ is not the first to close in any given rewinding attempt is less than $(1-\frac{1}{2mn})$. Therefore, the probability that it is not the first to close in all of the $2mn^2$ independent rewinding attempts is upper-bound by $(1-\frac{1}{2mn})^{2mn^2} < e^{-n}$, which is negligible. \item $p^j_k < \frac{1}{mn}$: In this case, we cannot claim that with overwhelming probability, $\Pi_k^j$ will be the first iteration to close again in at least one of the rewinding attempts. Rather, we bound the probability that a potential iteration $\Pi^j_k$ with $p^j_k < 1/mn$ will be the first iteration to close {\em before}\/ any rewinding takes place. Let $F$ denote the set of {\em potential}\/ iterations for which the probability that the iteration is the first to close is less than $1/mn$. Then, since there are at most $m$ potential iterations between any two fixed points (at most one per execution), we have that $|F| \leq m$. (The fact that every unsatisfied execution can only have one potential iteration between any two fixed points follows from the fact that as soon as a potential iteration closes, a fixed point is set. Thus, a second potential iteration can only open after the previous one closed, meaning that a fixed point separates them.) Therefore, by the union bound, the probability that an iteration from $F$ will be the first to close is less than $1/n$. \EE Combining the above, we have that the probability of encountering any single failed fixed point is less than $1/n + e^{-n} < 2/n$. Now, by the simulation strategy, $S$ outputs {\sf failure} if $\kappa(n)$ consecutive fixed points are failed. The probability that this occurs can be bound as follows. For any given starting fixed point, the probability that $\kappa(n)$ consecutive failed fixed points are encountered from this starting point is less than $(\frac{2}{n})^{\kappa(n)}$ (this is based on the above analysis that bounds the probability of encountering a single failed fixed point, given the previously fixed transcript, by $2/n$). There are at most $m\kappa(n)$ starting fixed points, and so the overall probability of encountering $\kappa(n)$ consecutive failed fixed points is upper bound by $m\kappa(n)(\frac{2}{n})^{\kappa(n)}$, which is negligible as long as $\kappa(n)$ is a super-constant function of $n$ (e.g., $\kappa(n)=\log\log n$). \EE This completes the proof. \EPF \ni Next, we show that $S$ never outputs the special {\sf unsatisfied} symbol. \BCM The probability that $S$ outputs {\sf unsatisfied} equals $0$. \label{clm:satisfy} \ECM \BPF $S$ only outputs {\sf unsatisfied} in the case that it reaches part~2 of the proof in an execution that it did not satisfy; let $\Pi_k$ be this execution. We can assume that $S$ does not output {\sf failure} (because if it did, then it would not output {\sf unsatisfied}). This implies that there are at most $\kappa(n)-1$ consecutive failed fixed points and that for all other fixed points, the execution for which the fixed point was set is satisfied. Now, there are $m\kappa(n)$ iterations in $\Pi_k$'s preamble. Furthermore, as we have mentioned, at most one iteration of any unsatisfied execution, including $\Pi_k$, can be opened between every two fixed points. Therefore, $S$ must have placed $m\kappa(n)$ fixed points before part~2 of $\Pi_k$ is reached. Since there are at most $\kappa(n)-1$ consecutive failed fixed points, by a pigeon-hole argument we have that there must be $m$ {\em non-failed}\/ fixed points that were placed by $S$. However, a non-failed fixed point is only placed when $S$ satisfies an execution. Therefore, $m$ different executions were satisfied between the time that $\Pi_k$ started and finished. Since the setting here is of $m$-bounded concurrency, there can be at most $m\!-\!1$ other executions that run simultaneously with $\Pi_k$. We therefore conclude that $\Pi_k$ must also have been satisfied. \EPF \ni Having established that $S$ outputs a special symbol with at most negligible probability, we are ready to prove that the simulation is successful. That is, \BCM Let $m=m(n)$ be a polynomial. Then, for every non-uniform probabilistic polynomial-time verifier $V^*$ who schedules the messages according to $m$-bounded concurrency and every polynomial $p(\cdot)$, $$ \left\{\langle P,V^*(z,r)\rangle(\ov x)\vphantom{S^{V^*}}\right\} _{n\in\N;\ov x\in L_n^{p(n)};z,r\in\bitset^*} \indist \left\{S^{V^*(\ov x,z,r)}(\ov x)\right\}_{n\in\N;\ov x\in L_n^{p(n)};z,r\in\bitset^*} $$ where $L_n = L \cap \bitset^n$. \label{clm:indist} \ECM \BPF We assume that $S$ does not output {\sf failure} or {\sf unsatisfied}. This is fine because these events happen with at most negligible probability. Next, consider the following hybrid experiment. Let $M^{V^*}$ be a machine who is given a witness to the fact that $x\in L$ and follows the strategy of $S$ exactly with the following exception. When $M$ reaches part~2 of the proof for a satisfied execution, it uses its knowledge of the witness to prove the proof in the same way as the honest prover, rather than using the fact that $c_j={\sf Commit}(r_j)$ for some $j$. We first claim that the distribution generated by $M^{V^*}$ is computationally indistinguishable from the distribution generated in a real execution between $P$ and $V^*$. Intuitively, the only difference between the transcripts is regarding the prover commitments, which are to $0^n$ in a real execution and to $r_j$ in the simulation by $M^{V^*}$. Therefore, the indistinguishability is due to the hiding property of commitments. More formally, consider the following two experiments with a probabilistic polynomial-time distinguishing machine $D$ and a perfectly-binding commitment scheme {\sf Commit}. In the first experiment, $D$ adaptively chooses $n$-bit values $r_1,r_2,\ldots$ and sends these values to an oracle that returns $c_j={\sf Commit}(r_j)$ for each $j$. Note that $D$ chooses the $r_j$ values adaptively and therefore $r_j$ is chosen after $c_1,\ldots,c_{j-1}$ have been received. In the second experiment, $D$ does the same; however, for each oracle query it receives back a commitment $c_j={\sf Commit}(0^n)$. (Of course, all commitments are generated with independent random coins.) By the hiding property of the commitments, these two experiments are indistinguishable; i.e., every such $D$ outputs~1 in both experiments with negligibly close probability. (This follows from a standard hybrid argument.) Now, let $\tilde M^{V^*}$ be a machine who participates in the above experiments (playing the role of $D$). Machine $\tilde M^{V^*}$ works exactly like $M^{V^*}$ except that instead of generating a prover-commitment to a string $r_j$ by itself, it queries its oracle with $r_j$ and uses the response $c_j$ as if it is a commitment to $r_j$. (Note that we abuse notation here and ignore the fact that $r_j$ can be from any iteration and any execution.) Now, on the one hand, if $\tilde M^{V^*}$ is involved in the first experiment (thereby receiving commitments to $r_j$), then it generates {\em exactly}\/ the same distribution as $M^{V^*}$. On the other hand, if $\tilde M^{V^*}$ is involved in the second experiment (thereby receiving commitments to $0^n$), then we claim that it generates a distribution that is statistically close to a real execution between $P$ and $V^*$. The fact that the distribution is statistically close to a real execution requires justification because $\tilde M^{V^*}$ rewinds $V^*$. Intuitively, this holds because in both cases, the commitments received by $V^*$ are to $0^n$; furthermore, the rewinding carried out by $\tilde M^{V^*}$ is such that it does not skew the distribution of the transcript in any way. This is formally shown by induction over the fixed points. The base case refers to an empty transcript (this is as if a fixed point is placed before the simulation begins). Now, assume that indistinguishability holds until the $i^\th$ fixed point is set; we now prove for the $i\!+\!1^\th$ fixed point. In order to prove this, first note that the setting of a fixed point can be viewed as the following two-step process: \BE \item Sample the event that causes the next fixed point to be set in a real execution. There are at most $2$ such events that can occur for every execution: 1 event for the case that the verifier aborts, and 1 event for the case that a potential iteration is the first to close. \item Given the event that causes the next fixed point to be set, sample from all real transcripts that result in this event occurring. \EE The above ``sampling'' is according to the distribution defined by $V^*(x,z,r,t)$, where $x,z,r$ are $V^*$'s common-input, auxiliary-input and random-tape, respectively, and $t$ is the transcript up to the $i^\th$ fixed point. Note that the distribution in question is dependent upon the prover's coins only ($V^*$'s coins $r$ are fixed here). Now, if $\tilde M^{V^*}$ does not carry out any rewinding in setting the $i\!+\!1^\th$ fixed point, then the portion of the transcript between the $i$ and $i\!+\!1^\th$ fixed point that is obtained, is distributed {\em exactly}\/ like the transcript of a real execution between $P$ and $V^*$. (Recall that in this case $\tilde M^{V^*}$ sends commitments to $0^n$ (just like the real prover) and furthermore, it uses a ``real witness'' for proving the proof of part~2.) We note that although the transcript is sampled directly, it implicitly follows the above described two-step process. Next, consider the case that rewinding is carried out by $\tilde M^{V^*}$. In this case, there are two possibilities. First, $\tilde M^{V^*}$ may output {\sf failure}; if this happens, then the resulting transcript is different from in a real execution. However, since this happens with at most negligible probability (by Claim~\ref{clm:failure}), this causes at most a negligible difference. In contrast, if $\tilde M^{V^*}$ does not output {\sf failure}, then the transcript that is output is either the same one as before rewinding (as when a failed fixed point is set), or the last one after rewinding (if $\tilde M^{V^*}$ succeeds in learning $r_j$). However, both of these transcripts are uniformly chosen from the set of transcripts in which the potential iteration in question is the first to close (i.e., the sampling is done exactly according to the distribution over all transcripts, conditioned on the event that causes the fixed point to be set). It follows that the transcript generated by $\tilde M^{V^*}$ in the second experiment is {\em statistically close}\/ to a real transcript between $P$ and $V^*$ (the only difference is in the case that {\sf failure} is output). In contrast, as shown above, the transcript generated by $\tilde M^{V^*}$ in the first experiment is exactly the same as by $M^{V^*}$. Therefore, by the indistinguishability of the two experiments, we conclude that the transcript distribution generated by $M^{V^*}$ is computationally indistinguishable from the transcript generated in a real execution. Next, we consider the difference between the distribution generated by $M^{V^*}$ and the distribution generated by $S$. The difference between these distributions is with respect to the witness used for proving part~2 of the proofs. Specifically, $M$ always uses the ``real'' witness for the statement being proved, whereas $S$ always uses the witness that $c_j={\sf Commit}(r_j)$. Thus, the indistinguishability of the distributions reduces to the zero-knowledge (or actually witness indistinguishability) property of the proof in part~2 of the protocol. (We also rely here on the fact that witness indistinguishability is preserved under concurrent composition~\cite{FS90}.) This reduction is straightforward and is therefore omitted. \EPF This completes the proof of Proposition~\ref{prop:cZK}. \EPF \BR {\bf -- on the length of the preamble.} {\rm The number of iterations in the preamble is chosen so that all executions are guaranteed to be satisfied before part~2 of the proof is reached; this is demonstrated in Claim~\ref{clm:satisfy}. Specifically, it holds that the number of iterations needs to be greater than or equal to $\kappa(n)$ times the number of {\em non-failed fixed points}\/ that are placed by the simulator. In the context of bounded concurrent zero-knowledge, the number of non-failed fixed points equals the number of concurrent executions that take place. We stress that we can extend the preamble to be of any polynomial length (greater than or equal to $m\kappa(n)$), and the number of non-failed fixed points required remains $m$ only. This will become important when Protocol~\RK\ is used for obtaining bounded-concurrent secure two-party computation.} \label{remark:length} \ER \BR {\bf -- reducing the length of the preamble.} {\rm We also remark that the length of the preamble can be reduced to $m$, rather than $m\kappa(n)$ by employing an {\em expected polynomial-time}\/ simulation strategy. The difference in the simulator is that when a potential iteration closes first, the verifier is rewound repeatedly until that same iteration closes first again. (This is in contrast to the above-described strategy where at most $2mn^2$ rewinding attempts are made.) We note that this must be done carefully in order to make sure that the simulator remains expected polynomial-time; techniques for such a simulation can be found in~\cite{GoKa}. The reason that we use strict polynomial-time simulation (at the expense of additional rounds) is due to the fact that the zero-knowledge proof is used as a subprotocol in a larger protocol that utilizes ``ideal calls'' to zero-knowledge. Furthermore, this larger protocol has been proven secure for strict polynomial-time adversaries only. Now, if our zero-knowledge simulation ran in expected polynomial-time, then we would encounter the following problem. In order to prove the security of our entire protocol (i.e., the larger protocol combined with our zero-knowledge subprotocol), we first simulate the zero-knowledge proofs, thereby obtaining an adversary for the larger protocol in a setting with ideal zero-knowledge calls. Next, we derive security by applying the proof of security for the larger protocol. Now, if the simulation of the zero-knowledge proof takes expected polynomial-time, then we would obtain an expected polynomial-time adversary for the larger protocol. However, as we have mentioned, this protocol has only been proven secure for strict polynomial-time adversaries. The proof of security would therefore not go through.} \ER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Non-Black-Box Bounded Concurrent ZK} \label{sec:boaz} In this section, we describe the bounded concurrent zero-knowledge protocol of Barak~\cite{B}. The high-level outline of the construction of~\cite{B} is as follows. In the first part of the protocol, the prover and verifier run a ``generation protocol'' with the following property. A simulator is able to obtain some trapdoor information from the verifier during the generation protocol (this trapdoor will be used later on in the simulation). In contrast, in a real execution between the prover and verifier, the prover has only a negligible chance of obtaining this trapdoor information. Then, the second part of the zero-knowledge protocol is designed such that given the trapdoor information, it is possible to complete the proof (without knowing any witness to the statement being proved). Thus, the simulator works by obtaining the trapdoor information in the first part and then using it to complete the proof in the second part. In contrast, in a real interaction the prover will not obtain the trapdoor information and thus its proof must be based on the validity of the statement being proved. In this section, we will only describe the generation protocol of the first part of the protocol of~\cite{B}. This suffices for our purposes here. For details regarding the second part, which uses universal arguments, see~\cite{B,BG}. \paragraph{Easy-hard relations.} The idea behind an easy-hard relation is that in a real interaction between the prover and verifier, it is hard for the prover to ``hit'' the relation. In contrast, it is easy for the simulator to ``hit'' the relation. Thus, such a relation can be used for part~1 of the proof as described above. In the definition below, we refer to ${\sf Ntime}(f(n))$ relations; a relation $R$ is said to be in ${\sf Ntime}(f(n))$ if there exists a non-deterministic Turing machine that upon input $(x,y)$, runs for at most $f(|x|)$ steps and outputs~1 if and only if $(x,y)\in R$. We now present the definition: \BD {\em (easy-hard ${\sf Ntime}(n^{\log\log n})$ relations):} Let $R \subseteq \bitset^* \times \bitset^*$ be an ${\sf Ntime}(n^{\log\log n})$ binary relation. We say that $R$ is an {\sf easy-hard relation}% \footnote{Such a relation is called {\sf interactive strong easy-hard} in \cite{B}. For the sake of brevity, we drop ``interactive'' and ``strong'' from the name.} % if there exist two interactive probabilistic polynomial-time {\sf generating} algorithms $P$ and $V$ that satisfy the following two properties: \BE \item {\em Hardness:} For any \(non-uniform\) probabilistic polynomial-time machine $P^*$, if $\tau$ is the transcript of the interaction of $P^*$ and $V$ on input $1^n$, then the probability that $P^*$ outputs $\sigma$ such that $(\tau,\sigma)\in R$ is negligible in $n$. \item {\em Easiness:} There exists a polynomial-time computable transformation that takes any \(non-uniform\) probabilistic polynomial-time machine $V^*$ and outputs a \(non-uniform\) probabilistic polynomial-time simulator $S^*$ such that $S^*$ outputs a pair $(v,\sigma)$ and: \BE \item The first string $v$ is computationally indistinguishable from the actual view of\, $V^*$ when interacting with $P$. \(The view of a party consists of the contents of its tapes and the messages that it receives.\) \item Let $\tau$ be the transcript that is derived from $v$ \(note that the transcript of an execution can be derived deterministically from either party's view\). Then, except with negligible probability, $(\tau,\sigma)\in R$. \EE \EE The pair $(P,V)$ is called a {\sf generation protocol for $R$}. \label{def:easy-hard } \ED The witness $\sigma$ for $\tau$ is the trapdoor information that was mentioned in the motivating discussion above. The ``hardness'' requirement says that a real prover will not be able to obtain such a $\sigma$; whereas the ``easiness'' requirement says that the simulator will obtain a $\sigma$ as required. In the second part of the argument system of \cite{B}, the prover essentially proves that either the original statement is true or that it knows $\sigma$ from the generation protocol. We remark that we have chosen to denote the generating algorithms by $P$ and $V$ as they are played by the prover and verifier in the zero-knowledge protocol. However, this notion can be defined independently of zero-knowledge (and indeed, the above is independent of the statement being proved). Barak showed that assuming the existence of hash functions that are collision-resistant against $n^{\log \log n}$-time adversaries, it suffices to prove the existence of an ${\sf Ntime}(n^{\log\log n})$ easy-hard relation in order to derive zero-knowledge. Furthermore, if the hardness and easiness properties hold in the bounded concurrent model, then bounded concurrent zero-knowledge is obtained \cite{B}. We note that the hardness assumption regarding the hash functions has been reduced so that it suffices for them to be collision resistant against any polynomial-time adversary \cite{BG}. However, this requires some special properties in the construction of the easy-hard relation as well. We ignore these technicalities and just remark that the weaker hardness assumption suffices for the results presented here. We now proceed to describe the easy-hard relation of~\cite{B} for achieving bounded concurrent zero-knowledge. \paragraph{The Barak easy-hard relation:} The main idea behind the relation is to have the transcript $\tau$ contain a ``proof'' that $P$ knows the next message function of $V$. The hardness property follows from the fact that $P^*$ cannot know $V$'s next message function (and in particular, $P^*$ cannot guess $V$'s random-tape). In contrast, the simulator $S^*$ {\em does}\/ hold $V^*$'s next message function and can therefore succeed in generating this ``proof''. Of course, the only question remaining is what does it mean for $P$ to ``prove'' that it holds the next message function of $V$? This was solved by \cite{B} in the following way: $P$ sends $V$ a commitment $c$ to a machine $M$, and $V$ replies with some random string $r$. Then, we say that $P$ knows $V$'s next message function if $M(c)=r$ (i.e., when applying the committed machine $M$ to the commitment value $c$, the output is exactly the message sent by $V$ upon receiving the commitment value $c$). The key point behind the hardness is that if $r$ is of high enough entropy, then $P^*$ cannot succeed in committing to the correct $M$. In contrast, since the simulator $S^*$ actually holds the code of $V^*$, it can just set $M=V^*$ (including the contents of all of $V^*$'s tapes). Then, of course, it holds that $M(c)=V^*(c)$ and so the simulator indeed commits to the correct next message function. The above works for the stand-alone case. However, in the bounded concurrent model, $V^*$ will not necessarily respond immediately with $r$. In particular, it may send messages belonging to other executions first. Therefore, it will not hold that $M(c)=r$. The solution to this problem is to say that $P$ holds the next message function if there exists a {\em ``short''}\/ string $y$ such that $M(c,y)=r$. By ``short'', we mean that $y$ should be at least $n$ bits shorter than the random string $r$ sent by $V$. The length of $r$ is fixed to be some polynomial $\ell(n)$, where $\ell(n)$ bounds the length of {\em all}\/ messages received by $V$ during all the concurrent executions. We now describe why this fulfills the requirements of being an easy-hard relation. \BI \item {\em Hardness:} In order for a cheating $P^*$ to succeed, it must be that $M(c,y)=r$. However, $M$ and $c$ are fixed before $V$ chooses $r$. Furthermore, $|r| \geq |y|\!+\!n$. Therefore, the Kolmogorov complexity of $r$ is too high for it to be predicted by $y$, and $P^*$ can ``hit'' the relation with at most negligible probability. \item {\em Easiness:} As in the stand-alone case, the simulator $S^*$ commits to $M=V^*$. However, here $S^*$ must also determine the string $y$. This string $y$ is set to be all the $P$-messages sent by $S^*$ from the time that $S^*$ committed to $M$ (in this execution) until the time that $V^*$ replies with $r$ (in this execution). Since $M=V^*$, it turns out that indeed $M(c,y)=r$. Notice also that since the total length of all $P$-messages in all concurrent execution is less than $\ell(n)$, it is possible for $S^*$ to define $y$ in this way. Thus, the ``easiness'' requirement holds. We note that it doesn't matter how $y$ is generated, as long as the relation is fulfilled. %We note that it is actually possible to extend this simulation to %the case that $V^*$ obtains some of its messages from an external %source (say, an oracle). Furthermore, the simulation works even %though $S^*$ is only given access to $V^*$'s code, and not the %oracle. This holds as long as the message $r$ is actually %generated by $V^*$. In order to see this, note that it doesn't %matter how $V^*$ responds to the messages that form part of $y$; %it is only important how it responds to the entire $y$, and this %is ``committed'' to by $S^*$. We will use this property later on. \EI For more details, see \cite{B}. The generation protocol and easy-hard relation of Barak are as follows: \BCT {\em (Barak generation protocol for an easy-hard relation $R$):} \BI \item {\bf Common input:} $1^n$ \item {\bf Length parameter:} $\ell(n)$ \item {\bf The protocol:} \BE \item $V$ chooses $h\rnd\bitset^n$ \(where $h$ defines a collision-resistant hash function with range in $\bitset^n$\) and sends it to $P$. \item $P$ sends $V$ a commitment $c={\sf Commit}(0^n)$. \item $V$ chooses $r\rnd\bitset^{\ell(n)}$ and sends $r$ to $P$. \EE \EI \label{const:easy-hard} \ECT We now define the easy-hard relation $R$ for which the above is a generation protocol. Loosely speaking, the relation consists of pairs $(c,r)$ and $(M,y)$ such that $c={\sf Commit}(M)$ and $M(c,y)=r$. In other words, the relation is ``hit'' if the prover succeeds in committing to a machine that outputs the verifier's response to the commitment itself (as described in the motivation above). We note that the actual relation also includes $h$ (the hash function from the protocol) and $s$ (the random coins used in generating the commitment $c$ to $M$). Formally, let $R$ be the relation of pairs $\{((h,c,r),(M,s,y))\}$ for which the following holds: \BE \item $M$ is a program of length at most $n^{\log \log n}$ where $n \eqdef |h|$. \item $c$ is a commitment to a hash of $M$ using coins $s$. That is, $c = {\sf Commit}(h(M);s)$. Note that $|h(M)|=n$. \item $\U(M,c,y)$ outputs $r$ within $n^{\log\log n}$ steps, where $\U$ is a universal Turing machine. \item $|y|\leq |r|-n$. \EE \ni Barak has shown that Construction~\ref{const:easy-hard} is a generation protocol in the bounded concurrent model for the easy-hard relation $R$, as long as $\ell(n)$ (that determines the length of $r$) fulfills the following requirement: {\em The total length of all messages sent by $P$ between the time that $P$ sends the commitment $c$ and $V$ replies with $r\rnd\bitset^{\ell(n)}$ is less than $\ell(n)-n$.} Thus, both the soundness and zero-knowledge properties of the protocol of~\cite{B} hold as long as this condition is fulfilled. We note that the length of the messages sent by $P$ in part~2 of the zero-knowledge protocol of~\cite{B} can be bound by $n^2$. Since $P$ only sends $n$ bits in the generation protocol, we can bound the total size of all $P$-messages in the protocol of~\cite{B} by $n^2+n$. Therefore, for $m$ concurrent executions, one can set $\ell(n)=2mn^2$ and it is guaranteed that $r$ is long enough. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A Special-Purpose Composition Theorem} \label{sec:compose} In this section, we consider a model where the parties run a real protocol that uses ideal calls to a zero-knowledge proof of knowledge functionality (computed by a trusted third party). We then present a composition theorem that demonstrates that in the setting of $m$-bounded concurrency, a protocol in this model can be transformed into a different protocol for the real model (with no trusted party), such that the output distributions from the two protocols are essentially the same. This composition theorem is the central tool in our construction of $m$-bounded concurrent secure two-party computation. \subsection{The ZK-Hybrid Model} In general, a {\em hybrid model}\/ is one where parties send protocol messages to each other (like in the real model), but also have access to a trusted party that computes some functionality (like in the ideal model). Thus, this model is a hybrid of the real and ideal models. A protocol that is designed for a hybrid model contains two types of messages: {\sf real messages} that are sent directly between the parties, and {\sf ideal messages} that are sent between the parties and the trusted third party. In the ZK-hybrid model, the parties have access to a trusted party who computes the following ideal zero-knowledge functionality: $$ ((v,w),\lambda) \mapsto (\lambda,(v,R(v,w))) $$ where $R$ is an NP-relation. That is, the first party (the prover) sends a statement $v$ and a witness $w$ to the trusted party computing the functionality. The second party (the verifier) then receives the statement $v$ and a bit $b$ signalling whether or not the prover provided a valid witness for $v$. We note that this functionality is actually a proof of knowledge because the prover must provide an actual witness to the trusted party. In order to model a situation where the verifier may reject a proof of even a true statement, we define a special symbol $\bot$ such that for {\em every}\/ relation $R$ and every $v$, it holds that $(v,\bot)\notin R$. Thus, upon receiving $(v,\bot)$, the trusted party always sends $(v,0)$ to the verifier. Let $p(n)$ be a polynomial and let $\ov x,\ov y \in (\bitset^n)^{p(n)}$ and $z\in\bitset^*$. Then, we denote by $\zkhybrid^m_{\Pi,\A}(\ov x,\ov y,z)$ the output distribution of $p(n)$ concurrent executions of protocol $\Pi$ in the {\rm ZK-hybrid} model, where the scheduling is according to what is allowed in the model of $m$-bounded concurrency. We stress that the only difference between this model and the real model, is that the protocol $\Pi$ also contains ideal messages which are dealt with by the trusted party who computes the above zero-knowledge functionality. \subsection{Motivation for the Composition Theorem} Informally speaking, the composition theorem states that in the setting of $m$-bounded concurrent composition, a real-model protocol $\Pi$ can be constructed from any ZK-hybrid model protocol $\Pi'$ so that the following holds: for any real model adversary $\A$ running $\Pi$ there exists a ZK-hybrid model adversary $\A'$ running $\Pi'$ so that the output distributions in both cases are essentially the same. In other words, the ideal zero-knowledge calls can be replaced by a real protocol, and the result is the same. Jumping ahead, this basically means that it suffices to obtain a secure protocol for the ZK-hybrid model, and we can infer the existence of a secure protocol for the real model. As we will see in Section~\ref{sec:final-prot}, such protocols already exist, and so our goal is fulfilled. The basic idea behind the theorem is to construct $\Pi$ from $\Pi'$ by replacing the ideal calls to the zero-knowledge functionality with concurrent zero-knowledge protocols. However, two main problems arise when attempting to implement such a strategy: \BE \item {\em Malleability$\!\!$ }/{\em Soundness:} Assume that in protocol $\Pi'$, both parties prove zero-knowledge proofs (as is indeed the case for all known protocols for secure two-party computation). Then, we must ensure that the adversary cannot maul the zero-knowledge proof of the honest party in order to cheat. On a technical level this problem arises because in the hybrid model, the zero-knowledge proofs are simulated, and such simulation essentially constitutes ``cheating''. Therefore, if the adversary could cheat by mauling the simulated proofs, this would mean that the result of a real execution (where the adversary cannot cheat) and a hybrid execution (where it can) would be different. In short, the problem here is of soundness and we remark that a naive instantiation of the ideal calls with zero-knowledge protocols would definitely suffer from this problem. \item {\em Simulation under concurrency with other protocols:} In the setting of concurrent zero-knowledge, the protocol in question is run concurrently to itself only; that is, it runs in the context of {\em self-composition}\/ only. In contrast, here the zero-knowledge protocol is run concurrent to itself {\em and}\/ to other protocols, as in the case of {\em general composition}. Therefore, one cannot automatically claim that the zero-knowledge property holds here. In fact, rewinding techniques (used in all black-box zero-knowledge protocols) are very problematic in this context. In order to see this, notice that the natural way to construct the ZK-hybrid model adversary $\A'$ from the real model adversary $\A$ is to have $\A'$ simulate the zero-knowledge proofs for $\A$, while all the other messages (i.e., the messages from the ZK-hybrid model protocol $\Pi'$) are forwarded to the external honest party. This causes a problem because messages from the zero-knowledge proofs in some executions may be interleaved with messages of $\Pi'$ in other executions. Since the messages of $\Pi'$ are forwarded by $\A'$ to an external party, $\A'$ cannot rewind $\A$ at these points. This may conflict with the necessity to rewind in order to simulate the zero-knowledge protocol (if the simulation strategy is indeed based on rewinding). \EE We solve the first problem by using different zero-knowledge protocols so that the adversary cannot maul one protocol in order to cheat in the other. Specifically, we have one of the parties prove statements with the non-black-box zero-knowledge protocol of \cite{B} (see Section~\ref{sec:boaz}), while the other party proves statements with the black-box zero-knowledge protocol of \cite{RK} (see Section~\ref{sec:rk}). Loosely speaking, it turns out that these protocols are both non-malleable (or more accurately, simulation-sound) with respect to each other. That is, both of the protocols remain sound even if the adversary proves one protocol while simultaneously receiving a {\em simulated}\/ proof of the other. We now informally (and inexactly) explain why this holds. If we simulate the protocol of~\cite{RK}, this makes no difference to the soundness of the protocol of~\cite{B} because no rewinding is carried out over the messages of~\cite{B} while simulating~\cite{RK}. (This is guaranteed by taking the number of rounds in the protocol of~\cite{RK} to be large enough, as we show below.) Thus, if it is possible to cheat in this setting, it is possible to cheat in a stand-alone execution of the protocol of~\cite{B} (by running the simulation of~\cite{RK} internally). On the other hand, if we simulate the protocol of~\cite{B}, then as above the simulation of~\cite{B} can be carried out internally, while a single execution of~\cite{RK} is carried out {\em externally}. This means that if an adversary could cheat in this setting, it is possible to cheat in a stand-alone execution of~\cite{RK}. One point worth noting here is that the simulation of the protocol of~\cite{B} {\em can}\/ be carried out, even though some messages are generated externally. The reason for this is that the string $y$ provided by the simulator can be generated in any way, and in particular, can contain messages obtained externally. See Section~\ref{sec:boaz}, just before Construction~\ref{const:easy-hard}, for an explanation. The second problem of concurrency with other protocols is solved as follows. First, the simulation strategy for the protocol of \cite{B} does not use rewinding. Therefore, no problem arises. (We remark that there are parameters for the protocol of \cite{B} that must be modified in this scenario, but this is reasonably straightforward.) In contrast, the simulation strategy of the protocol of \cite{RK} does use rewinding, which as we have described is problematic here. We solve this problem by using the simulation strategy demonstrated in Section~\ref{sec:rk}. Recall that this strategy is almost ``straight-line''. That is, the simulator deals sequentially with each execution and places fixed points behind which it never needs to rewind. The simulation succeeds as long as the number of iterations in the preamble is greater than or equal to the number of non-failed fixed points that need to be placed. Thus, we increase the length of the preamble so that the simulator can place a fixed point for every $\Pi'$-message that is sent. Then, since rewinding only takes place between fixed points, this ensures that no rewinding behind a $\Pi'$-message is necessary. This strategy is based on the methodology used by \cite{GL} to solve the problem of simulating zero-knowledge while external messages may be sent. \subsection{The Composition Theorem} \label{sec:composition-theorem} In this section we show that any protocol $\Pi'$ that runs in the ZK-hybrid model can be transformed into a protocol $\Pi$ in the real model. The transformation is such that any real-model adversary $\A$ for $\Pi$ can be simulated by a ZK-hybrid model adversary $\A'$ for $\Pi'$ in the setting of $m$-bounded concurrency. We remark that the protocol $\Pi$ depends both on $\Pi'$ and on the concurrency bound~$m$. \BT Let\, $\Pi'$ be a two-party protocol for the {\em ZK-hybrid model} and let $m(\cdot)$ be a polynomial. Then, assuming the existence of enhanced trapdoor permutations and collision resistant hash functions, there exists a protocol\, $\Pi$ for the real model with the following property. For every non-uniform probabilistic polynomial-time adversary $\A$ running\, $\Pi$ in the real model, there exists a non-uniform probabilistic polynomial-time adversary $\A'$ running\, $\Pi'$ in the {\rm ZK-hybrid} model such that for every polynomial $p(n)$, $$ \left\{\vphantom{0^{0^0}}\zkhybrid^m_{\Pi',\A'}(\ov x,\ov y,z)\right\}_{n\in\N;\ov x,\ov y \in(\bitset^n)^{p(n)}; z\in\bitset^*} \indist \left\{\vphantom{0^{0^0}}\real^m_{\Pi,\A}(\ov x,\ov y,z)\right\}_{n\in\N;\ov x,\ov y \in(\bitset^n)^{p(n)}; z\in\bitset^*} $$ \label{thm:compose} \ET \BPF We begin by showing how to construct $\Pi$. Denote the participating parties by $P_1$ and $P_2$. Then, both $P_1$ and $P_2$ may ``prove'' zero-knowledge proofs in $\Pi'$ (recall that in $\Pi'$ this involves interaction with the trusted party only). Protocol $\Pi$ is obtained by {\em replacing}\/ all the ideal zero-knowledge calls of $\Pi'$ with the zero-knowledge arguments of knowledge of~\cite{BL}, described in Section~\ref{sec:zkpok}. We denote this protocol by \POK. Recall that in this system of arguments of knowledge, both the prover and verifier play the role of prover in zero-knowledge proofs of {\em membership}; we call these the {\sf subproofs}. Now, all the zero-knowledge subproofs in which $P_1$ is the prover are proven using the black-box concurrent zero-knowledge protocol of~\cite{RK}, described in Section~\ref{sec:rk}; denote this protocol by \RK. Furthermore, all the zero-knowledge subproofs in which $P_2$ is the prover are proven using the concurrent zero-knowledge protocol of~\cite{B}, described in Section~\ref{sec:boaz}; denote this protocol by \BZK. That is, when $P_1$ plays the prover in the zero-knowledge proof of knowledge \POK, then $P_2$ uses Protocol \BZK\ when proving its subproof from the commit-with-extract scheme and $P_1$ uses Protocol \RK\ when proving its subproof in part~2 of \POK. Conversely, when $P_2$ plays the prover in the zero-knowledge proof of knowledge \POK, then $P_1$ uses Protocol \RK\ when proving its subproof from the commit-with-extract scheme and $P_2$ uses Protocol \BZK\ when proving its subproof in part~2 of \POK. {\em The important thing to remember is that all the subproofs in which $P_1$ plays the prover use Protocol\, \RK, and all the subproofs in which $P_2$ plays the prover use Protocol\, \BZK.} We note that the proof of knowledge \POK\ and the subproofs \RK\ and \BZK\ can all be implemented assuming the existence of enhanced trapdoor permutations and collision resistant hash functions. Before continuing, we formally define what it means to ``replace'' an ideal zero-knowledge call with protocol \POK: \BI \item {\em Prover:} If a party is instructed in $\Pi'$ to send $(v,w)$ to the trusted party computing the zero-knowledge functionality, then it plays the prover in the \POK\ zero-knowledge proof of knowledge protocol, using the witness $w$ that it has. The messages that it sends and receives within this proof are not recorded on its transcript for $\Pi'$. \item {\em Verifier:} If in $\Pi'$ a party is to receive a message $(v,b)$ from the trusted party computing the zero-knowledge functionality, then it plays the verifier in the \POK\ zero-knowledge proof of knowledge protocol. If it accepts the proof, then it writes $(v,1)$ on its transcript for $\Pi'$. Otherwise it writes $(v,0)$. As above, the messages within the proof are not recorded on its transcript for $\Pi'$. \EI As we have described above, the \RK\ and \BZK\ protocols are used as subproofs in \POK. Both of these protocols are parameterized: the \RK\ protocol by the number of iterations $k$ in the preamble and the \BZK\ protocol by the length $\ell(n)$ of the verifier message $r$. Recall that in the scenario of $m$-bounded concurrent zero-knowledge, in \RK\ the parameter $k$ is set to $m\kappa(n)$, and in \BZK\ the parameter $\ell(n)$ is set to $2mn^2$. Now, we denote by ${\sf rounds}({\sf Prot})$ the number of rounds in Protocol {\sf Prot}, and by ${\sf length}({\sf Prot})$ the total length (i.e., number of bits) of all the messages sent in Protocol {\sf Prot}. Furthermore, we denote by $\zeta$ the total number of ideal calls made by both parties to the ideal zero-knowledge functionality in $\Pi'$. Finally, when we refer to ${\sf rounds}(\POK)$ and ${\sf length}(\POK)$, we mean the number of rounds and the total length of the messages in the proof of knowledge {\em without}\/ the subproofs \RK\ and \BZK. The parameters for the zero-knowledge subproofs are set as follows. Let $\kappa(\cdot)$ be any super-constant (and sub-linear) function. Then, in \RK\ we set $$ k = \zeta m\kappa(n) + m\kappa(n) \!\cdot\!\left(\vphantom{0^{0^0}}{\sf rounds}(\Pi') + \zeta \!\cdot\!{\sf rounds}(\POK) + \zeta\!\cdot\! {\sf rounds}(\BZK)\right) $$ and in \BZK\ we set $$ \ell(n) = 2\zeta mn^2 + m\!\cdot\!\left(\vphantom{0^{0^0}}{\sf length}(\Pi') + \zeta \!\cdot\!{\sf length}(\POK) + \zeta\!\cdot\!{\sf length}(\RK)\right) $$ In other words, the number of iterations in the \RK\ preamble is $\zeta m\kappa(n)$ plus $m\kappa(n)$ times the combined number of rounds in $\Pi$ excluding the \RK\ subproofs; this combined number of rounds comes to ${\sf rounds}(\Pi')+\zeta \!\cdot{\sf rounds}(\POK)+\zeta\!\cdot{\sf rounds}(\BZK)$. (The first $\zeta m \kappa(n)$ iterations are used to cover the $\zeta m$ executions of \RK, as discussed in Remark~\ref{remark:length}. The number of additional iterations is fixed so that there are $\kappa(n)$ iterations for every non-\RK\ message that is sent in all $m$ executions of the protocol.) Likewise, the length $\ell(n)$ of the message $r$ in \BZK\ is set to $2\zeta mn^2$ (as in $\zeta m$-bounded concurrent zero-knowledge) plus $m$ times the length of all other messages sent. This ensures that $r$ is at least $n$ bits longer than all the messages sent by $P_2$ in $m$ executions of $\Pi$. We remark that there is no problem setting the parameters in such a way. That is, although $\ell(n)$ is dependent on ${\sf length}(\RK)$, the number of rounds in \BZK\ is {\em not} dependent on \RK. Thus, we can first set $k$ and then $\ell(n)$. We digress here for a moment and comment that in our final protocol, ${\sf rounds}(\Pi')$ and $\zeta$ are both constants and thus the final number of rounds in $\Pi$ is $O(m\kappa(n))$, where $\kappa(n)$ is any super-constant function (e.g., $\kappa(n)=\log\log n$). We now show that for every real model adversary $\A$ running $\Pi$, there exists a ZK-hybrid model $\A'$ running $\Pi'$ such that the output distributions generated by $\A$ and $\A'$ are indistinguishable. Intuitively, this is because for $m$-bounded concurrency the zero-knowledge arguments of knowledge as described constitute ``good'' replacements for the ideal calls to the zero-knowledge functionality. Loosely speaking, we construct $\A'$ from $\A$ as follows. $\A'$ internally incorporates $\A$ and externally forwards all the $\Pi'$-messages (i.e., the messages not belonging to the zero-knowledge proofs) between $\A$ and the external party with which $\A'$ interacts. In contrast, $\A'$ internally simulates the zero-knowledge proofs that $\A$ expects to see. Specifically, upon receiving a message $(v,1)$ from the trusted party computing the ideal zero-knowledge functionality, $\A'$ simulates the zero-knowledge proof of knowledge for $v$, where $\A$ plays the verifier. Likewise, when $\A$ proves a proof of knowledge for a statement $v$, the ZK-hybrid model adversary $\A'$ runs the extractor for the proof. If $\A'$ obtains a valid witness $w$, then it sends $(v,w)$ to the trusted third party; otherwise, it sends $(v,\bot)$. Such a strategy ensures that the output distribution generated by $\A'$ in a run of $\Pi'$ (in the ZK-hybrid model) is indistinguishable from the output distribution generated by $\A$ in a run of $\Pi$ (in the real model). Of course, the main challenge (and one of the central contributions of this work), is in showing how to carry out the simulation and extraction when the zero-knowledge proofs of knowledge are subprotocols within a larger protocol that is executed in the setting of $m$-bounded concurrency. We stress that it does not suffice to prove the correctness of the simulation and extraction within the context of $m$-bounded concurrent zero-knowledge. This is because now the zero-knowledge proof is run concurrently with $\Pi'$, and not only concurrently with itself. We now formally prove the existence of a ZK-hybrid model adversary $\A'$ for every real model adversary $\A$. We separately deal with the cases that $P_1$ and $P_2$ are corrupted. \subsubsection{Party \boldmath{$P_1$} is Corrupted} Let $\A$ be a real-model adversary for $\Pi$. We construct an adversary $\A'$ who internally incorporates $\A$ and works in the ZK-hybrid model interacting with $P_2$ in protocol $\Pi'$. Adversary $\A'$ sends {\sf internal} and {\sf external} messages. Internal messages are sent by $\A'$ to the internally incorporated $\A$, whereas external messages are sent by $\A'$ to the external honest party $P_2$ and to the external trusted party computing the ideal zero-knowledge functionality. As we have mentioned, all the $\Pi'$-messages are defined to be external, whereas all of the messages belonging to \POK\ are defined to be internal. Thus, except for the ideal zero-knowledge calls, $\A'$ forwards all of the $\Pi'$-messages unmodified between $\A$ and $P_2$. In addition: \BI \item Whenever $\A$, controlling $P_1$, proves a zero-knowledge proof of knowledge for some statement $v$, $\A'$ runs the {\em extraction}\/ strategy for \POK, possibly obtaining a valid witness $w$ for $v$. (Actually, it runs the {\em witness-extended emulator}\/ for \POK, and obtains both a transcript of an execution along with a value that is possibly a witness. See the short discussion in Section~\ref{sec:zkpok} on witness-extended emulation.) This involves simulating Protocol~\BZK\ for $\A$ as the verifier (because the subproof of part~1 that is simulated is given by $P_2$ to $P_1$) and honestly verifying Protocol \RK\ where $\A$ is the prover (because the subproof of part~2 is given by $P_1$). (In addition, the receiver messages of the commit-with-extract scheme of part~1 are chosen according to the extraction strategy; see Section~\ref{sec:zkpok}.) As we have mentioned, from this extraction procedure (or, actually, witness-extended emulation), $\A'$ receives some string $w$, which is possibly a witness for $v$, and a transcript of an execution of the proof. $\A'$ verifies that the transcript constitutes an accepting proof (this can be publicly verified by the construction of Protocol \POK). If yes, then $\A'$ externally sends $(v,w)$ to the trusted party computing the ideal zero-knowledge functionality. Otherwise, it sends $(v,\bot)$. \item Whenever $\A'$ receives an external message $(v,1)$ from the trusted party, it internally {\em simulates}\/ the zero-knowledge proof of knowledge \POK\ for $\A$. This involves honestly verifying Protocol \RK\ where $\A$ is the prover (from part~1 of \POK) and simulating \BZK\ for $\A$ as the verifier (from part~2 of \POK). (In addition, the value committed to by $\A'$ in the commit-with-extract scheme of part~1 is garbage; see Section~\ref{sec:zkpok}.) \ni (We note that $\A'$ never receives a message $(v,0)$ from the trusted party because $P_2$ is honest and we assume that honest provers always check that they have a correct witness before they send anything to the trusted party or attempt to prove \POK.) \EI The simulation of protocol \BZK\ is carried out using the simulator $S^*$ of~\cite{B}, as described in Section~\ref{sec:boaz}. Notice that in the above simulation, all of the subproofs in which $\A$ is the prover are \RK, and all of the subproofs in which $\A$ is the verifier are \BZK. Having described the simulation by the ZK-hybrid model adversary $\A'$, we proceed to prove that it generates a distribution that is indistinguishable from a real model execution. \paragraph{\sc Proof outline.} Intuitively, the simulation strategy by $\A'$ works as long as Protocol \RK\ is sound and the simulator of \BZK\ succeeds in generating a view that is indistinguishable from a real execution of \BZK. However, in order to prove this, we need to define a hybrid experiment that isolates the \RK\ and \BZK\ executions. We do this by defining an ideal zero-knowledge functionality that is a proof of membership, and not a proof of knowledge. We then show that replacing the \RK\ and~\BZK\ subproofs by this ideal functionality makes at most a negligible difference. This enables us to deal with the \RK\ and \BZK\ subproofs separately. \medskip\ni \paragraph{\sc The hybrid experiment.} The hybrid experiment involves an ideal zero-knowledge {\em proof of membership}\/ functionality, parameterized by an NP-language $L$, and defined by the following: $$ (v,\lambda) \rightarrow (\lambda,(v,\chi_L(v))) $$ where $\chi_L(v)=1$ if and only if $v\in L$. That is, the proving party sends a statement $v$ to the trusted party, who then sends $(v,1)$ to the verifying party if $v \in L$, and $(v,0)$ if $v \notin L$. In order to reflect the possibility that a prover may fail to prove a correct statement in a protocol execution that replaces this ideal functionality, we define that if the statement has the symbol $\bot$ appended to it (i.e., if it is of the form $v \circ \bot$), then the trusted party sends $(v,0)$ to the verifier irrespective of whether or not $v \in L$. We note that this ideal functionality may not be efficient (in particular, if $L$ is a hard language, then verifying whether or not $v\in L$ may take super-polynomial time); nevertheless this suffices here. We denote this hybrid experiment by \memberzk. \paragraph{\sc Step 1 -- replacing \BZK\ with an ideal zero-knowledge proof of membership.} We now define a protocol $\hpi$ that works in the memberZK-hybrid model. $\hpi$ is the same as the real-model protocol $\Pi$ except that instead of $P_2$ proving a statement $v$ to $P_1$ using the subproof \BZK, it sends $v$ to the trusted party computing the ideal zero-knowledge proof of membership functionality. Subproofs given by $P_1$ using \RK\ are unmodified. We now show that for every real-model adversary $\A$ for $\Pi$, there exists an adversary $\ha$ for $\hpi$, such that $\ha$ interacts with $P_2$ in the memberZK-hybrid model and generates an output distribution that is indistinguishable from an execution of $\A$ with $\Pi$ in the real model. Notice that the only difference between $\Pi$ and $\hpi$ is whether proofs given by $P_2$ (who in this case is honest) are carried out by running~\BZK\ or by using the zero-knowledge proof of membership functionality. Thus, the proof of indistinguishability is based on the zero-knowledge (or simulatability) property of \BZK\ in this scenario. The adversary $\ha$ for $\hpi$ works as follows. $\ha$ internally incorporates $\A$ and externally forwards all $\Pi'$, \POK\ and \RK\ messages between $\A$ and $P_2$. However, messages of \BZK\ are internally simulated for $\A$ by $\ha$. That is, whenever $\ha$ receives a message $(v,1)$ from the trusted party computing the ideal zero-knowledge proof of membership functionality, it simulates an execution of~\BZK\ with $\A$ as the verifier. We now prove that \begin{equation} \left\{\vphantom{0^{0^0}}\memberzk^m_{\hpi,\ha}(\ov x,\ov y,z)\right\} \indist \left\{\vphantom{0^{0^0}}\real^m_{\Pi,\A}(\ov x,\ov y,z)\right\} \label{eq:weakzk12} \end{equation} The difference between an execution of $\Pi$ with $\A$ and an execution of $\hpi$ with $\ha$ is that in $\Pi$ party $P_2$ proves real \BZK\ proofs, whereas in $\hpi$ they are simulated. Thus, as we have mentioned \eqref{eq:weakzk12} follows from the zero-knowledge property of \BZK. It remains to show that the \BZK\ simulation ``works'' in this scenario (i.e., within $\hpi$). However, as we have discussed in Section~\ref{sec:boaz}, the simulator for \BZK\ works on the condition that the total length of all the messages sent by the prover (i.e., $P_2$) from the time that it sends the commitment $c$ in \BZK\ until the time that $P_1$ returns $r\in\bitset^{\ell(n)}$ is less than $\ell(n) - n$. In order to see that this holds, recall that in the setting of $m$-bounded concurrency, the scheduling is such that from the time that any given execution begins until it terminates, messages from at most $m$ different executions are sent. Therefore, the length of all messages sent by $P_2$ from the time that it sends $c$ until $P_1$ replies with $r$ is upper-bound by $m$ times the length of all the messages sent by $P_2$ in an execution of $\Pi$. However, this follows immediately from the way $\ell(n)$ was chosen. \pa