research-article

An Interactive Information Odometer and Applications

Authors:

Mark Braverman,

Omri WeinsteinAuthors Info & Claims

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Pages 341 - 350

https://doi.org/10.1145/2746539.2746548

Published: 14 June 2015 Publication History

Abstract

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretic privacy.

As a first corollary, we prove a strong direct product theorem for communication complexity in terms of information complexity: If I bits of information are required for solving a single copy of f under μ with probability 2/3, then any protocol attempting to solve n independent copies of f under μⁿ using o(n • I) communication, will succeed with probability 2^-Ω(n). This is tight, as Braverman and Rao [BR11] previously showed that O(n • I) communication suffice to succeed with probability ~(2/3)ⁿ.

We then show how the information odometer can be used to achieve the best possible information-theoretic privacy between two untrusted parties: If the players' goal is to compute a function f(x,y), and f admits a protocol with information cost is I and communication cost C, then our odometer can be used to produce a "robust" protocol which: (i) Assuming both players are honest, computes f with high probability, and (ii) Even if one party is malicious, then for any k∈N, the probability that the honest player reveals more than O(k • (I+log C)) bits of information to the other player is at most 2^-Ω(k).

Finally, we outline an approach which uses the odometer as a proxy for breaking state of the art interactive compression results: We show that our odometer allows to reduce interactive compression to the regime where I=O(log C), thereby opening a potential avenue for improving the compression result of [BBCR10] and to new direct sum and product theorems in communication complexity.

References

[1]

Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Kouck?, and Toniann Pitassi. The hardness of being private. In IEEE Conference on Computational Complexity, pages 192--202. IEEE, 2012.

Digital Library

[2]

N. Alon and J. H. Spencer. The Probabilistic Method. Wiley--Interscience Series, John Wiley & Sons, Inc., New York, 1992.

[3]

Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 67--76, 2010.

Digital Library

[4]

Donald Beaver. Perfect privacy for two-party protocols. In J. Feigenbaum and M. Merritt, editors, Proceedings of DIMACS Workshop on Distributed Computing and Cryptology, volume 2, pages 65--77. American Mathematical Society, 1989.

[5]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In STOC, pages 1--10, 1988.

Digital Library

[6]

Mark Braverman and Anup Rao. Information equals amortized communication. In Rafail Ostrovsky, editor, FOCS, pages 748--757. IEEE, 2011.

Digital Library

[7]

Mark Braverman. Interactive information complexity. In Proceedings of the 44th symposium on Theory of Computing, STOC '12, pages 505--524, New York, NY, USA, 2012. ACM.

Digital Library

[8]

Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff. Direct products in communication complexity. Electronic Colloquium on Computational Complexity (ECCC), 19:143, 2012.

[9]

Mark Braverman and Omri Weinstein. An interactive information odometer with applications. Electronic Colloquium on Computational Complexity (ECCC), 21:47, 2014.

[10]

Reuven Bar-Yehuda, Benny Chor, Eyal Kushilevitz, and Alon Orlitsky. Privacy, additional information, and communication. IEEE Transactions on Information Theory, 39:55--65, 1993.

Digital Library

[11]

Benny Chor and Eyal Kushilevitz. A zero-one law for boolean privacy. STOC 89 and SIAM J. Disc. Math, 4:36--47, 1991.

Digital Library

[12]

Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley series in telecommunications. J. Wiley and Sons, New York, 1991.

Digital Library

[13]

Joan Feigenbaum, Aaron D. Jaggard, and Michael Schapira. Approximate privacy: Foundations and quantification (extended abstract). In Proceedings of the 11th ACM Conference on Electronic Commerce, EC '10, pages 167--178, New York, NY, USA, 2010. ACM.

Digital Library

[14]

Anat Ganor, Gillat Kol, and Ran Raz. Exponential separation of information and communication for boolean functions. Electronic Colloquium on Computational Complexity (ECCC), 21:113, 2014.

[15]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 218--229, New York, NY, USA, 1987. ACM.

Digital Library

[16]

Thomas Holenstein. Parallel repetition: Simplifications and the no-signaling case. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007.

Digital Library

[17]

D.A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098--1101, 1952.

[18]

Rahul Jain. New strong direct product results in communication complexity. 2011.

[19]

Rahul Jain and Hartmut Klauck. The partition bound for classical communication complexity and query complexity. CoRR, abs/0910.4266, 2009.

[20]

Rahul Jain, Attila Pereszlenyi, and Penghui Yao. A direct product theorem for the two-party bounded-round public-coin communication complexity. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 167--176. IEEE, 2012.

Digital Library

[21]

Rahul Jain and Penghui Yao. A strong direct product theorem in terms of the smooth rectangle bound. CoRR, abs/1209.0263, 2012.

[22]

Hartmut Klauck. On quantum and approximate privacy. In STACS, pages 335--346, 2002.

Digital Library

[23]

Hartmut Klauck. A strong direct product theorem for disjointness. In STOC, pages 77--86, 2010.

Digital Library

[24]

2}KerenidisLLRX12Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, and David Xiao. Lower bounds on information complexity via zero-communication protocols and applications. Electronic Colloquium on Computational Complexity (ECCC), 19:38, 2012.

