Congenial Differential Privacy under Mandated Disclosure

The curation and dissemination of large-scale datasets benefits science and society by supplying factual knowledge to assist discoveries, policy decisions, and promote transparency of information. As more data become accessible to more entities, however, the unobstructed access to information collected from individuals poses the risk of infringing on their privacy. Differential privacy is a mathematical concept that quantifies the extent of disclosure of confidential information in a database. It enjoys several advantages over its previous counterparts in statistical disclosure limitation. Most important of all, especially to data analysts who wish to conduct statistical inference on privatized data releases, is the transparency of the algorithm. The mechanism through which the privatized data release is generated can be spelled out in full, with its statistical properties fully understood. This enables analysts to incorporate it as part of a model, hence permitting the statistical validity of the resulting inference (Gong, 2020).

The protection of confidential data with differential privacy relies on the careful design of a probabilistic mechanism, one that can veil the microscopic identities of individual respondents while preserving the macroscopic aspects of the data with high fidelity. The probabilistic nature of the mechanism is necessary, and enables a tradeoff as such to be made (Dinur and Nissim, 2003). Typically, a differentially private mechanism injects a random perturbation into an otherwise deterministic query to be applied to the confidential database. One can say, then, that differentially private releases are “blurry” versions of the confidential data, just the same way a skilled Impressionist painter captures the essence of a pond of waterlilies without sketching out the contour of every petal and leaf.

When randomness is involved, however, certain truthful aspects of the data is invariably compromised, no matter how well-designed the privacy algorithm may be. Imagine if a picture of waterlilies was commissioned, not by an art collector, but by a botanist whose sole purpose is to study the structural formation of the plant, such as the exact length and width of its petals. She would be terribly disappointed at the Impressionist painting, even if it was the work of Claude Monet himself!

Circumstances in practice dictates that aspects of the data release may be deemed as unfit to be tampered with. These are usually key statistics reflecting the fundamental purpose of data collection, as required by law, policy, or other external constraints as put forth by the stakeholders. The data curator is mandated to disclose these statistics accurately at any expense, while at the same time shielding the remainder part of the data release with a veil of privacy. This poses a challenge to the design of the privacy mechanism subject to mandated disclosure. The central question is, how to integrate data privatization, an inherently random act, with the mandated disclosure of partial yet deterministic information, while maintaining both the logical consistency of the overall data release and the quality of the privacy protection.

In this work we conceptualize the privacy mechanism as one of the many phases of data processing. The concept of congeniality, or rather uncongeniality (Meng, 1994), is then relevant. The theory of uncongeniality was developed for investigating a seemingly paradoxical phenomenon discovered by researchers dealing with imputations for the U.S. Decennial Census and similar public-use data files. Fay (Fay, 1992) and Kott (Kott, 1995) found that one can have inconsistent variance estimation for multiple imputation inference (Rubin, 2004), even when both the imputation model and analysis procedure are valid. The issue turned out to be a mathematical incompatibility between the imputation model and the analysis procedure, even if neither is incompatible with the underlying model that generates the data. In other words, there is no probabilistically coherent model that can simultaneously imply the imputation model and the analysis procedure, a situation termed uncongeniality by Meng (Meng, 1994). To make matters worse, the imputation model, such as adopted by the Census Bureau, is typically not disclosed to the analyst of the imputed data, or at least not fully (e.g., due to confidential information used to help better predict the missing values). The lack of transparency makes it impossible for the analyst to correct for the uncongeniality, and worse, even to realize the problem.

