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 HE 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 multi-party 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 > \sum p_i$
Each actor chooses a random $r_i < m$
The actors seed their random number generators using a hardcoded 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.

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 > \sum p_i$
• Each actor chooses a random $r_i < 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.

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 HE 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 multi-party 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 > \sum p_i Each actor chooses a random r_i < m The actors seed their random number generators using a hardcoded 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. 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. 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.

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 HE 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 multi-party 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 > \sum p_i$
Each actor chooses a random $r_i < m$
The actors seed their random number generators using a hardcoded 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.