Gradual Differentially Private Programming

Differential privacy to the rescue.  In 2006, Cynthia Dwork put forward the first compelling notion of privacy-preserving data mining, together with basic mechanisms to realize it.⁶ Dubbed differential privacy (DP), this notion provides strong privacy guarantees, independent of the considered classes of attack and the auxiliary information available to the attacker (as leveraged in the SERVEL attack).

In general, a computation over a dataset is deemed differentially private if adding an extra individual to the dataset produces only a “negligible” variation of the computation outcome. This means that an attacker observing the computation outcome will be able to infer about the same information, whether any individual opts in or out of the dataset. Individuals will thus have no sensible reason to refrain from participating in such a data analysis. Figure 1 summarizes the main ingredients of the formal definition of DP.

Notably, we can achieve DP by output perturbation: if $f:D\to R$ is a real-valued query, $D$ denoting the dataset universe, we can construct a differentially private variant of $f$ by adding statistical noise to its output. Moreover, this noise should be calibrated according to the sensitivity of $f$, defined as:

Intuitively, $S\left(f\right)$ captures how much $f$’s output can vary upon the addition of an extra individual to $f$’s input dataset. For example, if the query $f$ counts the number of individuals in a dataset who are 40 years or older, then $S\left(f\right)$ = 1 since adding an individual to the dataset can change the count by at most 1.

Figure 2 describes the Laplacian mechanism, which formalizes this privatization strategy. In general, the greater the sensitivity of query $f:D\to R$, the more noise we must add to guarantee ε-DP, and, as a corollary, the less precise the private mechanism also becomes. Therefore, to keep results as accurate as possible, while guaranteeing ε-DP, it is crucial to have bounds for the sensitivity of queries that are both sound and as tight as possible. This has proved to be a daunting task.

We have witnessed this phenomenon personally in a course on data privacy that we created at the University of Chile, where students have hardly been able to derive sensitivities for elementary queries. To illustrate the class of sensitivity analysis required, let us consider Figure 3a, which shows a simple program where privacy depends on a dynamically obtained input value: if b is True, the function is 1-sensitive, so the program is private, but if b is False, the added noise is insufficient to ensure privacy. In fact, this problem goes way over the heads of undergraduate students. Recently, Min Lyu et al. uncovered serious flaws in multiple DP algorithms published in recognized venues, with stringent peer-review processes.⁸ This calls for systematic and principled approaches for developing and verifying DP programs.

Fuzz.  In 2010, the first language explicitly designed for reasoning about sensitivity and DP emerged: Fuzz.¹¹ The core idea revolves around the use of linear types to track sensitivity, making every well-typed program inherently differentially private.

Fuzz’s type system approximates sensitivity to the number of times variables are used in an expression. Generally, it offers two types for functions: $R\to R$, indicating unrestricted use of the argument (that is, ∞-sensitive), and $R-\circ R$, denoting a function that uses its argument at most once (that is, 1-sensitive). For instance, $f\left(x\right)=x+1$ can be typed as $R-\circ R$, but $g\left(x\right)=x+x$ only as $R\to R$, unless a technique known as metric scaling is used, which allows $g$ to be typed as $R-\circ !{}_{2}R$.

Additionally, Fuzz introduces the type $〇R$ for noisy computations, representing probability distributions over real numbers. For example, a function like add_noise, which adds Laplace-distributed noise with scaling parameter 1/ε to a real number, has type $R-\circ 〇R$. Suppose also a 1-sensitive function over_40 that computes how many people in a dataset are 40 years or older (typed as $D-\circ R$). Then we can build a differentially private version of this function as follows:

def over_40_DP(d):
  return add_noise(over_40(d))

The function over_40_DP is typed as $D-\circ 〇R$, and is formally guaranteed to be ε-DP.

Despite its contributions, Fuzz and some successors have limitations. In particular, Fuzz primarily supports the basic ε-DP variant, not accommodating more advanced versions, such as (ε,δ)-DP or Renyí-DP. Furthermore, some can be overly conservative in assessing program sensitivity, potentially requiring programmers to possess advanced knowledge about the sensitivity of their programs and scale types accordingly.

Jazz.  In response to these limitations and to enhance the adoption of DP in programming languages, we developed the Jazz language.¹⁶ Jazz is inspired by Fuzz¹¹ and Duet,¹⁰ but offers more precise sensitivity analysis without sacrificing simplicity. It is designed to support advanced DP variants and higher-order programming.

