📊 statistics

A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

This paper proposes a high-entropy differential privacy implementation that satisfies mandatory linear aggregation invariants (such as state totals) with near-certainty while deriving new privacy guarantees and addressing theoretical questions regarding the null space of correlation matrices.

Original authors: Ryan Lafferty, Anindya Roy

Published 2026-07-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ryan Lafferty, Anindya Roy

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 a librarian trying to share a secret list of book borrowers with the public, but you have a strict promise: you must never reveal who checked out a specific book. To keep this promise, you decide to add a little bit of "static" or noise to the list, like adding a few random names that weren't actually there, or changing a few names slightly. This is the core idea of Differential Privacy, a mathematical shield used by governments and tech giants to let us learn from data without exposing individuals.

However, there's a catch. Sometimes, the rules of the game demand that certain big-picture numbers stay exactly the same. For instance, the total number of people in a state must match the sum of the people in all its counties. If you just add random noise to every single county's count, the state total will likely drift off, breaking the math and making the data useless for official records. This creates a tug-of-war: you want to add enough noise to hide individuals, but you also need the noise to cancel itself out perfectly so the big totals remain untouched. This paper tackles the tricky math of how to add that "perfectly canceling" noise without breaking the privacy shield.

The Puzzle of the Perfectly Balanced Noise

Imagine you are a chef trying to bake a cake for a very picky judge. The judge has two rules:

The Taste Rule: Every bite of the cake must taste exactly like a specific flavor (say, vanilla) to ensure the recipe is followed.
The Weight Rule: The total weight of the cake must be exactly 1,000 grams. No more, no less.

Now, imagine you are adding "secret ingredients" (noise) to the batter to protect the recipe's origin. If you just sprinkle a handful of vanilla beans into every bowl randomly, the total weight of the cake will likely be wrong. You might end up with 1,005 grams or 990 grams. If you try to fix the weight by just subtracting the extra grams from the top, you ruin the "Taste Rule" because the top layer now tastes different from the rest.