The framework of uncongeniality was later generalized to the multivariate setting (Xie and Meng, 2017) and to general multi-phase processing (Blocker and Meng, 2013), which covers the current application by the same overarching principles. Two properties are critical for good privacy practice: transparency and congeniality. When the protection of privacy must observe mandated constraints, our proposal is to use conditional distributions as derived from the original unconstrained differential privacy mechanism conditioning on invariant margins. This approach achieves both automatically. Transparency is automatic, because the conditional distribution is determined by the original unconstrained distribution and the invariant constraints, both fully disclosed by design. Congeniality stipulates the use of a single coherent probabilistic model to ensure both differential privacy and mandated disclosure. This requirement is automatically satisfied when we use the conditional distribution derived from the original differential privacy mechanism, restricted solely to obey the mandated disclosure. A third advantage is that our proposal does not need any additional choice of procedural ingredients, such as projection distance, which is required by optimization-based post-processing such as adopted by the Census TopDown algorithm (Abowd et al., 2019).

There is, however, no free lunch. The first price we pay for congenial privacy is computational. Sampling from a distribution truncated on some space, as determined by the invariant margins, is generally not trivial, especially when the truncated region is of irregular shape. The second price is that we may pay more privacy loss budget than necessary, since the budget designed for the original mechanism depends on the sensitivity of the query measure on the unconstrained space, which is larger than that for the constrained space. When deriving the appropriate class of conditional distributions for the constrained mechanism, the new privacy loss budget should ideally be calibrated directly according to the query behavior on the constrained space, as opposed to be inherited from the unconstrained mechanism, which ensures a likely overly conservative level of privacy protection for the entire space. When the analytical complexity and computational requirements for the two approaches of budget calibration are similar, we certainly recommend the former.

Let $x=\left(x_{1},\ldots,x_{n}\right)$ denote a database consisting of $n$ individuals, and $\mathcal{X}$ the space on which it is defined. A query function $s:\mathcal{X}\to\mathbb{R}^{d}$ embodies the knowledge contained in the database that stakeholders – scientists, policy makers and the general public – would like to learn. What determines the value of $s\left(x\right)$ is of course $x$, or equivalently all its component $x_{i}$ values, corresponding to individual respondents included in the database. It is precisely these individuals records, or the $x_{i}$’s, that are the subject of privacy protection. How can the data curator say useful things about $s\left(x\right)$, while saying barely anything about each of the $x_{i}$’s?

The mechanism that can instill privacy into the curator’s release appeals to randomness. A random query function $M:\mathcal{X}\to\mathbb{R}^{d}$ is said to satisfy $\epsilon$-differential privacy (Dwork et al., 2006), if for all pairs of neighboring datasets $\left(x,x^{\prime}\right)\in\mathcal{X}\times\mathcal{X}$, we have that

for all Borel-measurable sets $B\in\mathscr{B}\left(\mathbb{R}^{d}\right)$. In this work, the term neighboring datasets means that $x$ and $x^{\prime}$ differ by exactly one individual’s record, i.e. for some $j=1,\ldots,n$, $x_{j}\neq x_{j}^{\prime}$ but for all $i\neq j$, $x_{i}=x_{i}^{\prime}$. Write $\mathtt{d}\left(x,x^{\prime}\right)=1$ if $x$ and $x^{\prime}$ are neighbors. This concept of neighbor is employed in the definition of $\epsilon$-bounded differential privacy (Abowd et al., 2019), and is distinct from the original formulation which defined neighbors as a pair that differ from each other by the addition or deletion of a single record. There are many ways to design an $\epsilon$-differentially private algorithm $M$, among which the most widely known and implemented are the Laplace and the Double Geometric algorithms (Dwork et al., 2006; Fioretto and Van Hentenryck, 2019), both are additive $\epsilon$-differentially private mechanisms.

Note that the definition of either the Laplace or the Double Geometric mechanism presents not just one, but a collection of mechanisms that can be written as $\left\{M_{\epsilon}\right\}$, indexed by $\epsilon>0$ the privacy loss budget allocated to the mechanism in question. When regarded as a sequence of statistical procedures, $\epsilon$ serves as an indicator of the statistical quality of the output (with larger $\epsilon$ for higher quality) that can be used to offer interpretation and to guide its own choice. This point will be immediately useful in Section 1.4.

