A COMMUNICATION-PRIVACY TRADEOFF FOR MODULAR ADDITION

We consider the following problem: A set of n parties, each holding an input value x(i) is-an-element-of {0,1,..., m - 1}, wishes to distributively compute the sum of their input values modulo the integer m, (i.e, SIGMA(i=1)n x(i) mod m). The parties wish to compute this sum t-privately. That is, in a way that no coalition of size at most t can infer any additional information. other than what follows from their input values and the computed sum. We present an oblivious protocol which computes the sum t-privately, using n . [(t + 1)/2] messages. This protocol requires fewer messages than the known private protocols for modular addition. Then, we show that this protocol is in a sense optimal, by proving a tight lower bound of [n . (t + 1)/2] messages for any oblivious protocol that computes the sum t-privately.