Like Duet, Jazz consists of two mutually defined sub-languages: one for sensitivity analysis and the other for privacy. The sensitivity sub-language allows fine-grained sensitivity information to be explicitly declared in types. For instance, the function $g\left(x\right)=x+x$ has the type $(x:R)\to \left\{2x\right\}R$, indicating a latent sensitivity of $2x$. In Jazz, the latent sensitivity of the function only matters whenever the function is applied. The type syntax also enables precise reasoning about multiple variables simultaneously. For instance, consider the following:

z = input()
def plus_z(y:ℝ)→{z+y}ℝ:
  def unused():
    z * y
  return z+y

Function plus_z is 1-sensitive in z and y (notation z+y), since unused is never applied. Jazz generalizes this idea of latent sensitivity accounting to other type constructors, such as data structures: the sensitivity of a computation that uses a tuple of values only considers the components that are effectively used, lazily, instead of eagerly accounting for the sensitivity of all the components. This inherently leads to more accurate analysis without resorting to complex scaling operators.

The privacy sub-language of Jazz allows reasoning about the privacy of individual variables. For instance, a function of type $(x:R·d)\to \left\{\epsilon x\right\}R$ satisfies ε-DP with respect to its argument $x$, if the relational distance of $x$ is at most d. The relational distance measures how much an argument can vary in two separate executions, often setting $d=1$ to recover the standard setting of two datasets that differ by only one individual. For instance, the previously introduced add_noise function is typed in Jazz as $(x:R·1)\to \left\{\epsilon x\right\}R$. The type system guarantees that in programs such as add_noise(y + z), the sum of the relational distances of y and z is at most 1.

Gradual sensitivity.  We developed the theory of gradual sensitivity typing, implemented in a prototype language called GSoul.¹ GSoul is close to the sensitivity sublanguage of Jazz, but also supports imprecise sensitivity information, either in the form of an interval (such as $\left[2,8\right]x$ to denote a function that is at least 2-sensitive and at most 8-sensitive in its argument $x$) or a fully unknown sensitivity (such as $?x$ if the sensitivity with respect to $x$ is not statically known, which is indeed equivalent to the interval $[0,\infty ]x$). As a gradually typed language, GSoul treats imprecise information optimistically during typechecking, but backs such optimism with dynamic checks during program execution to ensure other statically stated invariants are not violated.

Figure 3c shows how we can use the unknown sensitivity to smoothly handle the statically unpredictable sensitivity of may_square. The program optimistically typechecks because it is plausible for may_square to be 1-sensitive in y. When run, if b happens to be True, execution proceeds without error. Conversely, if b happens to be False, then a runtime exception is raised when add_noise is applied, reporting that the argument violates the 1-sensitivity requirement.

In addition to making adoption of sensitivity typing smoother by permitting parts of sensitivity information to be statically and precisely specified, and parts left unknown or imprecise, gradual sensitivity typing also provides an alternative to handle recursive functions in an exact, albeit dynamically checked manner. This is especially useful when dealing with recursive functions on which the sensitivity with respect to an argument depends on the number of recursive calls (unless one adopts dependent types as in Gaboardi et al.⁷). In GSoul, it suffices to declare the sensitivity of a recursive function as unknown and let dynamic checking account for the actual sensitivity observed at runtime.

DP with gradual sensitivity.  Gradual sensitivity opens at least two different ways to address DP programming. The approach described earlier consists in adding noise based on a fixed expected sensitivity: add_noise expects a 1-sensitive argument and adds noise accordingly. If the argument comes from a gradually typed computation that happens to violate this fixed requirement during execution, then a runtime error is raised. This approach has the benefit of ensuring a known accuracy of the result. On the downside, one could be adding too much noise, for instance if the argument happens to come from a computation that is insensitive, or whose sensitivity is strictly less than the expected one. While it is sound to do so, it unnecessarily sacrifices accuracy.

A dual approach consists of making a computation private by adding the amount of noise that corresponds to the observed sensitivity at runtime. This approach cannot fail dynamically and ensures that noise is appropriately calibrated to the actual sensitivity of the computation. However, its downside is that the resulting accuracy could be disastrous: if one erroneously implements a function as ∞-sensitive while it was intended to have a finite sensitivity, the result accuracy will be annihilated by an excessive amount of noise. Here, a new concern emerges—that of reporting to users the actual amount of noise added to a final result, without endangering privacy.

Both approaches appear viable and useful, possibly even within the lifecycle of the same codebase. A practical language for gradual DP programming should ideally support both, letting users determine which best fits their needs.