[25]

Iordanis Kerenidis, Mathieu Laurière, and David Xiao. New lower bounds for privacy in communication protocols. In ICITS, pages 69--89, 2013.

[26]

Eyal Kushilevitz. Privacy and communication complexity. SIAM J. Discrete Math., 5(2):273--284, 1992.

Digital Library

[27]

Troy Lee, Adi Shraibman, and Robert Spalek. A direct product theorem for discrepancy. In CCC, pages 71--80, 2008.

Digital Library

[28]

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil P. Vadhan. The limits of two-party differential privacy. In FOCS, pages 81--90, 2010.

Digital Library

[29]

D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay - a secure two-party computation system. In Proceedings of the 13th USENIX Security Symposium, pages 287--302, Berkeley, CA, USA. USENIX Association.

Digital Library

[30]

Marco Molinaro, David Woodruff, and Grigory Yaroslavtsev. Beating the direct sum theorem in communication complexity with implications for sketching. In SODA, page to appear, 2013.

Digital Library

[31]

Benny Pinkas. Fair secure two-party computation. In EUROCRYPT, pages 87--105, 2003.

Digital Library

[32]

Itzhak Parnafes, Ran Raz, and Avi Wigderson. Direct product results and the GCD problem, in old and new communication models. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC '97), pages 363--372, New York, May 1997. Association for Computing Machinery.

Digital Library

[33]

Anup Rao. Parallel repetition in projection games and a concentration bound. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008.

Digital Library

[34]

Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763--803, June 1998. Prelim version in STOC '95.

Digital Library

[35]

Ran Raz. A counterexample to strong parallel repetition. SIAM J. Comput., 40(3):771--777, 2011.

Digital Library

[36]

Ronen Shaltiel. Towards proving strong direct product theorems. Computational Complexity, 12(1--2):1--22, 2003. Prelim version CCC 2001.

Digital Library

[37]

Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. In STOC, pages 41--50, 2011.

Digital Library

Cited By

Peng BRubinstein A(2023)Near Optimal Memory-Regret Tradeoff for Online Learning2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00069(1171-1194)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00069
Anshu ABen-David SKundu S(2021)On query-to-communication lifting for adversary boundsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.30Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.30
Jain RKundu S(2021)A direct product theorem for one-way quantum communicationProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.27Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.27
Show More Cited By

Index Terms

An Interactive Information Odometer and Applications
1. Information systems
  1. Information systems applications
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Interactive compression for product distributions
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs ...
How to compress asymmetric communication
CCC '15: Proceedings of the 30th Conference on Computational Complexity

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If I^A denotes the number of bits of information revealed by the first party, I^B denotes the information revealed by ...
What Security Can We Achieve Within 4 Rounds?
Abstract
Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

June 2015

916 pages

ISBN:9781450335362

DOI:10.1145/2746539

General Chair:
Rocco Servedio
Columbia University
,
Program Chair:
Ronitt Rubinfeld
MIT and Tel Aviv University

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
Turing Centenial Fellowship
Packard fellowship
Simons Foundation

Conference

STOC '15

Sponsor:

SIGACT

STOC '15: Symposium on Theory of Computing

June 14 - 17, 2015

Oregon, Portland, USA

Acceptance Rates

STOC '15 Paper Acceptance Rate 93 of 347 submissions, 27%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
180
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Peng BRubinstein A(2023)Near Optimal Memory-Regret Tradeoff for Online Learning2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00069(1171-1194)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00069
Anshu ABen-David SKundu S(2021)On query-to-communication lifting for adversary boundsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.30Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.30
Jain RKundu S(2021)A direct product theorem for one-way quantum communicationProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.27Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.27
Braverman MMinzer DKhuller SVassilevska Williams V(2021)New separations results for external informationProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451044(248-258)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451044
Jain R(2021)Chain-Rules for Channel Capacity2021 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT45174.2021.9518181(262-267)Online publication date: 12-Jul-2021
https://doi.org/10.1109/ISIT45174.2021.9518181
Braverman M(2019)Information complexity and applicationsJapanese Journal of Mathematics10.1007/s11537-018-1727-914:1(27-65)Online publication date: 5-Mar-2019
https://doi.org/10.1007/s11537-018-1727-9
Braverman MKol GDiakonikolas IKempe DHenzinger M(2018)Interactive compression to external informationProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188956(964-977)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188956
Göös MJayram TPitassi TWatson T(2018)Randomized Communication versus Partition NumberACM Transactions on Computation Theory10.1145/317071110:1(1-20)Online publication date: 24-Jan-2018
https://dl.acm.org/doi/10.1145/3170711
Watson T(2018)Communication Complexity of Statistical DistanceACM Transactions on Computation Theory10.1145/317070810:1(1-11)Online publication date: 24-Jan-2018
https://dl.acm.org/doi/10.1145/3170708
Tyagi HWatanabe S(2018)Strong Converse using Change of Measure Arguments2018 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2018.8437605(1849-1853)Online publication date: Jun-2018
https://doi.org/10.1109/ISIT.2018.8437605
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents