2.2.1. Background: How is Security Defined.

First an ideal model for secure multiparty computation is formulated. A computation in this ideal model captures "the highest level of security we can expect from a multiparty computation". Next we require that executing a secure protocol \(\pi\) for evaluating some function \(f\) of the parties' inputs in the actual real-life setting is "equivalent" to evaluating \(f\) in the ideal model, where the meaning of this "equivalence" is explained below.

A computation in the ideal model proceeds as follows. First an ideal-model-adversary chooses to corrupt a set of parties (either adaptively or non-adaptively), learns their input, and possibly modifies it. Next all parties hand their (possibly modified) inputs to an incorruptible trusted party. The trusted party then computes the expected output (i.e. the function value) and hands it back to all parties. At this stage an adaptive adversary can choose to corrupt more parties. Finally the uncorrupted parties output the value received from the trusted party whereas the corrupted parties output some arbitrary function of the information gathered during this computation.

In the real-life model there exists no trusted party and the parties must interact with one another using some protocol in order to compute any "non-trivial" function. We say that the execution of a protocol \(\pi\) for evaluating \(f\) is "equivalent" to evaluating \(f\) in the ideal model, if for any adversary \(\mathcal A\) in the real-life model, there exists an ideal-model-adversary \(\mathcal S\) that has the same effect on the computation as \(\mathcal A\), even through \(\mathcal S\) operates in the ideal model. That is, on any input, the outputs of the parties after running \(\pi\) in the real-life model in the presence of \(\mathcal A\) should be distributed equally to the outputs of parties evaluating \(f\) in the ideal model in the presence of \(\mathcal S\). Furthermore, this condition should hold for any semi-honest protocol \(\pi'\) for \(\pi\) (according to either of the above notions of semi-honesty).

We require that the complexity of \(\mathcal S\) be comparable to (i.e. polynomial in) the complexity of \(\mathcal A\). This requirement can be motivated as follows. Machine \(\mathcal S\) represents "what could have been learned in the ideal model". Thus, security of a protocol can be interpreted as the following statement: "whatever \(\mathcal A\) can learn in the real-life model, could have been learned in the ideal model within comparable complexity". A much weaker and arguably unsatisfactory notion of security emerges if the complexity of \(\mathcal S\) does not depend on that of \(\mathcal A\). (This holds even in the non-adaptive case.)¹

2.2.2. Problems with Proving Adaptive Security

A standard construction of an ideal-model-adversary, \(\mathcal S\), operates via block-box interaction with the real-life adversary \(\mathcal A\). More specifically let \(\pi'\) be a semi-honest protocol for \(\pi.\;\mathcal S\) runs the black-box representing \(\mathcal A\) on a simulated interaction with a set of parties running \(\pi'.\;\mathcal S\) corrupts (in the ideal model) the same parties that \(\mathcal A\) corrupts in the simulated interaction, and outputs whatever \(\mathcal A\) outputs. From the point of view of \(\mathcal A\), the interaction simulated by \(\mathcal S\) should be distributed identically to an authentic interaction with parties running \(\pi'\). It is crucial that \(\mathcal S\) be able to run a successful simulation based only on the information available to it in the ideal model, and in particular without knowing the inputs of uncorrupted parties. We restrict our presentation to this methodology of proving security of protocols, where \(\mathcal S\) is restricted to probabilistic polynomial time. We remark that no other proof method is known in this context. In the sequel we often call the ideal-model-adversary \(\mathcal S\) a simulator.

Following the above methodology, the simulator that we construct has to generate simulated messages from the uncorrupted parties to the corrupted parties. In the non-adaptive case set of corrupted parties is fixed and known to the simulator. Thus the simulator can corrupt these parties, in the ideal model, before the simulation starts. In the adaptive case the corrupted parties are chosen by the simulated adversary \(\mathcal A\) as the computation unfolds. Here the simulator corrupts a party, in the ideal model, only when the simulated adversary decides on corrupting that party. Thus the following extra problem is encountered. Consider a currently uncorrupted party \(P\). Since \(\mathcal S\) does not know the input of \(P\), it may not know which messages should be sent by \(P\) to the corrupted parties. Still, \(\mathcal S\) has to generate some dummy messages to be sent by the simulated \(P\) to corrupted parties. When the simulated adversary \(\mathcal A\) later corrupts \(P\) it expects to see \(P\)'s internal data. The simulator should now be able to present internal data for \(P\) that is consistent with \(P\)'s newly-learned input and with the messages previously sent by \(P\), according to the particular semi-honest protocol \(\pi'\) run by \(P\). It turns out that this can be done for the [?] protocols for computing any function in the presence of non-erasing parties. Thus, the [?] protocols are adaptively secure in the presence of non-erasing parties. Recall, however, that not every protocol which is secure against non-adaptive adversaries is also secure against adaptive adversaries (see example in the third paragraph of the Introduction).

2.2.3. In Face of Honest-Looking Parties

Further problems are encountered when honest-looking parties are allowed, as demonstrated by the following example. Consider a protocol \(\beta\) that instructs each party, on private input \(\sigma\), to publicise a uniformly and independently chosen value \(r\) in some domain \(D\) and terminate. \(\beta\) looks "harmless" in the sense that no information on the inputs leaks out. However, consider the following honest-looking variant of \(\beta\). Let \(f_0,f_1\) be a clawfree pair of permutations over \(D\). Then, on input \(\sigma\in\{0,1\}\), an honest-looking party can 'commit' to its input by publicizing \(f_\sigma(r)\) instead of publicizing \(r\). If this honest-looking variant of \(\beta\) is shown secure via an efficient black-box simulation as described above, then the constructed simulator can be used to find claws between \(f_0\) and \(f_1\). Similar honest-looking variants can be constructed for the [?][?] protocols. Consequently, if clawfree pairs of permutations exist then adaptive security of the [?][?] protocols, in the presence of honest-looking parties, cannot be proven via black-box simulation. In fact, such honest-looking variants can be constructed for any "non-trivial" protocol, with similar effects.

2.3.1. Proving that \(\tilde\pi\) is Non-Adaptively Secure

We first sketch how \(\tilde\pi\) can be shown non-adaptively secure in the computational setting, assuming that \(\pi\) is non-adaptively secure in the secure channels setting. Let \(\mathcal S\) be the ideal-model-adversary (simulator) associated with \(\pi\) in the secure channels setting. (We assume that \(\mathcal S\) operates via "black-box simulation" of the real-life adversary \(\mathcal A\) as described above.) We wish to construct, in the computational setting, a simulator \(\tilde{\mathcal S}\) for \(\tilde\pi\). The simulator \(\tilde{\mathcal S}\) operates just like \(\mathcal S\), with two exceptions. First, in the computational setting the real-life adversary expects the messages sent to corrupted parties to be encrypted. Next, the real-life adversary expects to see the ciphertexts sent between uncorrupted parties. (In the secure channels setting the adversary does not see the communication between uncorrupted parties.) \(\tilde{\mathcal S}\) will imitate this situation as follows. First each message sent to a corrupted party will be appropriately encrypted. Next, the simulated uncorrupted parties will exchange dummy ciphertexts. (These dummy ciphertexts can be generated as, say, encryptions of the value '0'.) The validity of simulator \(\tilde{\mathcal S}\) can be shown to follow, in a straightforward way, from the validity of \(\mathcal S\) and the security of the encryption scheme in use.

2.3.2. Problems with Proving Adaptive Security

When adaptive adversaries are considered, the construction of a simulator \(\tilde{\mathcal S}\) in the computational setting encounters the following additional problem. Consider an uncorrupted party \(P\). Since \(\tilde{\mathcal S}\) does not know the input of \(P\), it does not know which messages should be sent by \(P\) to other uncorrupted parties.² Still, \(\tilde{\mathcal S}\) has to generate dummy ciphertexts to be sent by the simulated \(P\) to uncorrupted parties. These dummy ciphertexts are seen by the adaptive adversary. When the adversary later corrupts the simulated \(P\), it expects to see all of \(P\)'s internal data, as specified by the semi-honest protocol \(pi'\). Certainly, this data may include the cleartexts of all the ciphertexts sent and received by \(P\) in the past, including the random bits used for encryption and decryption, respectively. Thus, it may be the case that some specific dummy ciphertext \(c\) was generated as an encryption of '0', and the simulated \(P\) now needs to "convince" the adversary that \(c\) is in fact an encryption of '1' (or vice versa). This task is impossible if a standard encryption scheme (i.e. an encryption scheme where no ciphertext can be a legal encryption of both '1' and '0') is used.

We remark that Feldman, and independently Beaver and Haber, have suggested to solve this problem as follows^[?][?]. Instruct each party to erase (say, at the end of each round) all the information involved with encrypting and decrypting of messages. If the parties indeed erase this data, then the adversary will no longer see, upon corrupting a party, how past messages were encrypted and decrypted. Thus the problem of convincing the adversary in the authenticity of past ciphertexts no longer exists. Consequently, such "erasing" protocols can be shown adaptively secure in the computational setting. However, this approach is clearly not valid in the presence of semi-honest parties. In particular, it is not known whether the [?][?] protocols (or any other previous protocols) are secure in the presence of non-erasing parties.

2.3.3. Sketch of Our Solution

We solve this problem by constructing an encryption scheme that serves as an alternative to standard encryption schemes, and enjoys an additional property roughly described as follows. One can efficiently generate dummy ciphertexts that can later be "opened" as encryptions of either '0' or '1', at wish. (Here the word 'ciphertext' is used to denote all the information seen by the adversary during the execution of the protocol.) These dummy ciphertexts are different and yet computationally indistinguishable from the valid encryptions of '0' (or '1') produced in a real communication. We call such encryption protocols non-committing.³

Let \(\mathcal E^{(0)}\) (resp. \(\mathcal E^{(1)}\)) denote the distribution of encryptions of the value 0 (resp. 1) in a public-key encryption scheme. For simplicity, suppose that each of these distributions is generated by applying an efficient deterministic algorithm, denoted \(A^{(0)}\) (resp. \(A^{(1)}\)), to a uniformly selected \(n\)-bit string.⁴ In a traditional encryption scheme (with no decryption errors) the supports of \(\mathcal E^{(0)}\) and \(\mathcal E^{(1)}\) are disjoint (and \(\mathcal E^{(0)},\mathcal E^{(1)}\) are computationally indistinguishable). In a non-committing encryption scheme, the supports of \(\mathcal E^{(0)}\) and \(\mathcal E^{(1)}\) are not disjoint but the probability that an encryption (of either '0' or '1') resides in their intersection, denoted \(I\), is negligible. Thus, decryption errors occur only with negligible probability. However, the simulator can efficiently generate a distribution \(\mathcal E^{amb}\) which assumes values in \(I\) so that this distribution is computationally indistinguishable from both \(\mathcal E^{(0)}\) and \(\mathcal E^{(1)}\).⁵ Furthermore, each "ambiguous ciphertext" \(c\in I\) is generated together with two random-looking \(n\)-bit strings, denoted \(r_0\) and \(r_1\), so that \(A^{(0)}(r_0)=A^{(1)}(r_1)=c\). That is, the string \(r_0\) (resp. \(r_1\)) may serve as a witness to the claim that \(c\) is an encryption of '0' (resp. '1'). See Section 3.4 for a definition of non-committing encryption protocols.

Using a non-committing encryption protocol, we resolve the simulation problems which were described above. Firstly, when transforming \(\pi\) into \(\tilde\pi\), we replace every bit transmission of \(\pi\) by an invocation of the non-committing encryption protocol. This allows us to generate dummy ciphertexts for messages sent between uncorrupted parties so that at a later stage we can substantiate for each such ciphertext both the claim that it is an encryption of '0' and the claim that it is an encryption of '1'. We stress that although dummy ciphertexts appear with negligible probability in a real execution, they are computationally indistinguishable from a uniformly generated encryption of either '0' or '1'. Thus, using a non-committing encryption protocol, we construct Adaptively secure protocols for computing any (recursive) function in the computational model in the presence of non-erasing parties. Finally, we construct a non-committing encryption protocol based on a primitive called common-domain trapdoor systems (see Definition 4.3). We also describe two implementations based on the RSA and Diffie-Hellman assumptions respectively. Thus, we get

3.2.1. The Computation in the Ideal Model

The computation in the ideal model, in the presence of an ideal-model-adversary \(\mathcal S\), proceeds as follows. The parties have inputs \(\vec{x}=x_1\dots x_n\in D^n\) (party \(P_i\) has input \(x_i\)) and wish to compute \(f(x_1,\dots,x_n)\), where \(f\) is a predetermined function.⁶ The adversary \(\mathcal S\) has no initial input, and is parametrized by \(t\), the maximum number of parties it may corrupt.

First \(\mathcal S\) proceeds in up to \(t\) iterations. In each iteration \(\mathcal S\) may decide to corrupt some party, based on \(\mathcal S\)'s random input and the information gathered so far. Once a party is corrupted its internal data (that is, its input) becomes known to \(\mathcal S\). A corrupted party remains corrupted for the rest of the computation. Let \(B\) denote the set of corrupted parties at the end of this stage.

\(\mathcal S\) may alter the inputs of the corrupted parties; however, this is done without any knowledge of the inputs of the good parties. Let \(\vec{b}\) be the \(|B|\)-vector of the altered inputs of the corrupted parties, and let \(\vec{y}\) be the \(n\)-vector constructed from the input \(\vec{x}\) by substituting the entries of the corrupted parties by the corresponding entries in \(\vec{b}\).

The parties hand \(\vec{y}\) to the trusted party (party \(P_i\) hands \(y_i\)), and receive \(f(\vec{y})\) from the trusted party.⁷

Now that the output of the computation is known, \(\mathcal S\) proceeds in another sequence of up to \(t-|B|\) iterations, where in each iteration \(\mathcal S\) may decide to corrupt some additional party, based on \(\mathcal S\)'s random input and the information gathered so far (this information new includes the value received from the trusted party by parties in \(B\)). We stress that \(\mathcal S\) may corrupt at most \(t\) parties in the entire computation.

The uncorrupted parties output \(f(\vec{y})\), and the corrupted parties output some arbitrary function, computed by the adversary, of the information gathered by the adversary (i.e. \(\vec{b}\) and \(f(\vec{y})\)). We let the \(n\)-vector \(\operatorname{IDEAL}_{f,\mathcal S}(\vec{x})= \operatorname{IDEAL}_{f,\mathcal S}(\vec{x})_1\dots \operatorname{IDEAL}_{f,\mathcal S}(\vec{x})_n\) denotes the outputs of the parties on input \(\vec{x}\), trusted party for computing \(f\), and adversary \(\mathcal S\) (party \(P_i\) outputs \(\operatorname{IDEAL}_{f,\mathcal S}(\vec{x})_i\)).

For the benefit of formalistic readers we further formalize the above discussion (in Definitions 3.5 through 3.7). Other readers are advised to skip a page up to the paragraph discussing the computation in the real-life setting.

First, we need two technical notations.

• For a vector \(\vec{x}=x_1\dots x_n\), and a set \(B\subseteq[n]\), let \(\vec{x}_B\) denote the vector \(\vec{x}\), projected on the indices in \(B\).
• For an \(n\)-vector \(\vec{x}=x_1\dots x_n\), and a set \(B\subseteq[n]\), and a \(|B|\)-vector \(\vec{b}= b_1\dots b_{|B|}\), let \(\vec{x}/_{(B,\vec{b})}\) denote the vector constructed from vector \(\vec{x}\) by substituting the entries whose indices are in \(B\) by the corresponding entries from \(\vec{b}\).

Let \(D\) be the domain of possible inputs of the parties, and let \(R\) be the domain of possible random inputs. A \(t\)-limited ideal-model-adversary is a quadruple \(\mathcal S=(t,b,h,O)\), where:

• \(t\) is the maximum number of corrupted parties.
• \(b\,:\;[n]^*\times D^*\times R\mapsto[n]\cup\{\perp\}\) is the selection function for corrupting parties (the value \(\perp\) is interpreted as "no more parties to corrupt at this stage")
• \(h\,:\;[n]^*\times D^*\times R\mapsto D^*\) is the input substitution function
• \(O\,:\;D^*\times R\mapsto\{0,1\}^*\) is an output function for the bad parties.

The set of corrupted parties is now defined as follows.

Let \(D\) be the domain of possible inputs of the parties, and let \(\mathcal S=(t,b,h,O)\) be a \(t\)-limited ideal-model-adversary. Let \(\vec{x}\in D^n\) be an input vector, and let \(r\in R\) be a random input for \(\mathcal S\). The \(i\)-th set of faulty parties in the ideal model \(B^{(i)}(\vec{x},r)\), is defined as follows.

• \(B^{(0)} (\vec{x}, r)=\phi\).
• Let \(b_i\stackrel{\Delta}{=}b(B^{(i)} (\vec{x},r), \vec{x}_{B^{(i)}(\vec{x},r)},r).\) For \(0\leq i\lt t\), and as long as \(b_i\neq\perp\), let $$B^{(i+1)}(\vec{x},r) \stackrel{\Delta}{=} B^{(i)} (\vec{x},r) \cup\{b_i\}$$
• Let \(i^*\) be the minimum between \(t\) and the first \(i\) such that \(b_i=\perp\). Let \(b_i^f\stackrel{\Delta}{=}b(B^{(i)} (\vec{x},r), \vec{x}_{B^{(i)}(\vec{x},r)},f(\vec{y}),r)\), where \(\vec{y}\) is the substituted input vector for the trusted party. That is, \(\vec{y} \stackrel{\Delta}{=} \vec{x} /_{(B^{(i^*)}(\vec{x},r), h(B^{(i^*)}(\vec{x},r), \vec{x}_{B^{(i^*)} (\vec{x},r)},r))}\). For \(i^*\leq i\lt t\), let $$B^{(i+1)}(\vec{x},r)\stackrel{\Delta}{=}B^{(i)}(\vec{x},r)\cup b_i^f.$$

In Definition 3.7, we use \(B^{(i)}\) instead of \(B^{(i)}(\vec{x},r)\).

Let \(f\,:\;D^n\mapsto D'\) for some sets \(D,\,D'\) be the computed function, and let \(\vec{x}\in D^n\) be an input vector. The output of computing function \(f\) in the ideal model with adversary \(\mathcal S=(t,b,h,O)\), on input \(\vec{x}\) and random input \(r\), is an \(n\)-vector \(\operatorname{IDEAL}_{f,\mathcal S}(\vec{x})= \operatorname{IDEAL}_{f,\mathcal S}(\vec{x})_1\dots \operatorname{IDEAL}_{f,\mathcal S}(\vec{x})_n\) of random variables, satisfying for every \(1\leq i\leq n\): $$ \operatorname{IDEAL}_{f,\mathcal S}(\vec{x})_i = \begin{cases}f(\vec{y} &\text{if }i\not\in B^{(t)}\\ O(\vec{x}_{B^{(t)}},f(\vec{y}),r) &\text{if }i\in B^{(t)}\end{cases} $$ where \(B^{(t)}\) is the \(t\)^th set of faulty parties, \(r\) is the random input of \(\mathcal S\), and \(\vec{y}= \vec{x}/_{(B^{(t)}, h(B^{(t)}, \vec{x}_{B^{(t)}}, r))}\) is the substituted input vector for the trusted party.

3.2.2. Computation in the Real-Life Setting

Next we describe the execution of a protocol \(\pi\) in the real-life scenario. The parties engage in a synchronous computation in the secure channels setting, running a semi-honest protocol \(\pi'\) for \(\pi\) (according to any one of the notions of semi-honesty defined above). A computationally unbounded \(t\)-limited real-life adversary may choose to corrupt parties at any point during the computation, based on the information known to the previously corrupted parties, and as long as at most \(t\) parties are corrupted altogether. Once a party is corrupted the current contents of its memory (as determined by the semi-honest protocol \(\pi'\)) becomes available to the adversary. From this point on, the corrupted party follows the instructions of the adversary. Once the computation is completed, each uncorrupted party outputs whatever it has computed to be the function value. Without loss of generality, we use the convention by which the corrupted parties output their entire view on the computation. The view consists of all the information gathered by the adversary during the computation. Specifically, the view includes the inputs and random inputs of the corrupted parties and all the communication seen by the corrupted parties.

We use the following notation. Let \(\operatorname{VIEW}_{\pi,\mathcal A}(\vec x, \vec r)\) denote the view of the adversary \(mathcal A\) when interacting with parties running protocol \(\pi\) on input \(\vec x\) and random input \(\vec r\) (\(x_i\) and \(r_i\) for party \(P_i\)), as described above. Let \(\operatorname{EXEC}_{\pi,\mathcal A}(\vec x,\vec r)_i\) denote the output of party \(P_i\) after running protocol \(\pi\) on input \(\vec x=x_1\dots x_n\) and random input \(\vec r=r_1\dots r_n\), and with a real life adversary \(\mathcal A\). (By the above convention, we have \(\operatorname{EXEC}_{\pi,\mathcal A}(\vec x,\vec r)_i=\operatorname{VIEW}_{\pi,\mathcal A}(\vec x,\vec r)\) for corrupted parties \(P_i\).) Let \(\operatorname{EXEC}_{\pi,\mathcal A}(\vec x)_i\) denote the random variable describing \(\operatorname{EXEC}_{\pi,\mathcal A}(\vec x,\vec r)_i\) where \(\vec r\) is uniformly chosen. Let \(\operatorname{EXEC}_{\pi,\mathcal A}(\vec x)=\operatorname{EXEC}_{\pi,\mathcal A}(\vec x)_i\dots\operatorname{EXEC}_{\pi,\mathcal A}(\vec x)_n\).

3.2.3. Comparing Computations

Finally we require that executing a secure protocol \(\pi\) for evaluating a function \(f\) be equivalent to evaluating \(f\) in the ideal model, in the following sense.

Let \(f\) be an \(n\)-ary function, \(\pi\) be a protocol for \(n\) parties and \(\mathcal T\) a type of semi-honest behavior (i.e. as in any of the Definitions 3.2 through 3.4). We say that \(\pi\;t\)-securely computes \(f\) in the secure channels setting in the presence of \(\mathcal T\)-semi-honest parties and adaptive adversaries, if for any \(\mathcal T\)-semi-honest protocol \(\pi'\) for \(\pi\) and for any \(t\)-limited real-life (adaptive) adversary \(\mathcal A\), there exists a \(t\)-limited ideal-model-adversary \(\mathcal S\), such that the complexity of \(\mathcal S\) is polynomial in the complexity of \(\mathcal A\), and for every input vector \(\vec x\) we have $$\operatorname{IDEAL}_{f,\mathcal S}(\vec x)\stackrel{d}{=}\operatorname{EXEC}_{\pi',\mathcal A}(\vec x)$$

Definition 3.8 is stated for a single value of \(n\). In order to discuss asymptotic complexity (in \(n\)), we assume that the function \(f\), the protocol \(\pi\), the simulator \(\mathcal S\), and the adversary \(\mathcal A\) are Turing machines that have \(n\), the number of parties, as part of their inputs.

3.2.4. Black-box Simulation

In the sequel we use a more restricted notion of equivalence of computations, where the ideal-model adversary is limited to black-box simulation of the real-life setting. That is, for any semi-honest protocol \(\pi'\) for \(\pi\) there should exist an ideal-model adversary \(\mathcal S\) with oracle (or black-box) access to a real-life adversary. This black-box represents the input-output relations of the real-life adversary described above. For concreteness, we present the following description of the "mechanics" of this black-box, representing a real-life adversary. The black-box has a random tape, where the black-box expects to find its random input, and an input-output tape. Once a special start input is given on the input-output tape, the interaction on this tape proceeds in iterations, as follows. Initially, no party is corrupted. In each iteration \(l\), first the black-box expects to receive the information gathered in the \(l\)^th round. (In the secure channels setting this information consists of the messages sent by the uncorrupted parties to the corrupted parties.) Next black-box outputs the messages to be sent the corrupted parties in the \(l\)^th round. Next, the black-box may issue several 'corrupt \(P_i\)' requests. Such a request should be answered by the internal data of \(P_i\), according to protocol \(\pi'\). Also, from this point on \(P_i\) is corrupted. At the end of the interaction, the output of the real-life adversary is defined as the contents of the random tape succeeded by the history of the contents of the input-output tape during the entire interaction. We let \(\mathcal S^{\mathcal A}\) denote the ideal-model adversary \(\mathcal S\) with black-box access to a real-life adversary \(\mathcal A\).

The simulator is restricted to probabilistic polynomial-time (where each invocation of the black-box is counted as one operation).⁸ Furthermore, we limit the operation of the simulator as follows. We require that the start message is sent only once, and that no party is corrupted in the ideal model unless a request to corrupt this party is issued by the black-box.

If Definition 3.8 is satisfied by an ideal-model adversary limited to black-box simulation as described above, then we say that \(pi\;t\)-securely computes \(F\) in a simulatable way. In this case we call the ideal-model adversary a black-box simulator, or in short a simulator.

We remark that the only purpose of the technical restrictions imposed on the operation of the simulator is to facilitate proving composition theorems (such as Theorem 4.2). We stress that the security of known protocols (e.g. [?]) can be shown via simulators that obey these restrictions.

4.2.1. Encryption and Decryption

Let \(f_a\) and \(f_b\) be two randomly selected permutations over the domain \(D\), and let \(B\) be a hardcore predicate associated with them. The scheme uses a security parameter, \(k\), which can be thought to equal \(log_2|D|\).

To encrypt a bit \(\sigma\in\{0,1\}\) with encryption key \((f_a,f_b)\), the sender proceeds as follows. First it chooses \(x_1,\dots,x_{8k}\) at random from \(D\), so that \(B(x_i)=\sigma\) for \(i=1,\dots,5k\) and \(B(x_i)=1-\sigma\) otherwise (i.e. for \(i=5k+1,\dots,8k\)). For each \(x_i\) it computes \(y_i=f_a(x_i)\). These \(x_i\)'s (and \(y_i\)'s) are associated with \(f_a\) (or with \(a\)). Next it repeats the process with respect to \(f_b\). That is, \(x_{8k+1},\dots,x_{16k}\) are chosen at random from \(D\), so that \(B(x_i)=\sigma\) for \(i=8k+1,\dots,13k\) and \(B(x_i)=1-\sigma\) otherwise, and \(y_i=f_b(x_i)\) for \(i=8k+1,\dots,16k\). The latter \(x_i\)'s (and \(y_i\)'s) are associated with \(f_b\) (or with \(b\)). Finally, the sender applies a random re-ordering (i.e. permutation) \(\phi\,:\;[16k]\rightarrow[16k]\) to \(y_1,\dots,y_{16k}\) and send the resulting vector, \(y_{\phi(1)},\dots,y_{\phi(16k)}\), to the receiver.

