Privacy and communication complexity
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 416-421
- https://doi.org/10.1109/sfcs.1989.63512
Abstract
Each of two parties P/sub 1/ and P/sub 2/ holds an n-bit input, x and y, respectively. They wish to compute privately the value of f(x,y). Two questions are considered: (1) Which functions can be privately computed? (2) What is the communication complexity of protocols that privately compute a function f (in the case in which such protocols exist)? A complete combinatorial characterization of privately computable functions is given. This characterization is used to derive tight bounds on the rounds complexity of any privately computable function and to design optimal private protocols that compute these functions. It is shown that for every 1<or=g(n)<or=2*2/sup n/ there are functions that can be privately computed with g(n) rounds of communication, but not with g(n)-1 rounds of communication.Keywords
This publication has 14 references indexed in Scilit:
- Privacy and communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Optimal algorithms for Byzantine agreementPublished by Association for Computing Machinery (ACM) ,1988
- Completeness theorems for non-cryptographic fault-tolerant distributed computationPublished by Association for Computing Machinery (ACM) ,1988
- An O (log n ) expected rounds randomized byzantine generals protocolJournal of the ACM, 1987
- How to play ANY mental gamePublished by Association for Computing Machinery (ACM) ,1987
- Lower bounds by probabilistic argumentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Protocols for secure computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Communication complexityPublished by Association for Computing Machinery (ACM) ,1982
- On the andvantages of free choicePublished by Association for Computing Machinery (ACM) ,1981
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979