# Secure multiparty computation of number of 1s times number of 0s in a shared string

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.

• 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 Feb 24 '12 at 20:14
• Maybe it should be an answer, @SashoNikolov – Suresh Venkat Feb 24 '12 at 20:18
• @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 Feb 24 '12 at 20:24
• 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 Feb 24 '12 at 23:09
• @TsuyoshiIto it is equivalent – Sasho Nikolov Feb 25 '12 at 0:02

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.

• To be honest, I fail to see the connection of this answer to the question. – Tsuyoshi Ito Feb 26 '12 at 1:02
• @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 Feb 26 '12 at 1:10
• 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 Feb 26 '12 at 5:29
• 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 Feb 27 '12 at 3:33

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

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.

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<N/2$ or not. Does that one bit of information matter in your setting?
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<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.
• @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. Oct 24 '12 at 19:42