Upon receiving the ciphertext \(y_1,\dots,y_{16k}\), when having private key \(f^{-1}_r\) (where \(r\in\{a,b\}\)), the receiver computes \(B(f^{-1}_r(y_1)),\dots,B(f_r^{-1}(y_{16k}))\), and outputs the majority value among these bits.

4.2.2. Key Generation

We describe how the keys are generated, based on any common-domain trapdoor system. We use Oblivious Transfer^[?][?] in our constructions. Oblivious Transfer (OT) is a protocol executed by a sender \(S\) with inputs \(s_1\) and \(s_2\), and by a receiver \(R\) with input \(\tau\in\{1,2\}\). After executing an OT protocol, the receiver should know \(s_\tau\), and learn nothing else. The sender \(S\) should learn nothing from participating in the protocol. In particular \(S\) should not know whether \(R\) learns \(s_1\) or \(s_2\). We are only concerned with the case where \(R\) is uncorrupted and non-erasing.

We use the implementation of OT described in [?] (which in turn originates in [?]). This implementation has an additional property, discussed below, that is useful in our construction. For self containment we sketch, in Figure 5, the [?] protocol for OT of one bit.

It can be easily verified that the receiver outputs the correct value of \(\sigma_\tau\) in Step 4. Alsi, if the receiver is semi-honest in the non-erasing sense, then it cannot predict \(\sigma_{3-\tau}\) with more than negligible advantage over ½.¹³ The sender view of the interaction is uncorrelated with the value of \(\tau\in\{1,2\}\). Thus it learns nothing from participating in the protocol.

