Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Multi-Party Protocols, Information Complexity and Privacy

Multi-Party Protocols, Information Complexity and Privacy We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the k-party, n-bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is (n). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Multi-Party Protocols, Information Complexity and Privacy

Download PDF
29 pages

Loading next page...
 
/lp/association-for-computing-machinery/multi-party-protocols-information-complexity-and-privacy-O6QEm1R4M6
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3313230
Publisher site
See Article on Publisher Site

Abstract

We introduce a new information-theoretic measure, which we call Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: The Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; and an explicit calculation of the zero-error Public Information Complexity of the k-party, n-bit Parity function, where a player outputs the bitwise parity of the inputs. The latter result also establishes that the amount of randomness needed by a private protocol that computes this function is (n).

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Mar 17, 2019

Keywords: Multi-party communication complexity

References

  • Privacy, additional information and communication
    Bar-Yehuda, Reuven; Chor, Benny; Kushilevitz, Eyal; Orlitsky, Alon
  • An information statistics approach to data stream and communication complexity
    Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.
  • How to compress interactive communication
    Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup
  • Internal compression of protocols to entropy
    Bauer, Balthazar; Moran, Shay; Yehudayoff, Amir
  • Completeness theorems for non-cryptographic fault-tolerant distributed computation
    Ben-Or, Michael; Goldwasser, Shafi; Wigderson, Avi
  • Interactive information complexity
    Braverman, Mark
  • A tight bound for set disjointness in the message-passing model
    Braverman, Mark; Ellen, Faith; Oshman, Rotem; Pitassi, Toniann; Vaikuntanathan, Vinod
  • Public vs private coin in bounded-round information
    Braverman, Mark; Garg, Ankit
  • From information to exact communication
    Braverman, Mark; Garg, Ankit; Pankratov, Denis; Weinstein, Omri
  • On information complexity in the broadcast model
    Braverman, Mark; Oshman, Rotem
  • Information equals amortized communication
    Braverman, Mark; Rao, Anup
  • Towards a reverse newman’s theorem in interactive information complexity
    Brody, Joshua; Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian; Vereshchagin, Nikolai K.
  • Near-optimal lower bounds on the multi-party communication complexity of set disjointness
    Chakrabarti, Amit; Khot, Subhash; Sun, Xiaodong
  • Informational complexity and the direct sum problem for simultaneous message complexity
    Chakrabarti, Amit; Shi, Yaoyun; Wirth, Anthony; Yao, Andrew Chi-Chih
  • Tribes is hard in the message passing model
    Chattopadhyay, Arkadev; Mukhopadhyay, Sagnik
  • Topology matters in communication
    Chattopadhyay, Arkadev; Radhakrishnan, Jaikumar; Rudra, Atri
  • The range of topological effects on communication
    Chattopadhyay, Arkadev; Rudra, Atri
  • Multiparty unconditionally secure protocols
    Chaum, David; Crépeau, Claude; Damgard, Ivan
  • Multiparty communication complexity
    Dolev, Danny; Feder, Tomás
  • Amortized communication complexity
    Feder, Tomás; Kushilevitz, Eyal; Naor, Moni; Nisan, Noam
  • A minimal model for secure computation (extended abstract)
    Feige, Uri; Killian, Joe; Naor, Moni
  • Computing with noisy information
    Feige, Uriel; Raghavan, Prabhakar; Peleg, David; Upfal, Eli
  • Relative discrepancy does not separate information and communication complexity
    Fontes, Lila; Jain, Rahul; Kerenidis, Iordanis; Laplante, Sophie; Laurière, Mathieu; Roland, Jérémie
  • Networks cannot compute their diameter in sublinear time
    Frischknecht, Silvio; Holzer, Stephan; Wattenhofer, Roger
  • Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
    Gál, Anna; Gopalan, Parikshit
  • Exponential separation of information and communication
    Ganor, Anat; Kol, Gillat; Raz, Ran
  • Exponential separation of communication and external information
    Ganor, Anat; Kol, Gillat; Raz, Ran
  • Exponential separation of information and communication for boolean functions
    Ganor, Anat; Kol, Gillat; Raz, Ran
  • Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
    Gronemeier, Andre
  • The communication complexity of correlation
    Harsha, Prahladh; Jain, Rahul; McAllester, David A.; Radhakrishnan, Jaikumar
  • New strong direct product results in communication complexity
    Jain, Rahul
  • A direct sum theorem in communication complexity via message compression
    Jain, Rahul; Radhakrishnan, Jaikumar; Sen, Pranab
  • Hellinger strikes back: A note on the multi-party information complexity of AND
    Jayram, T. S.
  • Multi-party protocols, information complexity and privacy
    Kerenidis, Iordanis; Rosén, Adi; Urrutia, Florent
  • A strong direct product theorem for disjointness
    Klauck, Hartmut
  • Interactive compression for product distributions
    Kol, Gillat
  • Interactive compression for multi-party protocol
    Kol, Gillat; Oshman, Rotem; Sadeh, Dafna
  • Computer Science—Theory and Applications: Proceedings of the 10th International Computer Science Symposium in Russia (CSR’15)
    Kozachinskiy, Alexander
  • Communication Complexity
    Kushilevitz, Eyal; Nisan, Noam
  • On data structures and asymmetric communication complexity
    Miltersen, Peter Bro; Nisan, Noam; Safra, Shmuel; Wigderson, Avi
  • Communication Complexity and Information Complexity
    Pankratov, Denis
  • Lower bounds for number-in-hand multiparty communication complexity, made easy
    Phillips, Jeff M.; Verbin, Elad; Zhang, Qin
  • Simplified separation of information and communication
    Rao, Anup; Sinha, Makrand
  • Distributed verification and hardness of distributed approximation
    Sarma, Atish Das; Holzer, Stephan; Kor, Liah; Korman, Amos; Nanongkai, Danupon; Pandurangan, Gopal; Peleg, David; Wattenhofer, Roger
  • Towards proving strong direct product theorems
    Shaltiel, Ronen
  • A mathematical theory of communication
    Shannon, C. E.
  • Compressing interactive communication under product distributions
    Sherstov, Alexander A.
  • An optimal lower bound for distinct elements in the message passing model
    Woodruff, David P.; Zhang, Qin
  • Some complexity questions related to distributive computing (preliminary report)
    Yao, Andrew Chi-Chih