Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
The actors seed their random number generators using a hard-coded value, and all compute the same random ordering of the actors. How exactly do they do that? If the seed is hard-coded, the result won't be that random at all. Even when you get a value, how is participant $i$ to decide if he's before or after participant $i+1$? It would be better to choose a random value in the range of $10^{2n}$ for $n$ participants, and have colliding parties fight it out between them. –  rath Sep 12 '13 at 7:48
    
Can you assume secure channels (say with SSL)? How about a broadcast channel? Is there an assumed threshold of the number or corrupt players (say n/2 or n-1)? In other words what is the maximum number of corrupt players? –  mikeazo Sep 12 '13 at 11:29
    
@rath: What I mean by "hard-coded value" is something like cat(IP address, nonce), where nonce is the number of times you've generated a random ordering. The nodes then go in order from smallest to largest, as you suggest. The point is that any participant can verify that the ordering is correct; otherwise an adversary with only four nodes could just put themselves next to you! –  Kire321 Sep 12 '13 at 22:48
    
@mikeazo: Yes, I could use SSL to get secure channels. Broadcasting is possible but inefficient, since it just means transmitting to everyone. The threshold of corrupt players should be "better" then in the my naive approach. Assuming a 1% chance of leakage is tolerable, 30% of actors may be corrupted (in my naive approach), so better than that. –  Kire321 Sep 13 '13 at 16:23
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Great, that seems like it ought to work. Do you have a source for this, so I can give credit where credit is due? –  Kire321 Sep 13 '13 at 16:39
    
This is just a generalization of the dining cryptographers protocol. $\;$ –  Ricky Demer Sep 14 '13 at 1:44
add comment

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.

share|improve this answer
    
Security is still non-trivial even if the output necessarily reveals the honest party's input. $\hspace{1.27 in}$ –  Ricky Demer Sep 14 '13 at 1:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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