<p><em>New answer (10/24):</em> I think the following paper provides an elegant and efficient solution to your problem:</p>

<ul>
<li><a href="http://crypto.stanford.edu/~dabo/pubs/papers/2dnf.pdf" rel="nofollow">Evaluating 2-DNF Formulas on Ciphertexts</a>, Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.</li>
</ul>

<p>They show how to build a public-key encryption algorithm $E(\cdot)$ with the following two useful properties:</p>

<ul>
<li><p><em>Additively homomorphic.</em> Given $E(x)$ and $E(y)$, anyone can compute $E(x+y)$.</p></li>
<li><p><em>Can multiply (once).</em> Given $E(x)$ and $E(y)$ (neither of which was generated as a result of a multiplication operation), anyone can compute $E(x \cdot y)$.  You can use the result in addition operations, but you cannot use it in any multiplication operations (the result of a multiplication is tainted, and tainted values cannot be used as the input to another multiplication).</p></li>
</ul>

<p>The consequence is that, given a <em>quadratic</em> multivariate polynomial $\Psi(x_1,\dots,x_n)$, and given $E(x_1),\dots,E(x_n)$, anyone can compute an encryption of $\Psi(x_1,\dots,x_n)$.  This is super-useful for your situation.</p>

<p>In particular, in your situation, we can form the polynomial
$$\Psi(b_1,b_2,\dots,b_N) = \sum_{i \ne j} [b_i (1-b_j)].$$
Note that this is a quadratic multivariate polynomial, so given all of the $E(b_i)$'s, anyone can compute $E(\Psi(b_1,\dots,b_N))$.  Also note that $R=\Psi(b_1,\dots,b_N)$, so we're trying to compute exactly the value of this polynomial.</p>

<p>This suggests a natural protocol for your problem, using a threshold version of the encryption scheme in the paper referenced above:</p>

<ul>
<li>Everyone jointly generates a public/private keypair for a threshold version of this scheme, such that the public key is known to all but  the private key is shared among everyone (it requires cooperation of all $N$ parties to decrypt a ciphertext encrypted under this public key).  The public key is broadcast to all $N$ participants.</li>
<li>Each participant $i$ computes $E(b_i)$ and broadcasts $E(b_i)$ to all other participants.  Everyone checks that this has been done honestly.</li>
<li>Each participant computes $E(R) = E(\Psi(b_1,\dots,b_N))$ using the homomorphic properties of this encryption scheme and knowledge of $E(b_1),\dots,E(b_N)$.  Everyone checks that they got the same value.</li>
<li>The $N$ participants jointly use the threshold decryption protocol to recover $R$ from $E(R)$.  (Note that they will only apply the threshold decryption protocol to this one ciphertext; the honest participants will refuse to participate in decrypting any other ciphertext.)</li>
<li>Everyone proves somehow (maybe via ZK proofs) that they performed each step correctly.</li>
</ul>

<p>You'd have to fill in some details, but I bet you could expand this sketch/outline to get a protocol that would solve your problem efficiently and securely.</p>

<hr>

<p><em>My old answer:</em></p>

<p>I'd still look some more at a secure multiparty protocol for computing the sum $S = \sum_j b_j$.</p>

<p>The only way that this falls short of your scheme is it reveals one additional bit: it reveals whether $S&lt;N/2$ or not.  Does that one bit of information matter in your setting?</p>

<p>You say the sum $S$ is sensitive in your application.  I hope you are aware that revealing the value $R$ reveals $S$ up to two possibilities (i.e., given $R$, we can compute a value $Q$ such that $S \in \{Q,N-Q\}$).</p>

<p>If you absolutely must conceal this information, here is a different approach that you might be able to make work.  For each pair of parties $i,j$, securely compute $E(c_{i,j})$ where $c_{i,j} = b_i \oplus b_j$, $\oplus$ is the xor operation, and $E$ is some sort of additively-homomorphic encryption scheme.  Then you might be able to compute $\sum_{i&lt;j} c_{i,j}=R$ from this. There are some details to work out and the threat model may not be what you were hoping for, but it's possible you might be able to make something like this work.</p>