An important reason that differential privacy is embraced by the statistics community is that it defines privacy in the language of probability, induced by the mechanism that injects randomness in the data release. An impactful consequence is that the distributional specification of the mechanism can be made fully transparent without sabotaging the promised protection. This opens the door for systematic analysis of the statistical property of mechanisms, which is in turn crucial to the accurate interpretation of statistical inference from privatized data releases (Gong, 2019a). The clarity both in definition and in implementation makes up the statistical intelligibility of differential privacy as a data processing procedure.

We discuss the statistical interpretation of the privacy mechanism, which is what served as inspiration for the conditioning approach to construct the invariant-respecting mechanism in the first place. The degree of protection exerted by a privacy mechanism on the confidential database is seen as a calculated limit on the statistical knowledge it is able to supply, as a function of the privacy loss budget allotted to the mechanism. Compare quantities

which are the analyst’s prior probability about the value of the $i$th entry of the dataset, versus her posterior probability if an $\epsilon$-differentially private query released a report $B$. Thus, the statistical meaning of $M_{\epsilon}$ can be explained as follows.

Theorem 1.3 says that, any release generated by an $\epsilon$-differentially private procedure sharpens the analyst’s knowledge about $x_{i}$ by at most a factor of $\exp(\epsilon)$. This interpretation provides a direct link between the differential privacy promise and the actual posterior risk of disclosure due to the release of the random query $M_{\epsilon}$.

Recall that the definition of the Laplace and the Double Geometric mechanisms are both well-defined for any $\epsilon>0$. However, in the limiting case of $\epsilon\to 0$, i.e. the privacy loss budget becomes increasingly restrictive, both algorithms amount to adding noise with increasingly large variance to the confidential query. At $\epsilon=0$, neither mechanism remains well-defined since the distributions of the noise component become improper due to the infinite cardinality of their respective domains. Nevertheless, the definition of $\epsilon$-differential privacy allows for the expression with $\epsilon=0$. A mechanism is $0$-differentially private if one cannot gain any discriminatory knowledge from its release about the underlying database whatsoever. In other words, the analyst’s knowledge about the individual state of $x_{i}$ must remain the same as her prior. This notion can be explained consistently with Theorem 1.3, by observing that

where the limit is implied by (1.5). This inspires the following deliberate construction of $M_{0}$ as a $0$-differentially private procedure.

Definition 1.4 grants conceptual continuity to $M_{0}$, a perfectly meaningful object in the privacy sense but lacking statistical intelligibility from the mechanistic point of view. For practical purposes, $M_{0}$ should be taken to mean the suppression procedure, which supplies vacuous knowledge to the analyst about the state of affairs of the database. Theoretically, the meaning of $M_{0}$ as a probabilistic mechanism cannot be supplied by ordinary probabilities, because any probability specification represents a set of specific knowledge about relative frequencies of any pair of states. However, its meaning can be quantified precisely in the more general framework of imprecise probability, as Section 5 will discuss.

While privacy protection is called for, the data curator may be simultaneously mandated to disclose certain aspects of the data as they are exactly observed, without subjecting them to any privacy protection. This collection of information is referred to as invariant information, or invariants. In practice, invariants are often defined according to a set of exact statistics calculated based on the confidential database (Ashmead et al., 2019). For example, suppose $s$ is the histogram query which tabulates the population residing in each county of the state of New Jersey from the 2020 U.S. Census. When producing a differentially private version of the histogram, the Census Bureau is constitutionally mandated to report the total population of each state as enumerated. This means that the privatized histogram $M(x^{*})$ must possess the same total population size as $s(x^{*})$, where $x^{*}$ the confidential Census microdata; or in notation, $\left\|M\left(x^{*}\right)\right\|=\left\|s\left(x^{*}\right)\right\|$.