This is the exact problem the authors, Ryan Lafferty and Anindya Roy, are solving. In the world of data, the "cake" is a database (like the U.S. Census), the "bites" are individual data points (like a person's count in a neighborhood), and the "secret ingredients" are the random numbers added to hide identities. The "Weight Rule" represents linear invariants—constraints like "the total population of a state must equal the sum of its counties."

The Old Way vs. The New Way

Previously, data scientists tried to solve this by adding noise first and then "fixing" the totals afterward. They would add random numbers to every county, see that the state total was off, and then adjust the numbers to force the total back to the correct amount.

The authors argue that this "fix-it-later" approach is like trying to smooth out a crumpled piece of paper by pressing it flat with a heavy book. It might look flat, but the paper is now crushed and distorted. In math terms, this "projection" method squeezes the noise into a corner, making it less random (lower entropy) and potentially weakening the privacy guarantees. It's as if the noise becomes predictable, which is bad for privacy.

The "Maximum Entropy" Solution

Instead of fixing the mess after the fact, the authors propose a smarter way to mix the ingredients from the start. They developed a method to generate noise that is correlated.

Think of it like a team of dancers. If every dancer moves randomly, the group looks chaotic, but the center of the group might drift away. If you want the group to stay in one spot (the invariant), you can't just tell them to stop moving. Instead, you choreograph them so that when one dancer steps forward, another steps back by the exact same amount. They are moving together, but their movements are linked so the group stays put.

The paper proposes a "Maximum Entropy" implementation. In simple terms, "entropy" is a measure of randomness or surprise. The authors want the noise to be as unpredictable and "surprising" as possible (high entropy) while still obeying the rule that the total sum is zero. They use a mathematical tool called Projected Gradient Descent (a fancy way of saying "iteratively adjusting the dance steps") to find the perfect choreography.

They also use a technique called POCS (Projection onto Convex Sets), which is like a game of "hot and cold" where you keep adjusting the noise until it fits perfectly inside a specific shape defined by the rules. The result is a noise vector that:

Looks like the standard noise we expect (Gaussian or Laplace) for every individual piece of data.
Sums to exactly zero (or the required invariant) every single time.
Is as random as mathematically possible, ensuring the strongest privacy protection.

What They Found and Proved

The authors didn't just guess this would work; they proved it.

The Guarantee: They showed that even with this complex, linked noise, the system still provides the standard mathematical guarantee of Differential Privacy (specifically, $(\epsilon, \delta)$ -DP). This means the privacy shield is just as strong as the old, simpler methods, even though the noise is now "dancing" in a coordinated way.
The Math Magic: A big part of their work involved solving a difficult puzzle about correlation matrices (mathematical grids that describe how variables relate to each other). They provided a partial solution to an open question about the "null space" of these matrices—essentially figuring out exactly which patterns of linked noise are possible.
The Simulation: They tested their method with simulated data, including a scenario mimicking the U.S. Census with states, counties, and blocks. They showed that when they added noise to the smallest blocks, the county and state totals remained perfectly intact, while the individual block counts were still obscured enough to protect privacy.

Why It Matters

This isn't just a theoretical game. The U.S. Census Bureau and other agencies face this exact problem every time they release data. They have constitutional mandates that say state totals cannot be changed, but they also need to protect the privacy of every single person.

The authors' method offers a "principled" way to do this. Instead of hacking the data after the fact, they provide a way to generate the data correctly from the beginning. They also noted that this approach could be useful for other types of data, like smart meter readings (where the total energy use of a neighborhood must match the sum of individual homes) or wearable device data.

In short, the paper shows that you don't have to choose between accurate totals and strong privacy. By using a bit of advanced math to choreograph the noise, you can have both: a dataset that is perfectly consistent with the big rules, yet completely safe for the little details.

Technical Summary: A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

Problem Statement
Differential privacy (DP) is the standard for data privacy, typically implemented by adding independent Gaussian or Laplace noise to database queries. However, in applications like the U.S. Decennial Census, certain aggregate queries (e.g., state-level population totals) are subject to "invariants"—linear constraints mandated by law or policy that cannot be perturbed. Standard DP mechanisms, which add independent noise, violate these constraints because the sum of independent noise terms is rarely zero.

While post-processing techniques exist to force aggregates to match invariants, such methods alter the noise distribution, potentially modifying the privacy guarantees and interpretation of the DP mechanism. Furthermore, projecting unconstrained noise onto the space of invariants often results in a solution with lower entropy, reducing the utility of the released data. The core challenge is to design a noise addition mechanism that:

Maintains the specified marginal distributions (e.g., Laplace or Gaussian) at the granular level.
Satisfies linear aggregation constraints (invariants) with probability one.
Maximizes the entropy of the noise vector within the constrained subspace to ensure the noise is "as independent as possible" given the constraints.

Methodology
The authors propose an Aggregation Invariant Differential Privacy (AI-DP) mechanism. The approach treats both Gaussian and Laplace noise as scale mixtures of normal distributions. The methodology proceeds in three main stages:

Formalizing the Invariant Data Universe:
The authors redefine the neighboring database structure for DP guarantees. Instead of the standard single-entry swap, neighboring databases in the invariant universe ( $D_{Q,A,c}$ ) must differ in a way that preserves the linear constraints $AQ(D) = c$. This often requires swapping multiple entries simultaneously. Privacy guarantees are then evaluated within this constrained universe.
Correlation Matrix Construction via POCS:
To satisfy the constraints $AX = 0$ while maintaining specific marginals, the noise vector $X$ is modeled as a multivariate normal $N(0, \Sigma)$ where $\Sigma = DRD$ . Here, $D$ is a diagonal matrix of scales (derived from the mixing distribution), and $R$ is a correlation matrix satisfying $RB = 0$ (where $B = AD$).
Finding such an $R$ is formulated as a Convex Feasibility Problem (CFP): finding a matrix in the intersection of three convex sets:
- $C_1$ : The cone of positive semi-definite matrices.
- $C_2$ : The affine subspace of matrices with unit diagonal entries (correlation matrices).
- $C_3$ : The subspace of matrices where $RB = 0$.
  The authors employ the Cyclic Projection Onto Convex Sets (POCS) algorithm to find a solution $R$ in this intersection.
Maximum Entropy Optimization:
The POCS solution provides a valid correlation matrix but does not guarantee maximum entropy. To satisfy the requirement of maximizing entropy (Requirement [R3]), the authors formulate an optimization problem:
$R_{opt} = \min_{R \in C_n} \left[ \text{Tr}(B^T R B) - \tau \log \det(K^T R K) \right]$
where the first term enforces the constraint (ideally zero) and the second term (with tuning parameter $\tau$ ) penalizes low entropy. This is solved using a Projected Gradient Algorithm.

Key Contributions

Theoretical Privacy Guarantees: The paper derives $(\epsilon, \delta)$ -DP guarantees for the proposed mechanism under the invariant data universe. It proves that the mechanism satisfies these guarantees for databases differing by entries that preserve the invariants.
Correlation Matrix Theory: The work contributes new results to the literature on correlation matrices, specifically regarding the null space of correlation matrices.
- It provides a necessary and sufficient condition for the existence of a correlation matrix $R$ such that $RB=0$ for a rank- $k$ constraint matrix $B$ .
- It characterizes the set of solutions as faces of the elliptope (the set of correlation matrices) and identifies the maximum-rank solution as lying in the relative interior of this set.
Algorithmic Framework: The paper presents a practical algorithm (Algorithm 1 and 2) for sampling noise from scale mixtures of normals under linear equality constraints, utilizing POCS and projected gradient descent.
Handling Hierarchical Constraints: The methodology is shown to be adaptable to nested hierarchical structures (e.g., blocks $\to$ counties $\to$ states), ensuring consistency across all levels while preserving top-level invariants.

Results

Numerical Illustrations:
- Simple Aggregation: For the case where the constraint vector is a vector of ones (summing to a total), the authors show that a specific intraclass correlation matrix (rank $n-1$ ) is the unique max-rank and max-entropy solution, eliminating the need for iterative optimization in this specific case.
- Laplace Mechanism: By representing Laplace noise as a Gaussian scale mixture, the authors successfully generated 100 samples of Laplace-distributed noise satisfying a single linear constraint. The Q-Q plots confirmed the marginal distribution, and constraint violations were negligible (order of $10^{-6}$ ).
- Convergence: The projected gradient algorithm demonstrated convergence in minimizing the loss function while maintaining the penalty term for entropy.
Probability of Violation: The paper analyzes the probability that a random constraint vector fails to be "balanced" (a condition required for the existence of a nulling correlation matrix). It provides a tail bound showing that for vectors with heavy-tailed entries, the probability of infeasibility is exponentially small.

Significance and Claims
The authors claim that this work provides a principled way to address aggregation constraints in DP implementation without sacrificing the standard interpretation of differential privacy. By ensuring the noise vector has maximum entropy within the constraints, the method minimizes the distortion of the data's statistical properties beyond what is necessary to satisfy the invariants.

The paper explicitly states that it contributes to the discussion on how to analyze released data and interpret DP semantics in the presence of invariants, a gap identified in previous census implementation literature (Abowd et al., 2022). The methodology is presented as having general utility beyond census data, applicable to any setting involving sampling from normal mixture models under linear equality constraints, such as smart-meter and wearable-device data.

The authors remain modest regarding the scope, noting that the current work focuses on linear equality constraints and that future work is needed to address more general systems of linear equality and inequality constraints (e.g., non-negativity). They also note that the theoretical proof regarding the null space of correlation matrices is a partial solution to an open question in that field.