Private Computations over the Integers
Authors:
- Benny ChorBCBenny Chor
- Mihály Geréb-GrausMGMihály Geréb-Graus
- Eyal KushilevitzEKEyal Kushilevitz
- 1 April 1995
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 24 (2) , 376-386
Abstract
The subject of this work is the possibility of private distributed computations of n-argument functions defined over the integers. A function f is t-private if there exists a protocol for computing f, so that no coalition of at most t participants can infer any additional information from the execution of the protocol. It is known that over finite domains every function can be computed $\lfloor (n - 1)/2 \rfloor $-privately. Some functions, like addition, are even n-private. We prove that this result cannot be extended to infinite domains. The possibility of privately computing f is shown to be closely related to the communication complexity of f. By using this relation, we show, for example, that n-argument addition is $\lfloor (n - 1)/2 \rfloor $-private over the nonnegative integers, but not even 1-private over all the integers. Finally, a complete characterization of t-private Boolean functions over countable domains is given. A Boolean function is 1-private if and only if its communication complexity is bounded. This characterization enables us to prove that every Boolean function falls into one of the following three categories: It is either n-private, $\lfloor (n - 1)/2 \rfloor $-private but not $\lceil n/2 \rceil$-private, or not 1-private.Keywords
This publication has 15 references indexed in Scilit:
- On the structure of the privacy hierarchyJournal of Cryptology, 1994
- Secret sharing over infinite domainsJournal of Cryptology, 1993
- Privacy, additional information and communicationIEEE Transactions on Information Theory, 1993
- Privacy and Communication ComplexitySIAM Journal on Discrete Mathematics, 1992
- A Zero-One Law for Boolean PrivacySIAM Journal on Discrete Mathematics, 1991
- Knowledge and common knowledge in a distributed environmentJournal of the ACM, 1990
- Lower bounds on communication complexity in distributed computer networksJournal of the ACM, 1987
- How to play ANY mental game1987
- Protocols for secure computations1982
- Security Proofs for Information Protection Systems1981