3.1. Examples

The protocol presented in this paper relies on the existence of bit commitment schemes satisfying the properties defined above. In this subsection, we give three examples of commitment schemes which could be used in the protocol, namely the Quadratic Residuosity Scheme (QRS), the Jacobi Symbol Scheme (JSS), and the Discrete Log Scheme (DLS), of which DLS has not been used in published protocols before.

In QRS, \(A\)(lice) uses the algorithm \(\Omega\) to select at random two \(m\)-bit primes, \(p\) and \(q\) with \(p\equiv q\equiv -1\pmod 4\). She then puts \(N=pq,\,\)\(R_m^{(0)}\)\(=\)\(R_m^{(1)}\)\(=\mathbb Z_N^*\) and \(S_m\)\(=\Bigg\{x\in\mathbb Z_N^*\,\Bigg|\,\)\(\left(\frac x N\right)\)\(=1\Bigg\}\). She makes public \(N\) and uses for example the zero knowledge protocol from [11] to convince everyone that \(N\) is of the right form. In particular, this implies that -1 is a quadratic nonresidue modulo \(N\) of Jacobi symbol 1. If we define $$f_m^{(b)}(r)=(-1)^br^2\bmod N$$ it is easy to see that a commitment will contain a 1 if and only if the commitment is a quadratic nonresidue modulo \(N\).

In particular, \(N\) is a Blum integer and therefore has the mentioned property that -1 is a nonresidue but must have a Jacobi symbol of 1.

The "hiding" condition above now translates into the well known quadratic residuosity assumption: it is hard, even probabilistically, to distinguish quadratic residues from quadratic nonresidues modulo \(N\) (a formal statement can be found in [10]). Moreover, even with infinite computing power, clearly \(A\) cannot lie about the contents of a commitment.

