A communication-privacy tradeoff for modular addition
type: Item
instance of: scholarly article
title: A communication-privacy tradeoff for modular addition
zbMATH Open document ID: 0780.68003
DOI: 10.1016/0020-0190(93)90120-X
author: Benny Chor
author: Eyal Kushilevitz
published in: Information Processing Letters
publication date: 1993-05-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68M10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 168864
zbMATH Keywords: private computation
zbMATH Keywords: message complexity
zbMATH Keywords: modular sum
MaRDI profile type: Publication
cites work: Q3778674
Recommended article: Q4408469
Recommended article: Modular control under privacy protection: fundamental trade-offs
Recommended article: On communication protocols that compute almost privately
Recommended article: On Communication Protocols That Compute Almost Privately
Recommended article: Practical private computation of vector addition-based functions
Recommended article: Satisfiability modulo counting
Recommended article: Sum it up: verifiable additive homomorphic secret sharing
Recommended article: On the information level of modular secret-sharing schemes
Recommended article: Another look at anonymous communication. Security and modular constructions
Recommended article: Private circuits: a modular approach
description: scientific article; zbMATH DE number 168864