The Hardness of Being Private

DOI10.1145/2567671zbMath1321.94032OpenAlexW2174589003MaRDI QIDQ2943893

Lila Fontes, Anil Ada, Michal Koucký, Arkadev Chattopadhyay, Toniann Pitassi, Stephen A. Cook

Publication date: 7 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2567671

zbMATH Keywords

information theorycommunication complexityapproximate privacyVickrey auctionprivacy trade-off

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Information theory (general) (94A15) Approximation algorithms (68W25) Authentication, digital signatures and secret sharing (94A62)

Related Items

Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications, Communication Complexity of Conditional Disclosure of Secrets and Attribute-Based Encryption, Zero-information protocols and unambiguity in Arthur-Merlin communication, Certifying equality with limited interaction, Information lower bounds via self-reducibility, Computing (and Life) Is All about Tradeoffs

Cites Work

• Unnamed Item
• Unnamed Item
• An information statistics approach to data stream and communication complexity
• On the structure of the privacy hierarchy
• How to compress interactive communication
• On Communication Protocols That Compute Almost Privately
• Privacy, additional information and communication
• Communication Complexity
• Approximate Privacy
• Interactive information complexity
• A Zero-One Law for Boolean Privacy