The important additional property of this protocol is that, in a simulated execution of the protocol, the simulator can learn both \(\sigma_1\) and \(\sigma_2\) by uniformly selecting \(z_1,z_2\in D\) and having the receiver \(R\) send \(f(z_1),f(z_2)\) (in Step 2). Furthermore, if \(R\) is later corrupted, then the simulator can "convince" the adversary that \(R\) received either \(\sigma_1\) or \(\sigma_2\), at wish, by claiming that in Step 2 party \(R\) chose either \((x_1,x_2)=(z_1,f(z_2))\text{ or }(x_1,x_2)=(f(z_1),z_2)\), respectively.

In Figure 6 we describe our key generation protocol. This protocol is valid as long as at least one party remains uncorrupted.

4.2.3. Simulation (Adaptive Security of the Encryption Protocol)

Let \(\epsilon\) denote the combined encryption and decryption protocols, preceded by the key generation protocol.

Protocol \(\epsilon\) is an \((n-1)\)-resilient non-committing encryption protocol for \(n\) parties, in the presence of non-erasing parties.

Let \(P_r\) be the sender and \(P_s\) be the receiver. Recall that a non-committing encryption protocol is a protocol that securely computes the bit transmission function, \(BTR_{s,r}\) in a simulatable way. Let \(\epsilon'\) be a non-erasing protocol for \(\epsilon\). We construct a simulator \(\mathcal S\) such that \(IDEAL_{BTR_{s,r},\mathcal S^{\mathcal A}}(\sigma)\stackrel{d}=EXEC_{\epsilon',\mathcal A}(\sigma)\), for any \((n-1)\)-limited adversary \(\mathcal A\) and for any input \(\sigma\in\{0,1\}\) of \(P_{\mathcal S}\).

