Privately Sum Values without Dealers, MPC 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. The calculations should finish in seconds or minutes for $n = 20$.

The usual approach to this problem is use homomorphic encryption, but homomorphic encryption requires keys to be distributed among the actors. The two approaches to key generation that I found in the literature aren't useful here: there is no trusted party to act as a dealer, and secure multiparty computation is too slow.

Here's the best I can do using my own imagination. I'm curious if there's something in the literature I missed, or if somebody else's imagination is more fertile.


Choose $m &gt; \sum p_i$  
Each actor chooses a random $r_i &lt; m$  
The actors seed their random number generators using a hard-coded value, and all compute the same random ordering of the actors.  
Actor $i$ receives some $e_i$ from the previous actor, and sends $e_{i+1} = p_i + r_i + e_i \mod m \;\;$ to the next actor. $\;\; e_0 = 0 \qquad e_n = \sum p_i + \sum r_i \mod m$  
All the actors compute the same, new random ordering of the actors.
Actor $i$ receives some $d_i$ from the previous actor, and sends $\;\;d_{i+1} = d_i - r_i \mod m \;\;$ to the next actor. $\;\; d_0 = e_n \qquad e_n = \sum p_i$.


This is quite fast, requiring $2*n$ network transmissions and negligible computation. The security is good but not ideal. Most seriously, someone eavesdropping on your network connection can learn your $p_i$. Also, if your neighbors in the encryption and decryption processes share data, they can determine your $p_i$. If the adversary controls an actor with probability $p$, your data is leaked with probability $p^4$. An algorithm "better" than this one would maintain the secrecy of an individual $p_i$ even if the network is controlled by the adversary.
I believe the basic idea is the following:

Choose $m$ so that $\: \sum p_i \:$ can be efficiently recovered from $\; \operatorname{mod}\left(\sum p_i\hspace{.03 in},m\right) \:\:$.

Each party $i$ chooses $\:n\hspace{-0.03 in}-\hspace{-0.04 in}1\:$ elements $\:q_{i,\hspace{.03 in}j}\:$ of $\:\{0,\hspace{-0.04 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,m\hspace{-0.03 in}-\hspace{-0.04 in}2\hspace{.02 in},m\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$

independently and almost uniformly, where $j$ ranges over the other parties,
and then sends each to the corresponding other party over a confidential channel.

Each party $i$ lets $S$ be the set of other parties, and then lets $q_{i,i}$ be $\;\; \operatorname{mod}\hspace{.02 in}\left(\left(\hspace{.02 in}p_i-\left(\hspace{.02 in}\displaystyle\sum_{j\hspace{.02 in}\in \hspace{.02 in}S} q_{i,\hspace{.03 in}j}\right)\right),\hspace{.03 in}m\right) \;\;\;$.

Each party $i$ lets $q_i$ be $\; \operatorname{mod}\hspace{.02 in}\left(\left(\displaystyle\sum_j q_{j,i}\right),\hspace{.03 in}m\right) \:\:$,$\:\:$ and the broadcasts $\:q_i\:$.

Now, $\;\; \operatorname{mod}\left(\sum p_i\hspace{.03 in},m\right) \: = \: \operatorname{mod}\left(\sum q_i\hspace{.03 in},m\right) \;\;\;$.

The simplest thing to address is the use of the confidential channel. $\:$ First, if there is any way to

do this against a pure eavesdropper, then key agreement is possible, by letting Alice run one party

with a random $p_i$ from a large range, letting Bob run the others, one of which also has a random

$p_i$ from a large range and the others of which have a $p_i$ of zero, and letting the key be least

significant bits of Alice's $p_i$. $\:$ If secure erasure is allowed, then secure key agreement means

that one can lift from authentic channels to confidential channels. $\:$ If secure erasure is not

allowed, then non-committing key agreement would still suffice for that. $\:$ On the other hand,

if authentic channels are not available, then one must proceed as described in this paper.

The more complicated thing to address is the issue of parties lying about their $\:q_i\:$.

For each ordered pair of parties $\:\langle i\hspace{.01 in},j\hspace{.02 in}\rangle\:$,$\:$ there need to be equivocal commitments to $q_{i,\hspace{.03 in}j}$ such

that no secrets are needed to verify openings and the commitments and the committed values are computationally independent of the other $q_{i,\hspace{.03 in}j}$ values. $\;\;\;$ (For the first part, when $i$ and $j$ are different, just have either of them make the commitments and then send the decommit information to the other

of them over a confidential channel. $\:$ The computational independence part is easier than it would normally be because all relevant parties are in communication with each other.) $\:$ Finally, after the parties broadcast the $q_i$ values, the parties must give simultaneous computational zero knowledge arguments of knowledge of how to decommit the $q_{j,i}$ values in a way that is compatible with $q_i$.