💻 computer science

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms

This paper establishes the first unconditional space lower bounds for user-level differential privacy by introducing a novel multi-player communication game that links memory requirements to the necessity of tracking over-active users, proving an exponential separation between private and non-private space complexity for fundamental statistical estimation tasks like distinct element counting.

Original authors: Alessandro Epasto, Xin Lyu, Pasin Manurangsi

Published 2026-02-13

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alessandro Epasto, Xin Lyu, Pasin Manurangsi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, bustling library. Every day, thousands of people (users) come in to check out books, return them, or just browse. Your job is to keep a running tally of how many unique people are currently in the library.

However, there's a catch: You must protect everyone's privacy.

If you keep a perfect, detailed list of who is in the library at every second, you could accidentally reveal that "Bob" was there at 3:00 PM, which might be a secret he wants to keep. To fix this, you use a special "privacy filter" (Differential Privacy) that adds a little bit of "static" or "noise" to your counts so no one can be identified.

The Big Question

For a long time, computer scientists knew that adding this privacy filter made your calculations less accurate. But they assumed you could still do it efficiently with a small notebook (low memory).

This paper asks a new, surprising question: Does keeping a secret actually require a giant memory?

The authors say: Yes. To keep the data private and accurate, you are forced to carry a massive amount of information in your head (or memory), even if you don't want to.

The Core Problem: The "Over-Active" Users

Imagine that while most people visit the library once or twice a day, a few "super-fans" visit 10,000 times.

The Privacy Risk: If you count every single visit from these super-fans, their identity becomes obvious. The privacy filter requires you to "cap" (limit) how much these super-fans can influence your final count.
The Memory Trap: To know who to cap, you first have to identify who the super-fans are. You have to remember their names and track their visits in real-time.

The paper proves that you cannot cheat this. You cannot use a clever trick or a shortcut to guess who the super-fans are without actually remembering them. If you try to forget them to save space, your privacy guarantee breaks, or your count becomes wildly inaccurate.

The Analogy: The "Secret Handshake" Game

To prove this, the authors invented a strange game involving a line of people passing notes.

The Setup: Imagine a line of $P$ people. Each person holds a bag of mixed-up cards. Some cards belong to a secret group of "VIPs" (the super-fans), and others belong to regular people.
The Goal: Each person must look at their bag, pick out a specific number of cards, and pass a note to the next person.
The Rule: The group wins only if they successfully identify the VIPs without letting the VIPs show up too many times in the final pile.
The Catch: The note passed between people can only be so long (limited memory).

The authors proved mathematically that to win this game, the people must pass a note that is huge. If they try to pass a tiny note, they will inevitably fail to identify the VIPs correctly.

What does this mean for computers?
The "note" is the computer's memory. The "game" is the algorithm trying to count people privately. The proof shows that if you want to be accurate and private, you must use a lot of memory. There is no magic shortcut.

The Real-World Impact

The authors tested this on a very common problem: Counting Distinct Elements (like counting how many unique users are active on a website).

Before this paper: We knew how to do this privately, but it required a lot of memory (polynomial space). We wondered, "Can we do it with a tiny amount of memory, like we do when we don't care about privacy?"
After this paper: The answer is No.
- Non-private: You can count unique users with a tiny notebook (very efficient).
- Private: You need a massive filing cabinet (exponentially more memory).

The Takeaway

The title of the paper, "Keeping a Secret Requires a Good Memory," is the perfect summary.

In the world of data privacy, you can't have your cake and eat it too. If you want to protect people's secrets while still getting accurate results, you are forced to remember a lot more than you thought necessary. The "cost" of privacy isn't just slower speed or less accuracy; sometimes, the cost is massive memory usage.

This is a fundamental law of the universe for private algorithms, not just a bug in current software. It tells engineers that for certain tasks, they simply cannot build a "lightweight" private app; they must build a "heavy" one.

1. Problem Statement

The paper addresses a critical gap in the understanding of Differential Privacy (DP): the trade-off between privacy and memory efficiency (space complexity).

Context: While the trade-off between accuracy and privacy is well-studied, the inherent memory cost of maintaining user-level DP in streaming algorithms remains largely unexplored.
The Gap: Prior work established that some private algorithms require polynomial space, but it was an open question whether this was a fundamental limitation or just a limitation of current algorithms. Specifically, for the CountDistinct problem (estimating the number of unique elements in a stream), existing private algorithms use space proportional to $T^{1/3}$ (where $T$ is the stream length), whereas non-private algorithms can solve it with poly-logarithmic space ( $\tilde{O}(1)$ ).
The Question: Is the high memory usage of private algorithms a mathematical necessity, or can a more efficient private algorithm be designed?
Specific Focus: The paper focuses on User-Level Differential Privacy in the turnstile model (where users can both add and remove items from the stream).

2. Methodology

The authors introduce a novel proof technique that bridges communication complexity and differential privacy.

A. The Core Intuition: "Contribution Capping"

The authors argue that to achieve user-level DP, algorithms often must limit the influence of "over-active" users (heavy hitters) who contribute disproportionately to the dataset.

The Strategy: A common approach is to identify users who exceed a contribution threshold $w$ and cap their future updates.
The Memory Bottleneck: Identifying and tracking these $k$ heavy users requires storing their IDs. Intuitively, remembering a set of $k$ users requires $\Omega(k)$ bits of memory.
The Hypothesis: The paper posits that this memory-intensive strategy is not just a heuristic but fundamentally necessary for certain problems.

B. The Novel Proof Technique: Multi-Player Communication Game

To prove this necessity unconditionally (without relying on cryptographic assumptions), the authors design a communication game called AvoidHeavyHitters:

Setup: There are $P$ players and a referee. A hidden set of "heavy" users $C$ (size $k$ ) is distributed among the players.
The Game: Players process data in rounds. In each round, they must output a subset of users that satisfies specific size constraints.
The Constraint: The players win if they can collectively ensure that no user from the hidden set $C$ appears in too many submitted subsets.
The Link: The authors prove that to win this game with high probability, the players must communicate $\tilde{\Omega}(k)$ bits.
Reduction: They show that any accurate, low-space private streaming algorithm for CountDistinct can be converted into a protocol that wins this communication game. Therefore, if the communication game requires high communication, the streaming algorithm must require high memory.

3. Key Contributions

First Unconditional Space Lower Bounds: The paper establishes the first information-theoretic (unconditional) space lower bounds for user-level DP streaming algorithms. Previous bounds relied on cryptographic assumptions (e.g., Dinur et al., 2023).
Resolution of Open Problems: It resolves open questions posed by Jain et al. (2023) and Cummings et al. (2025) regarding the CountDistinct problem.
Exponential Separation: The work proves an exponential separation between the space complexity of private and non-private algorithms for natural statistical tasks.
- Non-private: $\tilde{O}(1)$ space (e.g., HyperLogLog).
- Private: $\tilde{\Omega}(T^{1/3})$ space is necessary for certain error rates.
Generalization: The technique is shown to apply to a broad class of problems beyond CountDistinct, including MaxSelect (finding the most popular item) and Quantile estimation.

4. Main Results

Theorem 2.1 (Main Lower Bound for CountDistinct)

For a stream with $(w, k)$ -occurrency bounds (where at most $k$ users have more than $w$ updates), any user-level DP algorithm that achieves an additive error of $h$ must use space:
$M \geq \tilde{\Omega}\left( \frac{kw}{h^2} \right)$

Corollary 2.2 (Specific Regime):
In a regime where $w \approx T^{2/3}$ and $k \approx T^{1/3}$ , to achieve an error of $\eta \approx T^{1/3}$ , any private algorithm requires space:
$M \geq \tilde{\Omega}(T^{1/3})$
This matches the space complexity of the best-known private algorithm (Cummings et al., 2025), proving it is nearly optimal.

Extension to Other Problems

Theorem 2.3 extends these lower bounds to:

MaxSelect: Finding the most frequent element.
Quantile: Estimating the rank of elements.
In both cases, achieving low error rates with user-level DP necessitates polynomial space, whereas non-private versions require only poly-logarithmic space.

5. Significance and Impact

Fundamental Limit: The paper demonstrates that for certain natural statistical problems, privacy and low memory usage are mathematically incompatible. You cannot have both high accuracy and low memory in a private setting for these tasks.
Shift in Research Focus: It suggests that researchers should stop searching for "magic" low-space private algorithms for these specific problems and instead focus on:
- Relaxing privacy definitions (e.g., event-level vs. user-level).
- Relaxing accuracy requirements.
- Accepting higher memory costs as a necessary price for privacy.
New Proof Paradigm: The "AvoidHeavyHitters" communication game provides a powerful new tool for proving lower bounds in differential privacy, potentially applicable to other problems that have resisted previous lower-bound techniques.
Practical Implication: For systems designers, this implies that deploying user-level private analytics for tasks like counting active users or tracking popular items will inherently require significant memory resources, impacting the scalability of such systems.

Summary Conclusion

The paper "Keeping a Secret Requires a Good Memory" fundamentally changes our understanding of the cost of privacy. By proving that tracking "over-active" users is an unavoidable requirement for user-level differential privacy in streaming settings, the authors establish that the high memory usage of existing private algorithms is not a flaw, but a fundamental necessity. This resolves long-standing open problems and sets a new benchmark for the space complexity of private algorithms.