The simulator \(\mathcal S\) proceeds as follows. First an invocation of the key generation protocol \(\epsilon_G\) is simulated, in such a way that \(\mathcal S\) knows both trapdoors \(f_a^{-1}\) and \(f_b^{-1}\). (This can be done using the additional property of the [?] Oblivious Transfer protocol, as described above.) For each party \(P\) that \(\mathcal A\) corrupts during this stage, \(\mathcal S\) hands \(\mathcal A\) the internal data held by \(P\) in the simulated interaction. We stress that as long as at least one party remains uncorrupted, the adversary knows at most one of \(f_a^{-1},f_b^{-1}\). Furthermore, as long as \(P_\tau\) remains uncorrupted, the adversary view of the computation is independent of whether \(P_\tau\) has \(f_a^{-1}\) or \(f_b^{-1}\).

Once the simulation of the key generation protocol is completed, \(\mathcal S\) instructs the trusted party in the ideal model to notify \(P_\tau\) of the function value. (This value of \(P_s\)'s input, \(\sigma\).) If at this point either \(P_s\) or \(P_\tau\) is corrupted, then \(\mathcal S\) gets to know the encrypted bit. In this case \(\mathcal S\) generates a true encryption of the bit \(\sigma\), according to the protocol. If neither \(P_s\) nor \(P_\tau\) are corrupted, then \(\mathcal S\) generates the values \(\vec z,\vec x^{(0)},\vec x^{(1)},\phi^{(0)},\phi^{(1)},r^{(0)},r^{(1)}\) as in Lemma 4.7, and lets \(\vec z\) be the ciphertext that \(P_s\) sends to \(P_\tau\) in the simulated interaction.

If at this stage \(\mathcal A\) corrupts some party \(P\) which is not the sender or the receiver, then \(\mathcal S\) hands \(\mathcal A\) the internal data held by \(P\) in the simulated interaction. If \(\mathcal A\) corrupts \(P_s\), then \(\mathcal S\) corrupts \(P_s\) in the ideal model and learns \(\sigma\). Next \(\mathcal S\) hands \(\mathcal A\) the values \(\vec x^{(\sigma)},\phi^{(\sigma)}\) for \(P_s\)'s internal data. If \(\mathcal A\) corrupts \(P_\tau\), then \(\mathcal S\) corrupts \(P_\tau\) in the ideal model, learn \(\sigma\), and hands \(\mathcal A\) the value \(f^{-1}_{\tau^{(\sigma)}}\) for \(P_s\) 's internal data.

The validity of the simulation follows theorem Lemma 4.7 and from the properties of the [?] Oblivious Transfer protocol. \(\quad\quad\blacksquare\).

4.3.1. An Implementation Based on RSA

We first construct the following common-domain trapdoor system. The common domain, given security parameter \(n\), is \(\{0,1\}^n\). A permutation over \(\{0,1\}^n\) is chosen as follows. First, choose a number \(N\) uniformly from \([2^{n-1},\dots,2^n]\), together with its factorization (via Bach's algorithm^[?]). Next choose a prime \(2^n\lt e\lt2^{n+1}\). (This way, we are assured that \(\operatorname{gcd}(e,\operatorname\phi(N))=1\), where \(\operatorname\phi(\cdot)\) is Euler's totient function, even if the factorization of \(N\) is not known.) Let \(f_N(x)=x^e\pmod N\) if \(x\lt N\) and \(f_N(x)=x\) otherwise. With non-negligible probability \(N\) is a product of two large primes. Thus, thus construction yields a collection of common domain permutations which are weakly one-way. Employing an amplification procedure (e.g. [?][?]) we obtain a proper common-domain system.

This common-domain trapdoor system can be used as described in Section 4.2. However, here the key generation stage can be simplified considerably. Observe that it is possible to choose a permutation from the above distribution without knowing its trapdoor. Specifically, this is done by choosing the numbers \(N\) of the different instances of \(f_N\) in the direct way, without knowing their factorization. Thus, the receiver will choose two trapdoor permutations \(f_a,f_b\), where only the trapdoor to \(f_\tau\) (i.e. \(f_\tau^{-1}\)) is known, \(r\in_R\{a,b\}\). Both \(f_a,f_b\) are now sent to the sender, who proceeds as in Section 4.2.1. In a simulated execution the simulator will choose both \(f_a\) and \(f_b\) together with their trapdoors.¹⁴

4.3.2. An Implementation Based on DH

Consider the following construction. Although it fails to satisfy Definition 4.3, it will be 'just as good' for our needs. The common domain, given security parameter \(n\), is a prime \(2^{n-1}\lt p\lt2^n\) where the factorization of \(p-1\) is known. Also a generator \(f\) of \(Z_p^*\) is fixed. \(p\) and \(g\) are publicly known. All computations are done modulo \(p\). To choose a permutation over \(Z_p^*\), choose an element \(v\in_R\mathcal Z^*_{p-1}\) and let \(f_v(x)=x^v\). The public description of \(f_v\) is \(y\stackrel{\Delta}=g^v\). The 'trapdoor' is \(v\stackrel\Delta=v^{-1}\pmod{p-1}\).

This construction has the following properties:

• Although it is hard to compute \(f_v\) if only \(p,g,y\) are known, it is easy to generate random elements \(x\in_R Z^*_p\) together with \(f_v(x)\): choose \(z\in_R\mathcal Z^*_p\), and set \(x=g^z\) and \(f_v(x)=y_z\). (This holds since \(f_v(x)=x^v=g^zv=y^z\).)
• If \(u\) is known then it is easy to compute \(f_v^{-1}(x)=x^u\).
• An algorithm \(A\) that inverts \(f_v\) given only \(p,g,y\) can be easily transformed into an algorithm \(A'\) that given \(p,g,g^\alpha,g^\beta\) outputs \(g^{\alpha\beta}\) (that is, into an algorithm that contradicts the Diffe-Hellman (DH) assumption). Specifically, assume that \(A(p,g,g^v,x^v)=x\). Then on input \(p,g,g^\alpha,g^\beta\), algorithm \(A'\) will run \(A(p,g^\alpha,g,g^\beta)\) to obtain\(g^{\alpha\beta}\).
• It is possible to choose a permutation from the above distribution without knowing its trapdoor. Specifically, this is done by uniformly choosing numbers \(y\in_R Z^*_p\) until a generator is found. (It is easy to decide whether a given \(y\) is a generator of \(Z^*_p\) when the factorization of \(p-1\) is known.)

Note that both in the encryption process and in the simulation it is not necessary to compute the permutations \(f\) on arbitrary inputs. It suffices to be able to generate random elements \(x\) in the domain together with their function value \(f(x)\). Thus, this construction is used in a similar way to the previous one.