CC BY-SA 3.0
2012-10-24T18:43:11.347Z
that is a very interesting idea. though it does not produce the production exactly, using xor actually conceal the info whether it is 0 or 1. One problem though, is xor computed in plaintext in the scheme? any secure computation for xor?
Richard
CC BY-SA 3.0
2012-10-24T19:42:23.157Z
@Richard, my thought was that you might be able to use two-party secure computation: party $i$ has input $b_i$, party $j$ has input $b_j$, and they want to jointly compute $E(c_{i,j})$ where $c_{i,j}=b_i\oplus b_j.$ This can be done (without computing xor in plaintext) using standard methods for 2-party secure computation. However, there's something subtle related to the threat model which I haven't fully thought through (what if party $i$ is malicious but party $j$ isn't?), and there'd need to be some way to force, say, party $i$ to use the same $b_i$ value in all such interactions.
D.W.
CC BY-SA 3.0
2012-10-23T22:46:03.487Z
2012-10-24T20:13:43.210Z
2012-10-24T20:13:43.210Z
D.W.
<p>This answer is about feasible solutions based on homomorphic encryption that is NOT fully-homomorphic, as the latter may be extremely inefficient (if there are efficient fully homomorphic cryptosystems that are comparable with those provided below in terms of efficiency, I'd be glad to hear about them).</p>

<p>Since you only need one multiplication then there are solutions that are potentially less expensive than fully homomorphic encryption: [1] and [2]. The latter works on encrypted bit-decompositions of the input so it will need a bit-decomposition protocol like [3] and [6], but the former works on whole values. Just for completeness, the former has been extended to $d$-operand multiplication in [4], even though the OP may not need this. These solutions are non-interactive and should work in the two-party case. </p>

<p>If you have more than two parties and could afford some interaction then [5] provides a "secure multiplication gate" which is potentially more efficient and allows unbounded number of multiplications. It works basically by converting the homomorphically-encrypted values to some sort of secret-sharing, multiplies the result (interactively), then convert it back to homomorphic encryption.</p>

<p>[1] <a href="http://www.springerlink.com/content/wtt5caxkr94laxkg/" rel="nofollow">Evaluating 2-DNF Formulas on Ciphertexts</a></p>

<p>[2] <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=814630" rel="nofollow">Non-interactive cryptocomputing for NC1</a></p>

<p>[3] <a href="http://www.springerlink.com/content/m17u3nl46656jn1u/" rel="nofollow">Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation</a></p>

<p>[4] <a href="http://www.springerlink.com/content/8031u1u12p01276u/" rel="nofollow">Additively Homomorphic Encryption with d-Operand Multiplications</a></p>

<p>[5] <a href="http://www.springerlink.com/content/bkq0y15k554l6ybg/" rel="nofollow">Multiparty Computation from Threshold Homomorphic Encryption</a></p>

<p>[6] <a href="http://www.springerlink.com/content/dvj5507116v88429/" rel="nofollow">Efficient Binary Conversion for Paillier Encrypted Values</a></p>

CC BY-SA 3.0
2012-02-26T01:02:23.113Z
To be honest, I fail to see the connection of this answer to the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-26T01:10:57.803Z
@TsuyoshiIto: This answer lists a few references that could be used to provide "secure computation for multiplication", and are especially tailored for the formula the OP provided which includes only one multiplication. It also lists relatively 'efficient' methods as per the OP's request. I actually fail to see your objection at all.
Mohammad Alaggan
CC BY-SA 3.0
2012-02-26T05:29:51.237Z
As I wrote in a comment to the question, multiplication is inessential in the question.  The title of the question is simply wrong.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-27T03:33:45.337Z
So the title should be modified. Otherwise maybe someone will come later to this question expecting to find something similar to my answer.
Mohammad Alaggan
CC BY-SA 3.0
2012-02-26T00:07:46.943Z
2012-02-26T00:07:46.943Z
Mohammad Alaggan
<p>Suppose there are $N&gt;2$ parties $p_j$, each with a bit $b_j\in{\{0,1\}}$. I want to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b_j})\times(N-\sum{b_j})$. </p>

<p>The computation should be secure in the sense that no party can learn more than the final result $R$. For example, it's not ok to perform secure sum, because then $\sum{b_j}$ will become known, and the sum is sensitive in my problem. So, is there any existing secure computation protocol that fits the demand?</p>

<p>Edit: The number $N$ in the problem is large, at least over $1000$. So efficient secure multiparty computation is needed. A secure sum protocol could be efficient but generic  SMC like boolean circuits might be too computation intensive. So I need an efficient protocol.</p>

