The complexity of differential privacy
From MaRDI portal
Publication:5021135
DOI10.1007/978-3-319-57048-8_7zbMATH Open1481.94070OpenAlexW2605062226MaRDI QIDQ5021135FDOQ5021135
Authors: Salil Vadhan 
Publication date: 12 January 2022
Published in: Tutorials on the Foundations of Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-57048-8_7
Recommendations
Cryptography (94A60) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (94D10) Informational aspects of data analysis and big data (94A16)
Cites Work
- Differential Privacy
- Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
- Theory of Cryptography
- A Pseudorandom Generator from any One-way Function
- A proof of security of Yao's protocol for two-party computation
- The geometry of differential privacy: the small database and approximate cases
- On the geometry of differential privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Optimal Lower Bound for Differentially Private Multi-party Aggregation
- Title not available (Why is that?)
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Six Standard Deviations Suffice
- Title not available (Why is that?)
- Foundations of Cryptography
- On the complexity of differentially private data release
- Unconditional differentially private mechanisms for linear queries
- The primes contain arbitrarily long polynomial progressions
- The primes contain arbitrarily long arithmetic progressions
- A theory of the learnable
- Collusion-secure fingerprinting for digital data
- Computational analogues of entropy
- Geometric discrepancy. An illustrated guide
- Limits on the usefulness of random oracles
- Limits of computational differential privacy in the client/server setting
- Computational Differential Privacy
- Distributed Private Data Analysis: Simultaneously Solving How and What
- Efficient noise-tolerant learning from statistical queries
- Tracing traitors
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- An introduction to randomness extractors
- Candidate indistinguishability obfuscation and functional encryption for all circuits
- Differentially private data analysis of social networks via restricted sensitivity
- On data structures and asymmetric communication complexity
- Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
- Grothendieck-type inequalities in combinatorial optimization
- Title not available (Why is that?)
- Optimal probabilistic fingerprint codes
- Advances in Cryptology – CRYPTO 2004
- Title not available (Why is that?)
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- What can we learn privately?
- Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys
- Preserving Statistical Validity in Adaptive Data Analysis
- Algorithmic stability for adaptive data analysis
- The Algorithmic Foundations of Differential Privacy
- Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
- Title not available (Why is that?)
- Optimal private halfspace counting via discrepancy
- Bounds on the sample complexity for private learning and private data release
- Analyzing Graphs with Node Differential Privacy
- Strong Hardness of Privacy from Weak Traitor Tracing
- Order-Revealing Encryption and the Hardness of Private Learning
- The Composition Theorem for Differential Privacy
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Differential privacy and robust statistics
- Differential privacy under continual observation
- Characterizing the sample complexity of private learners
- Faster Algorithms for Privately Releasing Marginals
- Faster private release of marginals on small databases
- Pure Differential Privacy for Rectangle Queries via Private Partitions
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Local, Private, Efficient Protocols for Succinct Histograms
- Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
- Fingerprinting codes and the price of approximate differential privacy
- Privacy-preserving statistical estimation with optimal convergence rates
- A learning theory approach to noninteractive database privacy
- Do Distributed Differentially-Private Protocols Require Oblivious Transfer?
- Privacy Aware Learning
- Simultaneous private learning of multiple concepts
- Efficient algorithms for privately releasing marginals via convex relaxations
- Pcps and the hardness of generating private synthetic data
- The Complexity of Computing the Optimal Composition of Differential Privacy
- Separating Computational and Statistical Differential Privacy in the Client-Server Model
Cited In (16)
- Differentially Private Learning of Geometric Concepts
- 30 years of synthetic data
- Formalizing data deletion in the context of the right to be forgotten
- Distribution-invariant differential privacy
- General inferential limits under differential and pufferfish privacy
- Comparative study of differentially private data synthesis methods
- Resolving the Complexity of Some Data Privacy Problems
- Answering \(n^2+o(1)\) counting queries with differential privacy is hard
- Majority vote for distributed differentially private sign selection
- Title not available (Why is that?)
- Opacity enforcement in discrete event systems using differential privacy
- Addressing Complexity in a Privacy Expert System
- On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
- Concurrent composition of differential privacy
- Private measures, random walks, and synthetic data
- Impossibility of Differentially Private Universally Optimal Mechanisms
Uses Software
This page was built for publication: The complexity of differential privacy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5021135)
