Security model for privacy-preserving aggregation scheme.

Question

Suppose that $S=(E,D)$ is an additively homomorphic encryption scheme. Now I want to design a protocol $P$ such that given inputs $x_1,x_2,..,x_n$, the adversary $A$ (who can decrypt) can only learn $\sum x_i$ and nothing else. To do that, $P$ first generates random values $r_1, r_2,..,r_n$ such that $\sum r_i = 0$. Then, $E(x_1+r_1)\times..\times E(x_n+r_n) = E(\sum x_i)$.

The trouble I have is when adversary has some domain knowledge of $x_i$. For example, if it knows that $x_i \geq 0$, and later decrypts $E(\sum x_i)$ to learn that $\sum x_i = 0$, it can learn that $x_i = 0$ for all $i$.

How could I formulate a security game that takes into account such attacks based on domain/auxiliary knowledge? Would IND-CPA security model be sufficient? How's about IND-CCA?

I've read the paper [1], but I don't think it addresses the domain/auxiliary knowledge.

[1] Shi et al. Privacy-preserving aggregation of Time-series Data (NDSS'11)

Answer 1

The standard approach is to break this problem into two pieces:

• What information is unavoidably leaked, merely by computing the desired function? In your case, the goal is to compute $\sum_i x_i$. This sum unavoidably leaks a little bit of information about the $x_i$'s. For instance, as you correctly state, if we somehow know that all $x_i$'s are non-negative, and if we happen to observe that $\sum_i x_i = 0$, then we can conclude that $x_1=\dots=x_n=0$. This kind of leakage is unavoidable: any approach to computing $\sum_i x_i$ must inevitably leak this information.

• What other information is leaked by the cryptographic protocol? We can ask whether the cryptographic protocol leaks more than the above (more than what is unavoidable).

Multi-party secure computation is designed to avoid any leakage of the second type: there will be none whatsoever. The only information leaked will be whatever can be deduced solely from the value of the output, i.e., whatever leakage is unavoidable and inherent in the functionality itself.

---

That leaves the question: just how much is unavoidably leaked, and is that much leakage acceptable? The cryptographic literature doesn't answer that question. If you think about it, it can't really, as that will depend deeply on the particular application domain. The cryptographic tools basically assume that you will think through these implications: before asking for a protocol to compute the sum $\sum_i x_i$, cryptographers assume you have thought through the implications of doing so.

So, the only good answer I can give you is: the standard approach is a bit different than you may have expected. Rather than trying to formalize something like IND-CPA (the equivalent of requiring there be no leakage whatsoever), we instead formalize things by requiring that there be no more leakage than whatever is an inevitable consequence of the value you're trying to compute.

Answer 2

This is tricky and I don't know that there is a generic way to take care of all domain/auxiliary information.

The way we typically do proofs in multi-party computations is by defining an ideal world and show that the information generated in the ideal world (usually the encrypted inputs and the outputs) could be used to simulate the real world protocol transcript (at least in the semi-honest case). If the simulator can generate the transcript, then clearly the transcript contains no additional information beyond what is already present in the info generated in the ideal world. Therefore, the protocol cannot leak additional information.

Given the protocol you've described, the ideal world would be a trusted party which cannot be corrupted is given encrypted inputs from each party. The trusted party decrypts them all (we don't need homomorphic encryption in the ideal world), adds them up and returns the answer. Well, if the answer is $0$ as you suggest, this leaks information. But, that information is leaked in the ideal world as well as in the real, so we don't consider it a breach of the protocol.

The most natural way then to deal with this problem in the ideal world is to have the trusted party check the output for certain cases (e.g., $0$) before outputting the answer. If one of those cases is achieved, the trusted party output $\bot$. You can definitely implement this functionality in your real world protocol using a secure comparison of some sort. Your protocol will obviously be more complex, but such is life.

That shows how you would handle a specific case. There are definitely other cases where domain/auxiliary information combined with the answer will allow adversaries to infer additional information. I don't know of any generic way to handle all of this, and quite possibly it is impossible to handle in a generic way.

Consider the following, assume we have a generic multi-party comptuation protocol $\pi$. Furthermore, assume this protocol is proven secure for up to $n-1$ adversarial parties.

Now, we might be tempted to use this protocol to compute the sum you describe in the question. But, there is a problem. If there are $n-1$ adversarial parties, they can all set their inputs to $0$. The single honest part sets its input to the proper input say $x_h$. The output of the computation is clearly $x_h$ so the honest party's input is leaked. This would happen in the (standard) ideal world too, though. So even though the protocol can handle up to $n-1$ adversarial parties, the specific functionality we are computing can only handle up to $n-2$ adversarial parties. This suggests that the functionality to be computed must have an impact on the adversary model we choose, and seems to suggest that a generic solution to the problem you mention might not be possible.

So then, it seems the path forward would be to list all possible corner cases for a computation where some undesired leak occurs due to domain/auxiliary information, then adjust the computation accordingly. Then the security could be proven using standard methods. This could then potentially be extended to classes of computations, etc.