CC BY-SA 3.0
2012-02-24T20:14:35.387Z
you are aware of the general feasibility results for multi-party secure computation as well as the recent work on fully homomorphic encryption? because both solve your problem.
Sasho Nikolov
CC BY-SA 3.0
2012-02-24T20:18:46.950Z
Maybe it should be an answer, @SashoNikolov
Suresh Venkat
CC BY-SA 3.0
2012-02-24T20:24:51.600Z
@Suresh i thought i'd give him a chance to clarify additional restrictions, because if he knows about secure sum arguably he should know at about the feasibility results.
Sasho Nikolov
CC BY-SA 3.0
2012-02-24T20:31:31.913Z
@SashoNikolov any references on the complete feasibility result of SMC? I will put additional requirement in terms of efficiency.
Richard
CC BY-SA 3.0
2012-02-24T20:55:10.890Z
http://dl.acm.org/citation.cfm?id=28420
Sasho Nikolov
CC BY-SA 3.0
2012-02-24T23:09:45.553Z
Is the problem equivalent to securely computing min{∑b_j, N-∑b_j}?  If so, the focus on multiplication seems like only a distraction to me.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-25T00:02:48.700Z
@TsuyoshiIto it is equivalent
Sasho Nikolov
CC BY-SA 3.0
2012-02-26T03:00:33.087Z
@TsuyoshiIto are you saying minimizaiton is solved problem?
Richard
<cr.crypto-security><security>
Secure multiparty computation of number of 1s times number of 0s in a shared string
Richard
# Secure multiparty computation of number of 1s times number of 0s in a shared string

(Asked by: username_0 on 2012-02-24)

Suppose there are $N>2$ parties $p\_j$, each with a bit $b\_j\in{\{0,1\}}$. I want to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b\_j})\times(N-\sum{b\_j})$.

The computation should be secure in the sense that no party can learn more than the final result $R$. For example, it's not ok to perform secure sum, because then $\sum{b\_j}$ will become known, and the sum is sensitive in my problem. So, is there any existing secure computation protocol that fits the demand?

Edit: The number $N$ in the problem is large, at least over $1000$. So efficient secure multiparty computation is needed. A secure sum protocol could be efficient but generic SMC like boolean circuits might be too computation intensive. So I need an efficient protocol.

**Tags:** cr.crypto-security, security

> **Comments:**
> **username_1**: you are aware of the general feasibility results for multi-party secure computation as well as the recent work on fully homomorphic encryption? because both solve your problem.  
> **username_2**: Maybe it should be an answer, @SashoNikolov  
> **username_1**: @Suresh i thought i'd give him a chance to clarify additional restrictions, because if he knows about secure sum arguably he should know at about the feasibility results.  
> **username_0**: @SashoNikolov any references on the complete feasibility result of SMC? I will put additional requirement in terms of efficiency.  
> **username_1**: http://dl.acm.org/citation.cfm?id=28420  
> **username_3**: Is the problem equivalent to securely computing min{∑b_j, N-∑b_j}?  If so, the focus on multiplication seems like only a distraction to me.  
> **username_1**: @TsuyoshiIto it is equivalent  
> **username_0**: @TsuyoshiIto are you saying minimizaiton is solved problem?  

---

## 2 answers

### Answer by username_4 on 2012-10-23. Score: 3

*New answer (10/24):* I think the following paper provides an elegant and efficient solution to your problem:

