On differential privacy and adaptive data analysis with bounded space

DOI10.1007/978-3-031-30620-4_2MaRDI QIDQ6085262zbMATH OpenOpenAlexFDO

Authors Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou

Publication date 12 December 2023

Published in Advances in Cryptology – EUROCRYPT 2023 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.05707

zbMATH Keywords

adaptive data analysisdifferential privacy

Mathematics Subject Classification ID

General topics in the theory of data (68P01) Informational aspects of data analysis and big data (94A16) Authentication, digital signatures and secret sharing (94A62)

Abstract: We study the space complexity of the two related fields of differential privacy and adaptive data analysis. Specifically, (1) Under standard cryptographic assumptions, we show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy, compared to the space needed without privacy. To the best of our knowledge, this is the first separation between the space complexity of private and non-private algorithms. (2) The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries. We revisit previous lower bounds at a foundational level, and show that they are a consequence of a space bottleneck rather than a sampling bottleneck. To obtain our results, we define and construct an encryption scheme with multiple keys that is built to withstand a limited amount of key leakage in a very particular way.

Recommendations

• Algorithmic stability for adaptive data analysis
• Algorithmic stability for adaptive data analysis
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• The algorithmic foundations of differential privacy
• Make Up Your Mind: The Price of Online Queries in Differential Privacy

Cites work

• A Leakage-Resilient Mode of Operation
• A Pseudorandom Generator from any One-way Function
• Algorithmic stability for adaptive data analysis
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Collusion-secure fingerprinting for digital data
• Computational Differential Privacy
• Deterministic communication vs. partition number
• Distributed Private Data Analysis: Simultaneously Solving How and What
• Does learning require memorization? a short tale about a long tail
• Exposure-resilient functions and all-or-nothing transforms
• Fingerprinting codes and the price of approximate differential privacy
• Leakage-resilient cryptography from minimal assumptions
• Non-uniform bounds in the random-permutation, ideal-cipher, and generic-group models
• On the complexity of differentially private data release, efficient algorithms and hardness results
• Optimal probabilistic fingerprint codes
• Optimal space lower bounds for all frequency moments
• Preserving statistical validity in adaptive data analysis (extended abstract)
• Private PAC learning implies finite Littlestone dimension
• Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali
• Random Oracles and Auxiliary Input
• Random oracles and non-uniformity
• Rectangles Are Nonnegative Juntas
• Separation of the monotone NC hierarchy
• Super-linear time-memory trade-offs for symmetric encryption
• Theory of Cryptography
• Theory of Cryptography
• Towards defeating backdoored random oracles: indifferentiability with bounded adaptivity
• When is memorization of irrelevant training data necessary for high-accuracy learning?

Cited in

(2)

• Multi-instance randomness extraction and security against bounded-storage mass surveillance
• Title not available (Why is no real title available?)

This page was built for publication: On differential privacy and adaptive data analysis with bounded space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6085262)