Suppose that the Double Geometric mechanism is to be applied to the histogram query $s$. Due to the random nature of the perturbations, a single realization of the mechanism will with high probability produce $\left\|M\left(x^{*}\right)\right\|\neq\left\|s\left(x^{*}\right)\right\|$. Furthermore $M\left(x^{*}\right)$ has a positive probability of consisting negative cell counts, which is logically impossible of the confidential query $s\left(x^{*}\right)$. The challenge of privacy preservation under mandated disclosure is thus to find an alternative mechanism, say $\tilde{M}$, such that every realization of $\tilde{M}$ meets all the requirement of mandated information disclosure, while preserving the promise of differential privacy.

Let $\mathcal{X}^{*}\subset\mathcal{X}$ be the set of $x$’s that obey the given invariants. In turn, $\mathcal{X}^{*}$ defines the set of values that the query must satisfy as

Note that implicitly, $\mathcal{S}^{*}=\mathcal{S}^{*}\left(x^{*}\right)$ is a set-valued function of the confidential dataset $x^{*}$, because the invariant knowledge we intend to impose on the private release is implied by $x^{*}$.

A random mechanism $\tilde{M}$ satisfies the mandated disclosure if

That is, whenever applied to a database conformal to the mandated disclosure, with mathematical certainty $\tilde{M}$ is also conformal to the mandated disclosure. The size and complexity of the restricted $\mathcal{S}^{*}$ (and $\mathcal{X}^{*}$) relative to their original spaces are crucial to the overall extent to which privacy of the residual information in the database can be protected, a point we will revisit in Section 5.1.

There may be many ways to construct a random mechanism $\tilde{M}$, but all are not equally desirable. We argue that $\tilde{M}$ should be constructed in a principled manner, and a constructive way to achieve that is to use conditional distributions of unconstrained privacy mechanisms. The resulting mechanism can be easily tuned to retain its differential privacy promise, while ensuring its congenial integration into the data processing pipeline, preserving the statistical intelligibility of its releases.

Let $M$ be a valid $\epsilon$-differentially private mechanism, which generates outputs that typically do not obey the invariant requirement $M\left(x\right)\in\mathcal{S}^{*}$, even if $x\in\mathcal{X}^{*}$. A natural idea to force the requirement onto $M$ is via conditioning. Define a modified privatization mechanism $M^{*}$, such that the probability distribution it induces is the same as the conditional distribution of $M$ subject to the constraint that $M\left(x\right)\in\mathcal{S}^{*}$. For what’s next, we’ll use the notation $Z\overset{L}{=}W$ to mean $Z$ and $W$ are identically distributed, and $M\left(x\right)\mid M\left(x\right)\in\mathcal{S}^{*}$ denotes a well-specified conditional distribution $P(M\left(x\right)\mid M\left(x\right)\in\mathcal{S}^{*})$. Also assume for now $P(M\left(x\right)\in\mathcal{S}^{*})>0$. We have the following theorem.

Our proof above might create an impression that only $\gamma\geq 0$ is permissible, but Sections 4 and 5.1 will supply two examples both with $\gamma<0$. Negative $\gamma$ may sound paradoxical, for it seems to suggest that better privacy protection can be achieved by disclosing some information. However, we must be mindful that differential privacy is not about protecting privacy in absolute terms. Rather, it is about controlling the additional disclosure risk from releasing the privatized data to the users (or hackers), relative to what they know before the release. The presence or absence of mandated invariants would ex ante constitute two different bodies of knowledge, hence any additional privacy protection would carry different interpretations too. We also emphasize that Theorem 2.1 generalizes to cases where $P(M(x)\in\mathcal{S}^{*})=0$, such as when it is a linear subspace of $\mathbb{R}^{d}$ and the privacy mechanism is continuous. The proof is a bit more involved in order to properly define $P(M\left(x\right)\mid M\left(x\right)\in\mathcal{S}^{*})$, which we will discuss in future work. However, this complication is not a concern for discrete privatization mechanisms, such as within the Census TopDown algorithm (Abowd et al., 2019).