* [Evaluating 2-DNF Formulas on Ciphertexts](http://crypto.stanford.edu/~dabo/pubs/papers/2dnf.pdf), Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.

They show how to build a public-key encryption algorithm $E(\cdot)$ with the following two useful properties:

* *Additively homomorphic.* Given $E(x)$ and $E(y)$, anyone can compute $E(x+y)$.
* *Can multiply (once).* Given $E(x)$ and $E(y)$ (neither of which was generated as a result of a multiplication operation), anyone can compute $E(x \cdot y)$. You can use the result in addition operations, but you cannot use it in any multiplication operations (the result of a multiplication is tainted, and tainted values cannot be used as the input to another multiplication).

The consequence is that, given a *quadratic* multivariate polynomial $\Psi(x\_1,\dots,x\_n)$, and given $E(x\_1),\dots,E(x\_n)$, anyone can compute an encryption of $\Psi(x\_1,\dots,x\_n)$. This is super-useful for your situation.

In particular, in your situation, we can form the polynomial
$$\Psi(b\_1,b\_2,\dots,b\_N) = \sum\_{i \ne j} [b\_i (1-b\_j)].$$
Note that this is a quadratic multivariate polynomial, so given all of the $E(b\_i)$'s, anyone can compute $E(\Psi(b\_1,\dots,b\_N))$. Also note that $R=\Psi(b\_1,\dots,b\_N)$, so we're trying to compute exactly the value of this polynomial.

This suggests a natural protocol for your problem, using a threshold version of the encryption scheme in the paper referenced above:

* Everyone jointly generates a public/private keypair for a threshold version of this scheme, such that the public key is known to all but the private key is shared among everyone (it requires cooperation of all $N$ parties to decrypt a ciphertext encrypted under this public key). The public key is broadcast to all $N$ participants.
* Each participant $i$ computes $E(b\_i)$ and broadcasts $E(b\_i)$ to all other participants. Everyone checks that this has been done honestly.
* Each participant computes $E(R) = E(\Psi(b\_1,\dots,b\_N))$ using the homomorphic properties of this encryption scheme and knowledge of $E(b\_1),\dots,E(b\_N)$. Everyone checks that they got the same value.
* The $N$ participants jointly use the threshold decryption protocol to recover $R$ from $E(R)$. (Note that they will only apply the threshold decryption protocol to this one ciphertext; the honest participants will refuse to participate in decrypting any other ciphertext.)
* Everyone proves somehow (maybe via ZK proofs) that they performed each step correctly.

You'd have to fill in some details, but I bet you could expand this sketch/outline to get a protocol that would solve your problem efficiently and securely.

---

*My old answer:*

I'd still look some more at a secure multiparty protocol for computing the sum $S = \sum\_j b\_j$.

The only way that this falls short of your scheme is it reveals one additional bit: it reveals whether $S

You say the sum $S$ is sensitive in your application. I hope you are aware that revealing the value $R$ reveals $S$ up to two possibilities (i.e., given $R$, we can compute a value $Q$ such that $S \in \{Q,N-Q\}$).

If you absolutely must conceal this information, here is a different approach that you might be able to make work. For each pair of parties $i,j$, securely compute $E(c\_{i,j})$ where $c\_{i,j} = b\_i \oplus b\_j$, $\oplus$ is the xor operation, and $E$ is some sort of additively-homomorphic encryption scheme. Then you might be able to compute $\sum\_{i

> **Comments:**
> **username_0**: that is a very interesting idea. though it does not produce the production exactly, using xor actually conceal the info whether it is 0 or 1. One problem though, is xor computed in plaintext in the scheme? any secure computation for xor?  
> **username_4**: @username_0, my thought was that you might be able to use two-party secure computation: party $i$ has input $b_i$, party $j$ has input $b_j$, and they want to jointly compute $E(c_{i,j})$ where $c_{i,j}=b_i\oplus b_j.$ This can be done (without computing xor in plaintext) using standard methods for 2-party secure computation. However, there's something subtle related to the threat model which I haven't fully thought through (what if party $i$ is malicious but party $j$ isn't?), and there'd need to be some way to force, say, party $i$ to use the same $b_i$ value in all such interactions.  

---

### Answer by username_5 on 2012-02-26. Score: 2

This answer is about feasible solutions based on homomorphic encryption that is NOT fully-homomorphic, as the latter may be extremely inefficient (if there are efficient fully homomorphic cryptosystems that are comparable with those provided below in terms of efficiency, I'd be glad to hear about them).

Since you only need one multiplication then there are solutions that are potentially less expensive than fully homomorphic encryption: [1] and [2]. The latter works on encrypted bit-decompositions of the input so it will need a bit-decomposition protocol like [3] and [6], but the former works on whole values. Just for completeness, the former has been extended to $d$-operand multiplication in [4], even though the OP may not need this. These solutions are non-interactive and should work in the two-party case.

If you have more than two parties and could afford some interaction then [5] provides a "secure multiplication gate" which is potentially more efficient and allows unbounded number of multiplications. It works basically by converting the homomorphically-encrypted values to some sort of secret-sharing, multiplies the result (interactively), then convert it back to homomorphic encryption.

[1] [Evaluating 2-DNF Formulas on Ciphertexts](http://www.springerlink.com/content/wtt5caxkr94laxkg/)

[2] [Non-interactive cryptocomputing for NC1](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=814630)

[3] [Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation](http://www.springerlink.com/content/m17u3nl46656jn1u/)

[4] [Additively Homomorphic Encryption with d-Operand Multiplications](http://www.springerlink.com/content/8031u1u12p01276u/)

[5] [Multiparty Computation from Threshold Homomorphic Encryption](http://www.springerlink.com/content/bkq0y15k554l6ybg/)

[6] [Efficient Binary Conversion for Paillier Encrypted Values](http://www.springerlink.com/content/dvj5507116v88429/)

> **Comments:**
> **username_3**: To be honest, I fail to see the connection of this answer to the question.  
> **username_5**: @TsuyoshiIto: This answer lists a few references that could be used to provide "secure computation for multiplication", and are especially tailored for the formula the OP provided which includes only one multiplication. It also lists relatively 'efficient' methods as per the OP's request. I actually fail to see your objection at all.  
> **username_3**: As I wrote in a comment to the question, multiplication is inessential in the question.  The title of the question is simply wrong.  
> **username_5**: So the title should be modified. Otherwise maybe someone will come later to this question expecting to find something similar to my answer.  

---

