A communication-privacy tradeoff for modular addition (Q1209990)

We consider the following problem: A set of \(n\) parties, each holding an input value \(x_ i\in \{0,1,...,m-1\}\), wishes to distributively compute the sum of their input values modulo the integer \(m\), (i.e., \(\sum^ n_{i=1}x_ i\bmod 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 what follows from their input values and the computed sum. We present an oblivious protocol which computes the sum \(t\)-privately, using \(n\times \lceil (t+1)/2\rceil\) 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 \(\lceil n\times (t+1)/2\rceil\) messages for any oblivious protocol that computes the sum \(t\)-privately.