The opening and comparability properties are easily verified for QRS: \(A\) simply makes public a square root modulo \(N\) of $$(-1)^b\operatorname{BCS}_{A,m}(b,r)\quad \left(\text{resp.}\quad(-1)^{b\oplus b'}\operatorname{BCS}_{A,m}(b,r)\operatorname{BCS}_{A,m}(b',r')^{-1}\right).$$ These proofs will be MKIPs because the commitments were chosen by \(A\) herself at random.

Blinding is also a simple process: having chosen \(b',\,B\)(ob) computes the new commitment as $$(-1)^{b'}s^2\operatorname{BCS}_{A,m}(b,r)=\operatorname{BCS}_{A,m}(b\oplus b',rs),$$ where \(s\) is randomly chosen from \(Z_n^*.\,B\) can show the value of \(b'\) by showing a square root of $$(-1)^{b'}\operatorname{BCS}_{A,m}(b\oplus b',rs)(\operatorname{BCS}_{A,m}(b,r))^{-1},$$ which equals \(s.\,s\) is called the blinding factor.

Also, given two blinded commitments as above, \(B\) can show a square root of $$(-1)^{b'\oplus b''}\operatorname{BCS}_{A,m}(b\oplus b',r')(\operatorname{BCS}_{A,m}(b\oplus b'',r''))^{-1}$$ to convince everyone about the value of \(b'\oplus b''\).

Clearly, \(A\) can open any commitment by using her knowledge of the factors of \(N\) to compute square roots. But it is important to note that it will only be safe for her to do so if she is convinced that she will always be opening blinded forms of commitments chosen by herself. This will be ensured by the construction of our main protocol.

Let's quickly specify an attack for if \(A\) opens a commitment that is not a blinded version of one of her own commitments. Let's say \(A\) has released the commitment \((-1)^br^2\bmod N\); \(B\) pretends to blind it with some identical bit and some value \(t^2\), making it \((-1)^b(-1)^b(rt)^2\equiv(rt)^2\pmod N\). Since \(\mathbb Z_N^*\) is a multiplicative ring, if \(B\) simply chooses an \(s\), there must exist some \(t\) such that \(rt=s\) and therefore such that \(s^2=(rt)^2\). \(B\) can therefore give \(A\) the commitment \(s^2\bmod N\) and, without further information, \(A\) cannot tell the difference between the fake commitment and a real one. If \(A\) opens the commitment, returning that a square root of \(s^2\) is \(x\), there is a 50% chance that \(x\not\equiv\pm s\pmod N\) since all quadratic residues have 4 square roots. $$\begin{align}x^2&\equiv s^2&\pmod N \\ x^2-s^2&\equiv0&\pmod N \\ (x-s)(x+s)&\equiv 0&\pmod N\end{align}$$ Since \((x-s)\not\equiv0\), we have factored \(N\).

In the JSS (first introduced by Blum^[12]), some participant \(B\) chooses a modulus \(N\) of the same form as above, such that the factorization is unknown to \(A\), and convinces her as above that \(N\) was correctly chosen. We then put $$\begin{align}R_m^{(0)}\;&=\;\left\{x\in\mathbb Z_N^*\,\middle|\,\left(\frac x N\right)=1\right\},\\ R_m^{(1)}\;&=\;\left\{x\in\mathbb Z_N^*\,\middle|\,\left(\frac x N\right)=-1\right\},\end{align}\\ \text{and}\quad S_m\;=\;QR(N),$$ where \(QR(N)\) denotes the set of quadratic residues modulo \(N\). Finally, we set $$f_m^{(b)}(r)\;=\;r^2\bmod N,$$ where \(r\in R_m^{(b)}\).

This scheme hides the bits unconditionally: since each square modulo \(N\) has two square roots of Jacobi symbol +1 and two of Jacobi symbol -1, release by \(A\) of \(\operatorname{BCS}_{A,m}(b,r)\) gives away no Shannon information about \(b\). On the other hand, the unforgeability property only holds conditionally here: if \(A\) could factor \(N\), she could lie about the value of \(b\).

JSS also satisfies the comparability property: Given two commitments \(s_1\,=\,\operatorname{BCS}_{A,m}(b,r)\) and \(s_2\,=\,\operatorname{BCS}_{A,m}(b',r'),\,A\) can make public a square root of \(s_1(s_2)^{-1}\) of Jacobi symbol \((-1)^{b\oplus b'}\) to convince everybody about the value of \(b\oplus b'\). Note that this is still information theoretically secure: after having seen a proof that \(b\oplus b'\,=\,1\), say, the two possibilities \((b,b')\,=\,(1,0)\) and \((b,b')\,=\,(0,1)\) remain equally likely, even to someone who knows the factorization of \(N\).

Note that if \(A\) is going to commit to bits using JSS in a multiparty protocol, every participant except \(A\) must supply a different modulus, and when committing to a bit, \(A\) must make public a set of commitments to this bit, one for each modulus supplied. This is to prevent the possibility that \(A\) breaks the unforgeability property by conspiring with somebody who knows the factorizations. This of course means that the other participants must be convinced that the same bit is contained in all commitments in a given set. Fortunately, the construction of our main protocol is such that this automatically ensured whenever JSS is used.

Note also that if absolute certainty is needed about the correctness of the choice of \(N,\,B\) could be required to simply reveal the factorization of \(N\) after the protocol has been executed. It would be too late for \(A\) by then to use this knowledge in the protocol. Another possibility is for \(B\) to prove to \(A\) in zero knowledge that the modulus has the right form. However, all the known proofs of this leave an exponentially small probability that \(B\)'s claim is false, in which case \(A\) would be giving away information about her secrets. Thus it seems that with this scheme, \(A\) will never be quite sure that her secrets have not been betrayed until after it happened!

The next example, the Discrete Log Scheme, solves this problem. Here, \(B\) chooses an \(m\)-bit prime \(p\), a generator \(g\) of \(\mathbb Z_p^*\), and an element \(a\in\mathbb Z_p^*\) at random and reveals them to \(A\). We now put \(R_m^{(1)}\,=\,R_m^{(0)}\,=\,S_m\,=\,\mathbb Z_p^*\), and $$f_m^{(b)}(r)\,=\,a^bg^r.$$

This scheme also hides the bits unconditionally, since the bit contained in a commitment is not uniquely determined, if the random choice made by \(A\) is unknown. Note that if \(p\) is determined such that the factorization of \(p-1\) is known, \(A\) can easily check for herself that \(p\) is a prime and that \(g\) is a generator.

To open a commitment, \(A\) must show the discrete log base \(g\) of $$a^{-b}\operatorname{BCS}_{A,m}(b,r),$$ namely \(r\). It is also easy to see that the unforgeability property holds, assuming that \(A\) cannot find the discrete log of \(a\).

Given two commitments \(\operatorname{BCS}_{A,m}(b,r)\) and \(\operatorname{BCS}_{A,m}(b',r'),\,A\) can prove that \(b\oplus b'=0\) by showing the discrete log of $$\operatorname{BCS}_{A,m}(b,r)(\operatorname{BCS}_{A,m}(b',r'))^{-1}$$ and to show that \(b\oplus b'=1\), she shows the discrete log of $$a^{-1}\operatorname{BCS}_{A,m}(b,r)\operatorname{BCS}_{A,m}(b',r').$$ Once again, it is easy to see that \(A\) cannot make a false claim about \(b\oplus b'\) unless she can find the discrete log of \(a\).

An additional advantage of DLS compared to JSS is that it is not necessary in a multiparty application that all participants different from \(A\) choose their own instances, and that \(A\) then must commit to a bit "in parallel" using all the published instances. Since there is no trapdoor present in DLS, all participants can collaborate in choosing \(p,\,g\) and \(a\) using some multiparty coinflipping protocol.

4.1. Correctness and Security

The definitions in this section are straightforward generalizations of the definition of "zero knowledge proof systems" found in [13]. This becomes clear if one takes a slightly different point of view of the situation where a prover convinces a verifier about the membership of a string \(x\) in an NP-language \(L\).

In fact the prover and the verifier are doing an interactive computation, where only the prover supplies input, namely a certificate of membership for \(x\). The notion of correctness of the protocol they execute corresponds to the fact that we have a proof system: we want the protocol to produce the correct output of the computation, namely "accept" if indeed the prover put in a valid certificate of membership for \(x\). The notion of security corresponds to the fact that the proof system is zero knowledge: we want the verifier to gain nothing useful about the secrets of the prover, other than the fact that \(x\) is in \(L\).

If we model the computation needed to verify membership for \(x\) by a boolean circuit \(C\), it is clear that this is just a special case of the general problem addressed in this paper.

We allow \(C\) to be a probabilistic circuit, i.e. take as input a number of bits chosen uniformly from \(\{0,1\}\). Thus, given as inputs \(I=\)\((ip_1,\dots,ip_n)\)\(,\,C\) determines a probability distribution \(OP_I^C\) on the output. We assume for simplicity that the output is public, i.e. the same output string will appear on the output tape of any participant following the protocol (the generalization to different (private) outputs is easy and will be discussed later). Given a choice of inputs as above, we let \(OP_{I,m}^{prot}\) denote the probability distribution according to which the output string of a participant following the protocol is distributed, when the protocol is executed with security parameter value \(m\) and no cheating is detected. We would like this distribution to be essentially equal to \(OP_I^C\). In other words, the only way for (a set of) dishonest participant(s) to prevent the correct result from being computed is to stop the protocol, e.g. by deliberately sending an incorrect message.

We let \(OP_I^C(op)\) (resp. \(OP_{I,m}^{prot}(op)\)) denote the probability that the binary string \(op\) is produced as output.

A protocol is said to be correct if for any choice of inputs \(I=\)\((ip_1,\dots,ip_n)\), and any binary string \(op\) and constant \(c,\) $$|OP_I^C(op)-OP_{I,m}^{prot}(op)|\lt m^{-c}$$ for all sufficiently large \(m\).

A conspiracy is a subset \(X\) of \(\{P_1,\dots,P_n\}\) with \(|X|\lt n\). The machines in a conspiracy may follow any (polynomial time) program, and they may establish private communication channels to share all the information available to them.

Intuitively, we will consider the protocol secure if no conspiracy will learn more from the protocol than what could already have been inferred from the output of the computation and the part of the input known to the conspiracy.

To state this more formally, we need some definitions:

The binary string which is that concatenation of all messages sent during an execution of the protocol is called a protocol conversation.

Let \(ra\) be a binary string containing as many bits as there are random input bits to \(C\). Then by \(f_C(ip_1,\dots,ip_n,ra)\) we denote the output of \(C\) resulting from inputs \((ip_1,\dots,ip_n)\) and random choice \(ra\).

We let \(P_{prot}^{(m)} (ip_1,\dots,ip_n,ra)\) denote the probability distribution according to which a protocol conversation with security parameter \(m\) and inputs (\(ip_1,\dots,ip_n\)\(,\)\(ra\)) is distributed.

Note that this distribution is conditional on the program followed by the machines in \(X\), i.e. the conspiracy's strategy. Note also that the definition talks about the inputs of machines in \(X\). This is not necessarily a meaningful concept: nothing prevents a dishonest participant from pretending that the contents of its input tape are different from what they are in fact. This "problem" is easily solved, however, if we jump ahead in the protocol description a little: each participant must publish bit commitments which determine a particular choice of input. We therefore define the input of a participant to be the bit string committed to during the execution of the protocol.

A simulator for \(X\) is a polynomial time Turing machine \(M_X\) which, on input \(\left(m, f_C(ip_1,\dots,ip_n,ra), \left\{ip_i,\,\middle|\,P_i\in X\right\}\right)\) will generate a protocol conversation distributed according to the distribution \(P_{M_X}^{(m)}\left(f_C(ip_1,\dots,ip_n,ra), \left\{ip_i,\,\middle|\,P_i\in X\right\}\right)\).

The protocol is said to be secure against the conspiracy \(X\) if there exists a simulator for \(X\), \(M_X\), such that for any \((ip_1,\dots,ip_n)\) and \(ra\), the two ensembles of probability distributions $$\left\{P_{M_X}^{(m)}\left(f_C(ip_1,\dots,ip_n,ra), \left\{ip_i,\,\middle|\,P_i\in X\right\}\right)\right\}_{m=1}^\infty$$ and $$\left\{P_{prot}^{(m)}(ip_1,\dots,ip_n,ra)\right\}_{m=1}^\infty $$ are polynomially (in \(m\)) indistinguishable.

We assume that the reader is familiar with this notion. For details, refer to [13].

There is also soon to be a tutorial on proof of zero-knowledge through simulation.

The protocol is said to be secure if it is secure against any conspiracy.

This definition means that no matter which type of hostile behavior is exhibited by \(X\), the private inputs of all honest participants and the random inputs are optimally protected. But note that providing the protocol secure under this definition does not exclude the possibility that a conspiracy, by stopping the protocol in some clever way, could find out about the output, while preventing honest participants from getting at it. The basic protocol as described in Section 5 already offers protection against this, but a lot of variations on the theme are possible. More details will be given in Section 6.

This concept of a conspiracy learning the output while stopping the other parties from learning the output is known in the literature as fairness.

Transformations of Truth Tables

Our protocol works with "transforms" of truth tables. Basically, a transform of a truth table \(T(G)\) is just a row-permuted version of \(T(G)\) with the last column changed and some extra (encrypted) information about the transformation included.

Let \(g\) be a gate in \(C\) with \(t\) input wires. For \(i=1\cdots n\), we define an \(i\)-transform \(T\) of \(T(G)\) to be a \((t+1)\) by \(2^t\), 0-1 matrix with a list of bit commitments attached to each row and each column. The list attached to row \(l\) is called \(rlist(l,T)\). The list attached to column \(k\) is called \(clist(k,T)\).

Each list contains one commitment from each participant \(P_j\), for which \(j\leq i\), except \(clist(k,T)\), when the \(k\)-th column corresponds to an input wire in some \(I_j\). These lists are empty if \(j\gt i\), and contain one bit commitment from \(P_j\) if \(j\leq i\).

By \(rsum(l,T)\) (resp. \(csum(k,T)\)), we denote the XOR sum of all bits committed to in \(rlist(l,T)\) (resp. \(clist(k,T)\)). The sum of an empty list is defined to be 0.

A 0-transform of \(T(G)\) is defined to be simply \(T(G)\) itself.

Most of the work done in the protocol by \(P_i\) will consist of receiving \((i-1)\)-transforms and from these creating \(i\)-transforms. We require that there is some specific relation between a truth table \(T(G)\) and its transforms used in the protocol. When this relation holds, the transform is said to be valid. A valid transform can be seen as an encrypted version of \(T(G)\): the rows are permuted, and each column is XORed with an independently chosen bit. In addition to this, the last entry in each row is XORed with an independently chosen bit. The attached lists of bit commitments (when opened) contain complete information about how the transform was constructed. More specifically, we have the following:

A valid \(i\)-transform \(T\) of \(T(G)\) is an \(i\)-transform of \(T(G)\) which satisfies that:

There exists a permutation \(\sigma\) of \((1,\dots,2^t)\) such that: $$\begin{split} T_{lk}&=T(G)_{\sigma(l)k}\oplus csum(k,T),\quad\,&\mbox{if}\;k\lt t+1,\\ T_{lk}&=T(G)_{\sigma(l)k}\oplus csum(k,T)\oplus rsum(l,T),\quad &\mbox{if}\;k= t+1, \end{split} $$ where \(T_{lk}\) (resp. \(T(G)_{lk}\)) is the entry in the \(l\)-th row and \(k\)-th column of \(T\) (resp. \(T(G)\)).

6.1. The Encryption Phase

The procedure Transform Circuit below is iterated once by each participant, such that the \(i\)-th iteration is executed by \(P_i\). After each iteration, the protocol Check Transformation is executed to verify that the preceding iteration of Transform Circuit has been performed correctly. The input to the first iteration will be the truth tables in the original circuit.

The interactive proof demonstrating that every \(T\) was created according to the protocol proceeds as follows:

For every \(i=1\cdots n\), the probability that \(P_i\) has cheated (i.e. sent incorrect messages) anywhere in the protocol is smaller than \(m^{-c}\) for any constant \(c\) and all sufficiently large \(m\). If no cheating occurs, then the encryption phase ends with \(P_n\) outputting a valid \(n\)-transform of every truth table in \(C\).

It is not hard to see that if at least one iteration in the Check Transformation protocol, \(P_i\) was able to give satisfying answers in both steps 3 and 4, and if \(P_i\) was not able to change the contents of his bit commitments, then \(T\) must have been correctly constructed. This and the unforgeability property of all bit commitment schemes used suffice to prove the first statement. The second follows from the obvious fact that if \(T\) was created correctly from \(S\) in the Transform Circuit protocol, then \(T\) is valid if \(S\) was valid.

If all participants use QRS for bit commitments, then the unforgeability property holds unconditionally for all participants, which means that the probability of undetected cheating will be at most \(2^{-m}\).

Intuitively, the Check Transformation protocol is secure from \(P_i\)'s point of view because all the other participants never see anything but random "copies" of \(S\) or \(T\), which they could also have produced themselves. All other participants will therefore be convinced that \(T\) was correctly constructed, but will learn nothing more about \(T\). A formal proof can be found in Section 6.3.

6.2. The Computation Phase

At the end of the encryption phase, \(P_n\) has output a set of \(n\)-transforms of the truth tables in \(C\). This set will be called \(C^*\).

Let \(w\) be an input wire in \(C\) connecting into the gate \(G\), and suppose \(w\) corresponds to column \(k\) in \(T(G)\). Let \(T^*\) be the \(n\)-transform of \(T(G)\) contained in \(C^*\).

As the first step in the computation phase, encrypted input bits are specified for each such \(w\). This is done as follows: if \(w\in\) \(R\), then the mutually trusted source of random bits selects a bit \(b_w\), which is made public; if \(w\in\)\(I_i\) for some \(i,\,P_i\) reads a bit \(b\) in \(ip_i\) corresponding to \(w\) from its private input tape, and then makes \(b_w=b\oplus b_i(k,T^*)\) public.

To describe the next steps in the computation phase, we need to define the notion of computations in \(C^*\).

By a computation \(\Gamma^*\) in \(C^*\), we mean a selection of exactly one row in each \(n\)-transform in \(C^*\).

A computation \(\Gamma^*\) is said to be consistent, if the following is satisfied: Suppose output column \(k_1\) in the transform \(T^*_1\) is connected with column \(k_2\) in the transform \(T_2^*\), and let \(\Gamma^*(k_1)\) and \(\Gamma^*(k_2)\) be the entries selected by \(\Gamma^*\) in the two columns then $$\Gamma^*(k_1)\oplus rsum(l_1,T_1)\;=\;\Gamma^*(k_2),$$ where \(l_1\) is the index of the row selected by \(\Gamma^*\) in \(T_1^*\).

The intuition behind these rather technical looking definitions is very simple: if we assume that all transforms in \(C^*\) are valid, then the selection of a row in a table \(T^*\) corresponds to selecting a row in the original truth table, under the product of all row permutations chosen for \(T^*\) by the participants. Therefore, a computation in \(C^*\) corresponds to a computation in \(C\). Moreover the consistency condition on a computation in \(C^*\) just says that if we look at the string of bits selected in the computation and "remove" all layers of encryption, then the consistency condition as defined in Section 5 holds for the computations in \(C\) (note that by construction of the \(n\)-transforms in \(C^*,\,csum(k_1,T_1^*)=csum(k_2,T_2^*)\)). Formally, we have the following:

Given an \(n\)-transform \(T^*\) in \(C^*\), let \(\sigma_i\) be the row permutation chosen by participant \(P_i\) for \(T^*\). If \(\Gamma^*\) is a computation in \(C^*\) selecting row \(l\) in \(T^*\), then we define the corresponding computation \(\Gamma\) in \(C\) by selecting row \((\sigma_n\cdots\sigma_1)^{-1}(l)\) in the original truth table.

Let \(\Gamma^*\) be a computation in \(C^*\) and suppose all transforms in \(C^*\) are valid. Then the corresponding computation \(\Gamma\) in \(C\) is consistent if and only if \(\Gamma^*\) is consistent.

The rest of the protocol is now just an algorithm which constructs a consistent computation in \(C^*\) from the input as specified above.

6.3. Proofs of Correctness and Security

Before starting on this section, the reader is well advised to review the definitions of correctness and security given in Section 4.1.

Using the results proved in preceding sections, it is now not hard to prove:

The protocol is correct, as defined in definition 4.1.

First note that for each input wire \(w\) in \(R\), the input bit given to \(C\) is the XOR sum of one bit chosen by the mutually trusted random source, and one bit chosen by each participant (namely the bit committed to in the \(clist\) corresponding to \(w\)). By Lemma 6.2, this means that the conditional probability distribution of the output of the protocol assuming that no cheating has occurred, is exactly equal to the "right" probability distribution \(OP_C^I\), for any choice \(I\) of inputs. The theorem now follows from Theorem 6.1 and elementary probability theory.

To show that the protocol is secure, we assume the existence of some conspiracy \(X\). We must then exhibit a simulator \(M_X\) for \(X\) and prove that its output is polynomially indistinguishable from an actual proof conversation. Only informal descriptions will be given, we trust that this will make the proofs easier to understand, and that the reader will have no trouble in filling in the necessary details.

We begin with the description of the simulator \(M_X\):

Recall that \(M_X\) is given as input the security parameter value \(m\), the output of a "real" computation \(f_C(ip_1,\dots,ip_n,ra)\), and the part of the input "known" to \(X\) \(\{\)\(ip_i\)\(|\,P_i\in\)\(X\)\(\}\). In addition to this, \(M_X\) is of course allowed to use the machines in \(X\) in any (feasible) way it likes. We will describe the algorithm of \(M_X\) as a simulated protocol execution, where the participants in \(X\) act "as themselves" and \(M_X\) plays the parts of all other participants.

\(M_X\) starts by putting \(ip_i\) on the input tape of \(P_i\) for every \(P_i\in\)\(X\). Also, the random tapes of all machines in \(X\) are filled in using \(M_X\)'s own random tape. This means that all the machines in \(X\) are deterministic from now on.

For simplicity, we assume that all participants use QRS for bit commitments. \(M_X\) therefore chooses a modulus \(N_i\) for all participants \(P_i\) not in the conspiracy, while the participants in \(X\) choose their own moduli. Although this means that \(M_X\) in fact knows some of the factorizations involved, it is of course essential that this is not used in the simulation!

Next, \(M_X\) executes a simulation of the proof that \(N_i\) is a Blum integer, for every \(i=1\cdots n\). When \(i\) is such that \(P_i\in\)\(X\), \(P_i\) can be used directly as the prover, otherwise the simulation from [11] can be used.

We now come to the executions of the Transform Circuit procedure. If \(P_i\in\)\(X\), then the \(i\)th iteration of this procedure is replaced by an execution of the procedure Simulate Conspiracy below, otherwise the procedure Simulate Honest Participant is used.

In the computation phase, \(M_X\) lets all machines in \(X\) specify their encrypted choice of input bits, and specifies randomly chosen bits for all other participants. It is now easy to see that the Construct Computation procedure can be executed exactly as in the protocol: by the remarks in the Simulate Conspiracy procedure, \(M_X\) has all the information it needs to open all bit commitments from participants not in \(X\).

Why does this simulation look just like a "real" protocol conversation? Consider the set of messages sent by participant \(P_i\) in the protocol, and suppose \(P_i\) is honest. It is easy to see that the bits shown "in clear" in the messages will be distributed in exactly the same way in the simulation as in an actual protocol conversation. The difference between simulation and protocol therefore lies only in the distribution of the bits hidden in \(P_i\)'s bit commitments. It is intuitively clear that to notice this difference, a distinguisher would need the ability to tell the difference between commitments containing 0's and those containing 1's. But by assumption, this cannot be done efficiently. This argument is formalized below.

The protocol is secure.

It remains to be shown that the output of the simulator described above is polynomially indistinguishable from an actual protocol conversation. For simplicity, we will only do this in the case where \(n-1\) participants conspire against one honest participant \(P_i\). Cases with smaller conspiracies are in principle similar and introduce only technical differences.

Recall that a polynomial time distinguisher \(\Delta\) is a probabilistic polynomial time algorithm which takes as input a binary string and gives a one bit output. Let \(p_{prot}(m)\) be the probability that \(\Delta\) outputs a 1 when given an actual protocol conversation with security parameter \(m\) as input. Similarly, \(p_{sim}(m)\) is the probability that \(\Delta\) outputs a 1 when given a simulated conversation created as above. By way of contradiction, we assume that there exists a choice of inputs (\(ip_1,\dots,ip_n\),ra) which will result in distinguishable protocol and simulated conversations, i.e. there exists a constant \(c\), such that $$\left|p_{prot}(m)-p_{sim}(m)\right|\;\gt\;m^{-c}$$ for infinitely many \(m\).

Below, we will derive a contradiction with the quadratic residuosity assumption by showing how to use \(\Delta\) to construct an algorithm that will distinguish quadratic residues from nonresidues modulo a Blum integer \(N\), whenever \(N\) has \(m\)-bit prime factors, and \(m\) satisfies the above equation. Let us therefore assume that we are given an element \(x\) in \(Z_N^*\) of Jacobi symbol 1.

Below, we will describe a polynomial time Turing machine \(M_X'\), which on input (\(ip_1,\dots,ip_n\),ra) and \(x\) chosen as above will generate a conversation. This conversation will be a "real" protocol conversation if \(x\) is a quadratic residue, and it will be distributed exactly as a simulated one if \(x\) is a quadratic nonresidue.

The description of \(M_X'\) is easy, based on the algorithm of \(M_X:\,M_X'\) assigns \(N\) as modulus to \(P_i\), and then works exactly as \(M_X\), except for steps i and ii in the Simulate Honest Participant procedure. In step i, \(M_X'\) will: for each commitment placed by \(P_i\) in an input column list choose a bit \(b\) at random and multiply the commitment by \(x^b\). To see why this is done, observe that in a real protocol conversation the bits used in the (encrypted) computation and the bits contained in column lists are correlated: they always XOR together to the bits used in the unencrypted computation. If \(x\) is a quadratic nonresidue, this correlation is destroyed by the multiplications by \(x\), corresponding to the fact that we should be producing a simulated conversation in this case. The resulting transformation, however, is no longer valid. Since both simulation and protocol conversations produce valid transforms for non-output gates, we have to do something about this. But it is not hard to see that the correctness of the transform can be ensured by also multiplying appropriately chosen commitments in row lists and output column list by \(x\). Note that \(M_X'\) will know how to do this, since it knows exactly how every transform was computed. Finally in step ii, the multiplications by -1 are replaced by multiplications by \(x\).

In the computation phase, \(M_X'\) specifies inputs for \(P_i\) according to the protocol, i.e. as if the \(x\)'s had not been multiplied in. The reader may have observed that a problem could arise here: to complete this phase, \(M_X'\) must be able to open some of the commitments from \(P_i\) placed in row lists. But this is of course impossible if the commitment has been multiplied by \(x\). Note, however, that since all inputs are known to \(M_X'\), it is known which rows will be used in the computation in \(C\), and therefore it can be predicted which rows will be used in the encrypted computation. This, together with the observation that the necessary adjustments can always be done while leaving at least one row untouched, solves the problem.

Now observe that, if \(x\) is a quadratic residue, multiplying a commitment by \(x\) does not change the bit contained in the commitment, while if \(x\) is a quadratic nonresidue, the bit is complemented. Using this fact, it is straightforward to check that the claim above about the output of \(M_X'\) holds.

Let \(p_{prot}(m\,|\,N)\) be the probability that \(\Delta\) outputs a 1 when given as input a protocol conversation in which \(P_i\) chooses \(N\) as modulus. \(p_{sim}(m\,|\,N)\) is defined similarly. An easy calculation will show that the equation above implies $$\left|p_{prot}(m\,|\,N)\;-\;p_{sim}(m\,|\,N)\right|\;\gt\;m^{-c+1}$$ for infinitely many \(m\) and for more than a negligible (i.e. polynomial) fraction of the possible choices of \(N\). Elementary probability theory now shows that if \(x\) is a randomly chosen element in \(\mathbb{Z}_N^*\) of Jacobi symbol 1, then we can guess whether \(x\) is a quadratic residue with an advantage polynomially larger than ½, whenever this derived equation holds. But this contradicts the hiding property of QRS, i.e. the intractability assumption on the quadratic residuosity problem.

If \(P_n\) is honest and uses DLS for bit commitments, then the protocol releases no information in the Shannon sense about the private input of \(P_n\) and all intermediate results in the computation.

Since DLS hides the bits unconditionally, it is easy to see that the protocol provides even a conspiracy consisting of all other participants with nothing more than the string of input bits and intermediate results, encrypted under a true one-time pad.

A similar result holds if \(P_n\) uses JSS, assuming that the moduli used are of the right form. Since the known interactive proofs of this would leave a small probability that this is not so, \(P_n\) would on the average be releasing an exponentially small amount of information when using JSS.

7.1. Private Outputs

How can we make some of the output bits private to a participant \(P_i\)? First, note that this problem could always be solved by rewriting the circuit, such that each of the output bits in question were XORed with a bit chosen at random by the participant.

With out protocol, however, this is not needed: we can just modify the protocol such that \(P_i\) is not required to open his or her bit commitments corresponding to the output wires in question. The proof of security could easily be modified to take this into account: just note that if some output bits are private to a participant not belonging to a conspiracy, then the simulation can be done without knowing these bits.

This is important because, since the conspiracy does not learn those secret outputs, they cannot use the bits of those outputs in their protocol. As mentioned, they don't need them.

7.2. Simultaneous Release of the Output

An obvious strategy for a set of dishonest participants would be to try stopping the protocol early in such a way that this conspiracy could find out about the output while preventing honest participants from getting it. To solve this problem in general, one could just execute a set of coordinated instances, such that the input was constant over all rounds, while the circuit was rewritten such that exactly one bit of the result was computed in each instance.

Note, however, that our basic protocol already implements a bit by bit release, since the "encryptions" of the output columns are opened for one column at a time. Thus, each participant will never have more than a one bit advantage over any other participant. Also this statement could be incorporated into the formal security proof: loosely speaking, if the protocol stops without computing the complete result, then the simulation can be done without knowing all output bits.

If simultaneous release is to be combined with private outputs, however, then a bit by bit release does not make sense because the private outputs may have different lengths. We propose instead the following solution, the basic idea of which was first introduced by Yao in [1]: The parties agree on a probabilistic circuit, which will produce as output an instance of a bit commitment scheme based on a trapdoor one-way function, e.g. an instance of QRS, together with the trapdoor information. Our basic protocol can now be used to do a computation in this circuit. The parties open the specification of the instance, such that commitments can be computed, but keep the trapdoor closed. In the case of QRS, this would mean that a public modulus has been computed, but its factorization is still unknown to everyone. Since all coin flips in the computation are secret, no participant can compute the trapdoor information by himself. The parties now go back to the original circuit and do the computation, using the bit commitment instance computed above for all commitments in output column lists. When this is done, the trapdoor information is opened, bit by bit, which is possible by above remarks. Using Yao's terminology, this is a fair protocol because all participants need exactly the same information in order to get their share of the output.

7.3. Other Special Requirements

Since our basic protocol protects not only the inputs, but also all intermediate results, a variety of special properties can be obtained by rewriting the circuit. For example, the result could be distributed only to a secret subset of users, the subset being chosen at random or based on the result. Also, a secret permutation could be applied to the private output of some participant to hide the order in which that participant obtains his or her output bits. This could be important, e.g. in the implementation of a game such a poker.

7.4. Verifiability

Is it possible for a non-participant to check from, say, a recording of all messages sent in the protocol that the result computed is a correct one? It is clear that such a check cannot be possible without interacting with the participants, since otherwise the protocol could not be minimum knowledge with respect to the private inputs: recall that there should be no way for anyone to tell whether presented with a genuine protocol conversation or a simulated one. But this is exactly what we would be asking the non-participant above to do!

With interaction, however, checking is easy: all participants could be asked to prove once again using the Check Transformation protocol that they had computed valid transforms. Then all the computation phase could be checked without interaction.

7.5. Fault Recovery

In our basic construction, there is not much one can do short of stopping the protocol if some participant sends incorrect messages or just stops completely. In the recent literature, a number of techniques have been proposed for recovering for such situations.

Under the assumption that the majority of users are honest, [2] propose to verifiably secret share the secret inputs of all participants. In the event of a fault, a majority of users would recover all the secrets of the participant who stopped, and complete the computation. Thus, it is assumed by definition that all honest participants will always send the messages they are supposed to. This hardly seems a realistic assumption, however: in practice, almost all faults may occur by accident, or even worse, as a result of dishonest participants sabotaging honest ones to reveal their secrets!

Galil, Haber, and Yung^[3] propose instead a secret sharing in two levels: first, for each secret bit of a user, the user distributes one "XOR share" to each of the other participants, where the exclusive-or of these XOR shares is the original secret bit. The XOR shares are then verifiably secret shared. Recovery in now possible by reconstructing the XOR shares held by the stopped participant, which has the effect of preserving that participant's privacy.

Our protocol could easily be adapted to include the procedure of [3]: In case QRS is used, participant \(P_i\) would first commit to \(ip_i\), and then distribute XOR shares of the factorization of his or her modulus to the other participants. If \(P_i\) stops working, any majority of users could reconstruct the XOR shares of the factorization of \(P_i\)'s modulus, and use instances of our basic protocol to simulate \(P_i\): open his commitments as needed, etc.

In addition to this, the techniques presented in [14] can be used to add flexibility to the protocol. Here, it is shown how to change the quorum, i.e. the number of participants necessary to reconstruct the secret, during the protocol. This can be useful in applications, where it can be assumed that almost all faults occur by accident, because of breakdown of communication lines, etc. In this case, it may be desirable to keep the ratio between the quorum and the number of remaining participants constant.

7.6. The Possibility of Further Generalizations

From an intuitive point of view, it may seem unnatural that only one participant can be unconditionally protected. Why not try to devise a protocol where any subset of the participants could have this option?

To understand this question better, consider the All-or-nothing-disclosure problem (ANDOS).

Also known as one-of-\(n\) oblivious transfer.

In this problem, party A(lice) possesses a number of secrets, of which she is willing to disclose exactly one to B(ob). B would like to be able to choose which secret to get, without disclosing to A which secret he is interested in.

Clearly, ANDOS is just a special case of the general computation problem. Furthermore, the folklore of the subject has it that for fundamental information theoretical reasons, a two party ANDOS cannot be implemented such that the secrets of both parties are unconditionally protected. Informally, this is so since, if A is unconditionally protected, the messages she sends must contain enough Shannon information to determine exactly one of her secrets. But this must then be the secret B learns, which means that he is anything but unconditionally protected!

Although we do not yet have a formal proof that this last claim is true, it certainly seems that there is little hope of achieving the generalization described above.

Under different assumptions, however, it is possible to get unconditional security for all participants. In [16], it is shown how to do this using no cryptographic assumptions, in a model where there exists an unconditionally secure secrecy channel between every pair of participants, and where at least two thirds of the participants will follow the protocol.

On the positive side, it should be noted that in joint work with Claude Crépeau, we have recently shown that our basic protocol can be made to work, based only on the assumption that a one-way function exists, and that there is a protocol solving the ANDOS problem: Clearly, bit commitments are possible if one-way functions exist, and the comparability property can always be satisfied using the fact that all NP-statements can be proved in zero knowledge (although using very inefficient protocols). The idea is now to use a protocol for ANDOS to get something which will replace the blinding property: Notice that when participant \(P_i\) blinds other participants' commitment, the basic fact used in the protocol is that \(P_i\) knows the XOR sum of the bit contained in the original commitment, and the one contained in the blinded version. It will therefore be sufficient if that participant can learn a set of these XOR relations by doing an ANDOS protocol with each \(P_j\) with \(j\lt i\).

The fact that ANDOS can be based on the existence of a trapdoor one-way function^[15] then implies that our protocol can also be based only on a trapdoor one-way function. The resulting protocol would have the same property as the one of [3] which is based on the same assumption, namely that only one trapdoor function would have to be generated for each participant, while the solution in [2] requires generation of \(\operatorname O(n^2)\) functions.