-1
$\begingroup$

Let's say that I want to compute the sum of $k$ values owned by other parties. The other parties are willing to collaborate to compute the sum, but they do not want to disclose their summands. Is there a cryptographic primitive, say based on public-key cryptography, that makes it possible for me to distribute a public key to the parties, get back the results, and obtain the sum of the encrypted values when I have all the pieces (but no information filters if not all pieces are known)?

$\endgroup$
  • 1
    $\begingroup$ Is there a cryptographic primitive, say based on public-key cryptography, that makes it possible for me to distribute a public key to the parties, get back the results, and obtain the sum of the encrypted values when I have all the pieces (but no information filters if not all pieces are known)? Yes. To give you a better answer than that, we need more information. Your question suffers from the XY problem. $\endgroup$ – mikeazo Oct 11 '16 at 13:13
  • $\begingroup$ I don't understand. If the answer is "yes", why don't you say which the primitive is? $\endgroup$ – seba Oct 11 '16 at 22:04
  • $\begingroup$ because you haven't fully specifies the problem, so I can't give you any recommendations. I need to know your adversary model, who can talk to who, etc. $\endgroup$ – mikeazo Oct 11 '16 at 23:26
  • $\begingroup$ I've voted to close this due to "not clear what you're asking". If the two answers so far don't answer the question in its current state, I don't know what will. $\endgroup$ – tylo Oct 12 '16 at 10:33
2
$\begingroup$

Additive (semi-)homomorphic encryption is what you're looking for, and the Paillier cryptosystem is most commonly known/referenced.

Here's a very basic protocol for what you want:

  • Party A generates the key and publishes the public key
  • Every other party encrypts their value
  • Party B sends her value to Party C
  • Party C uses the homomorphic property to add her value to the one send by B.
  • Party C sends this to Party D
  • and so on...
  • ... until the last one sends the entire sum to Party A
  • Party A decrypts it, and can send it to the others if necessary

Party A only gets the final result and learns nothing else. For all the others, they can't decrypt the ciphertexts. But the protocol doesn't have any other properties, which you might want. For that, more information on the actual problem would be required.

| improve this answer | |
$\endgroup$
  • $\begingroup$ No, you're relying on a trusted third party, which is not part of the problem definition. We are currently already using Paillier, but it doesn't do what we need. $\endgroup$ – seba Oct 11 '16 at 22:05
  • 2
    $\begingroup$ @seba, the fact that this doesn't really answer your question probably doesn't really surprise tylo. You have given so few details that it is impossible to really answer your question. $\endgroup$ – mikeazo Oct 11 '16 at 23:28
  • $\begingroup$ Yes, but on the other hand introducing the trusted third party is incredibly powerful. As an example, consider the following protocol that does not need a cryptosystem. $\endgroup$ – seba Oct 12 '16 at 10:20
  • $\begingroup$ Each party having pieces of information $k_i$ extracts a random $r_i$ (all arithmetic is modulo $n$). Then they send to me $k_i+r_i$. Then they send the $r_i$'s to the third party, who sends me $\sum_i r_i$. I can recover $\sum_i k_i$, and still I do not know anything about each $k_i$. No cryptosystem is needed. $\endgroup$ – seba Oct 12 '16 at 10:22
  • 2
    $\begingroup$ @seba Actually, this is not a protocol with a trusted party. Party A does not get anything except the result, if the other parties can communicate directly. With a trusted party, every participant would just send their input and that party adds them up. However, I am not surprised, because your question doesn't state what you want. There are numerous ways to do MPC, but you have to define clearly what your goal is. $\endgroup$ – tylo Oct 12 '16 at 10:28
1
$\begingroup$

I would have preferred to wait in answering until you more fully specified the problem you are trying to solve, the adversary model you are working in, etc. So, likely there will be something about my approach that doesn't satisfy you. Hopefully it will, at the least, help you to more fully specify your problem.

For my setup, I will assume $n$ parties, $p_1,\dots,p_n$, each with a private input, $a_1,\dots,a_n$. We want to compute $\sigma=\sum_{a=1}^n a_n$ and reveal it to a third-party $Q$. The security requirement is that none of the parties $p_1,\dots,p_n$ learns another party's input, nor do they learn $\sigma$. $Q$ learns only $\sigma$ and nothing else.

First, an impossibility result. If we allow for $n-1$ of the parties $p_1,\dots,p_n$ to be corrupt and $Q$ to simultaneously be corrupt, we cannot achieve the above objective. This is because $Q$ can collaborate with the $n-1$ corrupt parties to learn the one honest party's private input. This is done by simply subtracting the private inputs of the corrupt parties from $\sigma$. Note that this result is independent of the cryptography used.

Solution Options
Even with the impossibility result, there are a lot of options. You can use a secure multiparty computation protocol like SPDZ to achieve security in the malicious or even covert adversary model. The fact that you are not doing any multiplications simplifies how this is accomplished significantly. It should be very fast, and very efficient.

If you are in the honest-but-curious model, a simple additive secret sharing of private inputs among the $n$ parties will work. Each party then adds the shares they received from the other parties locally and sends the result to $Q$, who adds everything up and gets the answer. If you want to do something like Paillier, you can (why would you though, it would be so much slower). The parties need to agree upon a random number that they give to $Q$ and random shares of that random number that they add to their private input value. They then encrypt with $Q$'s public Paillier key (or any additively homomorphic cipher) and send the value to $Q$. $Q$ sums them up which gives him the sum of the private inputs plus the random number. He decrypts, then subtracts out the random number, and recovers $\sigma$.

If $n$ is really large (say a million), these techniques may still be too slow. In that case I would recommend a technique I developed for MPC that will make things much faster. It does change the adversary model some, however.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, the answer is very inspiring. While I cannot apply any of these techniques directly (e.g., the first paper I found on the SPDZ site requires synchronous communication, communication between parties sharing the pieces, etc., all stuff I don't have) I'm starting to understand the basic ideas. $\endgroup$ – seba Oct 12 '16 at 15:21
  • $\begingroup$ @seba, synchronous communication can be dealt with, but no communication between parties. That will be tough. You may also want to take a look at function encryption. Like I keep saying though, it is hard to give a solid answer without all the details. $\endgroup$ – mikeazo Oct 12 '16 at 15:24
  • $\begingroup$ Well, I have a distributed asynchronous network of arbitrary topology in which a processor $x$ wants to compute the sum of the degrees of its neighbors without knowing the degrees themselves. The neighbors might not be able to communicate between each other (that depends on the network). Everybody is honest and follows the protocol, but $x$ shouldn't learn anything about the degree of its neighbors except what's implied by the sum (e.g., if there is just one neighbor it will learn its degree). $\endgroup$ – seba Oct 12 '16 at 15:28

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