Theorem 2.1 holds broadly for arbitrary kinds of $\epsilon$-differentially private mechanisms, as well as any deterministic invariant information about either the database or the query function that can be expressed in a set form. It lends itself to the same kind of posterior interpretation enjoyed by unconstrained differentially private mechanisms. Specifically, if $M^{*}_{\epsilon}$ is the constrained differentially private procedure constructed based on the unconstrained procedure $M_{\epsilon}$, according to the specifications of Theorem 2.1, then for all $x\in\mathcal{X}^{*}$ such that $\exists x^{\prime}\in\mathcal{X}^{*}$ so that $\mathtt{d}\left(x,x^{\prime}\right)=1$, and $\forall B\in\mathscr{B}\left(\mathcal{S}^{*}\right)$, the analyst’s posterior probability $\pi\left(x_{i}=\omega\mid x\in\mathcal{X}^{*},M_{\epsilon}^{*}\left(x\right)\in B\right)$ is bounded in between

This an interval that bears structural resemblance to (1.5), thanks to the conditional nature of $M^{*}$ which allows for statistical information from privacy mechanisms, constrained or otherwise, to be interpreted in the same (hence congenial) way.

The definition of $\epsilon$-differential privacy has the property that, if a mechanism $M$ is $\epsilon_{1}$-differentially private, then for all $\epsilon_{2}\geq\epsilon_{1}$, $M$ is also $\epsilon_{2}$-differentially private. If the invariant information does not substantially disrupt the neighboring structure of the sample space of the database, a notion we will make precise later in Section 5, what Theorem 2.1 says is that enforcing the invariant $\mathcal{X}^{*}$ onto the unconstrained mechanism $M$ via conditioning costs $\left(1+\gamma\right)$ times – and at most twice since $\gamma$ can always be set to $1$ – the privacy loss budget allotted to $M$. When a more cost-effective value of $\gamma$ is hard to determine, a simplest way to ensure privacy loss budget $\epsilon$ for $M^{*}$ is to use a budget of $\epsilon_{0}=\epsilon/2$ for the unconstrained mechanism $M$ to begin with; see Section 3.

Let $p$ denote the probability distribution, either a mass function or a density function, induced by the unconstrained differentially private algorithm $M$ which depends on the confidential query $s^{*}$. Further denote $p^{*}$ to be the corresponding conditional distribution of $p$ constrained on the invariant set $\mathcal{S}^{*}$. The constrained privacy mechanism requires samples from $p^{*}$. A simplest, though often inefficient or event impractical, method is rejection sampling. Since

where $c=\int_{\mathcal{S}^{*}}p\left(s\right)ds$, one can opt for a proposal density $q$ with support $\mathcal{S}^{*}$ such that $\sup_{s\in\mathcal{S}^{*}}[p(s)/q(s)]\leq R$, and accept a sample $s\sim q$ with probability $p(s)/Rq(s)$. This encompasses the option to set $q=p$, the unconstrained privacy kernel itself, and keep sampling until the sample falls into $\mathcal{S}^{*}$. This strategy is clearly inefficient in general, and impossible when $c=0$.

Efficient algorithm tailor-made to specifications of $\mathcal{S}^{*}$ are possible. Here, we present in Algorithm 1 a generic approach based on Metropolized Independent Sampling (MIS; Liu, 1996), for the most common case in which the mandated invariants are expressed in terms of a consistent system of linear equalities and inequalities

Here $A$ and $B$ are $d_{A}\times d$ and $d_{B}\times d$ matrices with ranks $d_{A}<d$ and $d_{B}<d$ respectively, and $a$ and $b$ vectors with length $d_{A}$ and $d_{B}$ respectively. The algorithm requires a proposal index set $\mathcal{I}$, a subset of $\left\{1,\ldots,d\right\}$ of size $d-d_{A}$ such that $\text{rank}\left(A_{[\mathcal{I}^{c}]}\right)=d_{A}$, where $A_{[\mathcal{J}]}$ is the submatrix of $A$ consisting of all columns whose indices belong to $\mathcal{J}$. For each $A$, the choice of $\mathcal{I}$ may not be unique, and can have a potential impact on the efficiency of the algorithm.

