The Complexity of Differential Privacy
From MaRDI portal
Publication:5021135
DOI10.1007/978-3-319-57048-8_7zbMath1481.94070OpenAlexW2605062226MaRDI QIDQ5021135
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
Semidefinite programming (90C22) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (94D10) Informational aspects of data analysis and big data (94A16)
Related Items
Differentially Private Learning of Geometric Concepts, Distribution-invariant differential privacy, Concurrent composition of differential privacy, Comparative study of differentially private data synthesis methods, On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy, Unnamed Item, Formalizing data deletion in the context of the right to be forgotten
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Limits on the usefulness of random oracles
- The primes contain arbitrarily long polynomial progressions
- A proof of security of Yao's protocol for two-party computation
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- On data structures and asymmetric communication complexity
- Bounds on the sample complexity for private learning and private data release
- Efficient algorithms for privately releasing marginals via convex relaxations
- The primes contain arbitrarily long arithmetic progressions
- Pure Differential Privacy for Rectangle Queries via Private Partitions
- The Complexity of Computing the Optimal Composition of Differential Privacy
- Order-Revealing Encryption and the Hardness of Private Learning
- Simultaneous Private Learning of Multiple Concepts
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
- On the geometry of differential privacy
- Differential privacy under continual observation
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Grothendieck-Type Inequalities in Combinatorial Optimization
- Optimal Lower Bound for Differentially Private Multi-party Aggregation
- Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
- Preserving Statistical Validity in Adaptive Data Analysis
- Local, Private, Efficient Protocols for Succinct Histograms
- Differentially private data analysis of social networks via restricted sensitivity
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- PCPs and the Hardness of Generating Private Synthetic Data
- Limits of Computational Differential Privacy in the Client/Server Setting
- An Introduction to Randomness Extractors
- What Can We Learn Privately?
- Efficient noise-tolerant learning from statistical queries
- Separating Computational and Statistical Differential Privacy in the Client-Server Model
- Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
- Strong Hardness of Privacy from Weak Traitor Tracing
- Computational Differential Privacy
- The Algorithmic Foundations of Differential Privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys
- Distributed Private Data Analysis: Simultaneously Solving How and What
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Six Standard Deviations Suffice
- A theory of the learnable
- A Pseudorandom Generator from any One-way Function
- Tracing traitors
- Do Distributed Differentially-Private Protocols Require Oblivious Transfer?
- The Composition Theorem for Differential Privacy
- Collusion-secure fingerprinting for digital data
- Foundations of Cryptography
- Analyzing Graphs with Node Differential Privacy
- Differential privacy and robust statistics
- On the complexity of differentially private data release
- Fingerprinting codes and the price of approximate differential privacy
- Advances in Cryptology – CRYPTO 2004
- Algorithmic stability for adaptive data analysis
- A learning theory approach to noninteractive database privacy
- Unconditional differentially private mechanisms for linear queries
- Optimal private halfspace counting via discrepancy
- Privacy-preserving statistical estimation with optimal convergence rates
- Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Privacy Aware Learning
- Theory of Cryptography
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Optimal probabilistic fingerprint codes
- Differential Privacy
- Geometric discrepancy. An illustrated guide
