Suppose $n$ actors each hold a plaintext $p_i$. We wish to find $\sum p_i$, without leaking any information about individual $p_i$. Any actor (or any link in the network) could be controlled by an active adversary. More precisely, these protocols can be proved secure against a polynomial time bounded adversary who can corrupt a set of less than $n/2$ parties initially, and then make them behave as he likes, we say that the adversary is active.

In article Multiparty Computation from Threshold Homomorphic Encryption there is approach to multiparty computation (MPC) basing it on homomorphic threshold crypto-systems. I'm unsure how to make multiparty sum secure in malicious model (against less than $n/2$ active adversaries) following this approach. I'm under impression that it's quite simple:

  1. each player uses additive homomorphic encryption to calculate ciphertext $E(p_i)$ of his own imput, sends the ciphertext to other parties and attach proof of plaintext knowledge to the ciphertext
  2. verify proofs, add ciphertexts to calculate $E(\sum p_i)$
  3. decrypt sum $E(\sum p_i)$ using threshold decryption to calculate $\sum p_i$

Could you confirm that what I described above is secure in malicious model (against less than $n/2$ active colluding adversaries)?

  • $\begingroup$ Does "fully secure" mean secure against stronger adversaries than the $\hspace{2.14 in}$ kind described in your initial paragraph? $\;$ $\endgroup$ – user991 Nov 17 '14 at 0:15
  • $\begingroup$ secure against less than $n/2$ active adversaries is sufficient (I clarified the question) $\endgroup$ – zacheusz Nov 17 '14 at 7:16
  • 1
    $\begingroup$ For step 1, you'll need each actor to have it's own NIZK setup string too. $\:$ Step 2 would require a definition of "additive homomorphic encryption" that is far stronger than the usual one, since it would need to handle the fact that the ciphertexts will have been encrypted under different public keys. $\:$ (Are you aware of any candidates for that?) $\;\;\;\;$ $\endgroup$ – user991 Nov 17 '14 at 7:36
  • $\begingroup$ the additive homomorphism property of the encryption scheme is covered in the referenced article link.springer.com/chapter/10.1007/3-540-44987-6_18 . The good example is Paillier Cryptosystem rd.springer.com/chapter/10.1007%2F978-3-540-48000-6_14 I wonder why the authors didn't meant about NIZK setup in the article link.springer.com/chapter/10.1007/3-540-44987-6_18 $\endgroup$ – zacheusz Nov 17 '14 at 9:51
  • 1
    $\begingroup$ The NIZK protocols need to be simulation-extractable, rather than just plain NIZK. $\:$ The threshold decryption needs to be simulatable (I don't know whether or not most threshold PKE schemes provide that). $\endgroup$ – user991 Nov 17 '14 at 10:00

You are on the right track. However, as Ricky Demer points out in the comments, your suggestion would not work because the input is encrypted with different public keys. To fix this you need to use the properties of the threshold-encryption scheme.

In a threshold-encryption scheme the players run a key-generation protocol in order to generate a common public key $pk$, and a secret sharing of the secret key $sk$. This means that while all players hold $pk$ no single player holds $sk$. I.e., all players can encrypt but no one can decrypt without the help of the other players. In order to decrypt the players run a special decryption protocol.

So in other words your suggestion is almost correct, only the players do not hold different public encryption keys. To fix it you need to add an other step before step 1 where the players collaborate to generate keys. And in step 3 the players do not decrypt on their own. Instead they run a decryption protocol among each other.

This works because you only want to compute a sum (i.e., you are only doing additions). However, in general you could compute any arithmetic function. The only problem is that since you are using a additively homomorphic encryption scheme, doing multiplication is not as simple as addition. This is solved by running a special multiplication protocol among the players for every multiplication.

These days of course you could use a fully homomorphic threshold encryption scheme instead of a additively homomorphic one. In that case you would no longer need a special multiplication protocol. The reason why the authors of the paper you are linking to do not use a fully homomorphic scheme is simply that those were not invented when the paper was written.

This is just a rough description of course. For more detail I recommend you read the paper you linked to.

  • $\begingroup$ Good point with the public encryption scheme - I edited the question. I'was suggested by other homomorphic setups (Pohlig-Hellman). My doubts are because summing just looks too simple in comparison with product algorithm. The main doubt is if this algorithm is secure against active adversaries. $\endgroup$ – zacheusz Nov 17 '14 at 9:58
  • $\begingroup$ Well, there are some details missing here, but yes this should be secure against malicious adversaries. Provided that the protocols for the threshold encryption scheme are secure against malicious adversaries of course (i.e., the distributed key generation and decryption). Sums just are very simple. In fact generally linear functions are often very efficient to compute in MPC. $\endgroup$ – Guut Boy Nov 19 '14 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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