This algorithm is applicable to both discrete and continuous data and privatization schemes, and it does not require the normalizing constant for $p^{*}$. In Section 3 below, we use it to construct a mechanism for differentially private demographic contingency tables subject to both linear equality and inequality invariant constraints.

While Theorem 2.1 always holds with $\gamma=1$, it likely sets a loose bound on the ratio between $P\left(M^{*}\left(x\right)\in B\right)$ and $P\left(M^{*}\left(x^{\prime}\right)\in B\right)$, hence declaring an overly “conservative” nominal level of privacy loss induced by $M^{*}$. Depending on how the invariant $\mathcal{S}^{*}$ interacts with the distributional property of the unconstrained mechanism $M$ in a specific instance, $\gamma$ can be shown to take smaller values, adding more “bang of the buck” to the privacy loss budget, so to speak. Three examples are given below.

Our third example is a less trivial example of $\gamma<0$, which is actually provided by the congenial mechanism in Example 4.1. There, although the guaranteed privacy loss budget is still $\epsilon$, in applying Theorem 2.1, $k$ must be set to $2$ or greater, because under the constraint of fixed sum, the nearest neighbors among binary vectors $(x,x^{\prime})$ must have $\mathtt{d}(x,x^{\prime})=2$. Hence the $\epsilon$ privacy bound implies $k(1+\gamma)=2(1+\gamma)=1$, yielding $\gamma=-0.5$.

This example also reminds us that a major cause of information leakage due to invariants is the structural erosion to the underlying data space, such as making $\mathtt{d}(x,x^{\prime})=1$ (as measured on the original space $\mathcal{X}$) impossible. In reality, the unconstrained data space $\mathcal{X}$ is typically regular, and contains $\mathcal{X}^{*}$ as a proper subset. We should expect to find many $x\in\mathcal{X}^{*}$, and many (if not many more) $x^{\prime}\in\mathcal{X}\backslash\mathcal{X}^{*}$ such that $x$ and $x^{\prime}$ are neighbors, near or far. Knowing that the confidential dataset must belong to $\mathcal{X}^{*}$ categorically rules out the possibility that all the $x^{\prime}$’s can be the confidential dataset, weakening the differential privacy promise by eliminating the neighbors. If the invariant is sufficiently restrictive such that $\mathcal{X}^{*}$ becomes topologically small relative to $\mathcal{X}$, it may be the case that for some $x\in\mathcal{X}^{*}$, all of its original immediate neighboring datasets are not in $\mathcal{X}^{*}$:

in which case we say that the neighboring structure of the original data space of the database is substantially disrupted, as seen in Example 4.1. If the disruption is so substantial that neighbors of any distance cease to exist, we say that the neighborhood structure is completely destroyed:

Then, even for the constrained mechanism $M^{*}$, the $\epsilon$-differential privacy promise becomes vacuously true, since no possible neighboring pairs remain for which the concept of privacy is applicable. However, Example 5.2 demonstrates that vacuous privacy promise can occur without the neighborhood structures completely destroyed.

In general, it is conceptually difficult to parse out the share of responsibility on privacy attributable to the data curator under any scenario of mandated disclosure. If certain information is made public, then any information that it logically implies cannot be expected to be protected, either. The best that we can expect any privacy mechanism to deliver, then, is protection over information that truly remains. Notions that serve the equivalent purposes as $\mathcal{X}^{*}$ and $\mathcal{S}^{*}$ have been proposed in the literature for expositions of new notions of differential privacy, including blowfish and pufferfish privacy (He et al., 2014; Kifer and Machanavajjhala, 2012), where the privacy guarantee is re-conceptualized on the restricted space modulo any structural erosion to the original sample space due to external or auxiliary information available to an attacker. When interpreting the promise of Theorem 2.1, we shall pay due diligence to the case in which immediate neighbors no longer exists, and talk about the $\epsilon$-differential privacy guarantee only for those $k$-neighbors that actually do.