Privately Sum Values without Dealers, MPC

Question

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.

Answer 1

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

Answer 2

I'm assuming when you say "secure multiparty computation is too slow" you are talking about using MPC to simulate of a trusted dealer. MPC is quite fast these days, especially when computing additions.

Since additive secret sharing (or even shamir secret sharing) is linear, it might work for your needs. In other words, say there are 4 parties with inputs $x_1,x_2,x_3,x_4$. Let $s$ be the additive secret sharing function and $r$ be the reconstruction function.

Due to the linearity of additive secret sharing $s(x_1+x_2+x_3+x_4) = s(x_1)+s(x_2)+s(x_3)+s(x_4)$

So, you could have each party share their input, send one share (over secure channel) to each other party and keep one share for themselves. Every party then sums the shares they hold. They then broadcast the summed-up share. Everyone then has the shares necessary to reconstruct $x_1+x_2+x_3+x_4$.

To make this secure against a malicious adversary, you could use portions of the SPDZ MPC protocol (though greatly simplified since you only will be doing additions). From that protocol, you'd use their MAC to check validity. Another option is to use Feldman's VSS (which will require a few more calls to the broadcast channel).

In either case the maximum threshold for corrupt parties is $n-2$ since if there were $n-1$ corrupt parties, they all set their inputs to $0$ and you leak the one honest party's input. With either additive secret sharing or shamir secret sharing (since you aren't doing any multiplications), you could easily achieve maximum security threshold.

I'm not sure if there are any linear secret sharing schemes which are verifiable and do not require a broadcast channel.