9
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Feb 24, 2012 at 20:14
  • 1
    $\begingroup$ Maybe it should be an answer, @SashoNikolov $\endgroup$
    – Suresh Venkat
    Feb 24, 2012 at 20:18
  • 2
    $\begingroup$ @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. $\endgroup$
    – Sasho Nikolov
    Feb 24, 2012 at 20:24
  • 3
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Feb 24, 2012 at 23:09
  • 2
    $\begingroup$ @TsuyoshiIto it is equivalent $\endgroup$
    – Sasho Nikolov
    Feb 25, 2012 at 0:02

2 Answers 2

Reset to default
3
$\begingroup$

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.

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<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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Richard
    Oct 24, 2012 at 18:43
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Oct 24, 2012 at 19:42
2
$\begingroup$

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

[2] Non-interactive cryptocomputing for NC1

[3] Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation

[4] Additively Homomorphic Encryption with d-Operand Multiplications

[5] Multiparty Computation from Threshold Homomorphic Encryption

[6] Efficient Binary Conversion for Paillier Encrypted Values

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ To be honest, I fail to see the connection of this answer to the question. $\endgroup$
    – Tsuyoshi Ito
    Feb 26, 2012 at 1:02
  • $\begingroup$ @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. $\endgroup$
    – Mohammad Alaggan
    Feb 26, 2012 at 1:10
  • 4
    $\begingroup$ As I wrote in a comment to the question, multiplication is inessential in the question. The title of the question is simply wrong. $\endgroup$
    – Tsuyoshi Ito
    Feb 26, 2012 at 5:29
  • 1
    $\begingroup$ So the title should be modified. Otherwise maybe someone will come later to this question expecting to find something similar to my answer. $\endgroup$
    – Mohammad Alaggan
    Feb 27, 2012 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.