Consider $N$ players and assume that a private channel between each pair of players is available. Player $i \in \{ 1, \ldots,N\}$ holds a secret $S_i$, which is a sequence of $B$ random bits.

The players want to perform the secure addition $S_1 + \ldots + S_N$ modulo 2, i.e., after communication over their private channels, the $N$ players can compute the sum if they pool their information together, and any set of $N-1$ players cannot learn any information about the sum.

It is well known that this secure addition can be performed from linear secret sharing schemes (Reference). In this case the communication complexity, i.e., the overall amount of information exchanged between the players is $N(N-1)B$ bits (each player applies a secret sharing scheme to share his secret with the $N-1$ other players by sending them each a share of size $B$ bits).


  • Is there another coding scheme that achieves a better communication complexity for this specific problem?

  • What is the best known lower bound on the communication complexity for this specific problem?

Edit: I am only interested in solutions that provide information-theoretic security.

  • $\begingroup$ Have you looked into use additively homomorphic ciphers? I'd assume that you would get better complexity bounds, but you may not actually get better performance because of ciphertext expansion. $\endgroup$ – mikeazo Nov 6 '19 at 18:59
  • $\begingroup$ I am not sure what you are referring to. Does the method you suggest provide information-theoretic security, or just complexity-based security? I am only interested in information-theoretic security. $\endgroup$ – user297646 Nov 6 '19 at 19:41
  • $\begingroup$ It only provides complexity-based security. I suggest you edit your original question to mention that you are only interested in information theoretic security. That said, most MPC protocols require secure comms channels, are you going to use information theoretic protocols for that too rather than more traditional methods like TLS? $\endgroup$ – mikeazo Nov 6 '19 at 20:16
  • $\begingroup$ Thank you, I have updated the post. I just want to compare things that are comparable. For the secure channels, yes I assume that they provide information-theoretic security. I know that this has a cost, for instance, correlated random variables available at the participants and the dealer, which could be obtained from noisy channels. $\endgroup$ – user297646 Nov 7 '19 at 0:05

Your Answer

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

Browse other questions tagged or ask your own question.