Ted is writing things

On privacy, research, and privacy research.

Converters between differential privacy variants

This is a small collection of interactive converters between differential privacy variants.

A diagram with four text elements: Pure DP, Zero-concentrated DP, Gaussian DP,
and Approximate DP. Arrows go from Pure DP to Zero-concentrated DP, from
Gaussian DP to Zero-concentrated DP, from Gaussian DP to Approximate DP, and
from Zero-concentrated DP to Approximate

Pure DP to zero-concentrated DP

If a mechanism satisfies \(\varepsilon\)-DP with \(\varepsilon=\) , then it also satisfies \(\rho\)-zero-concentrated DP with \(\rho=\) . The converse is not true.

Zero-concentrated DP to approximate DP

If a mechanism satisfies \(\rho\)-zero-concentrated DP with \(\rho=\) , then it also satisfies \((\varepsilon,\delta)\)-DP with \(\varepsilon=\)  and \(\delta=\) . The converse is not true.

Gaussian DP to approximate DP

If a mechanism satisfies \(\mu\)-Gaussian DP with \(\mu=\) , then it also satisfies \((\varepsilon,\delta)\)-DP with \(\varepsilon=\)  and \(\delta=\) . The converse is not true.

You can also use this to compute the \((\varepsilon,\delta)\)-DP guarantees of a Gaussian mechanism of standard deviation \(\sigma\) applied to a mechanism of global \(L^2\) sensitivity \(\Delta_2\), by replacing \(\mu\) above by \(\Delta_2/\sigma\).

Gaussian DP to zero-concentrated DP

If a mechanism satisfies \(\mu\)-Gaussian DP with \(\mu=\) , then it also satisfies \(\rho\)-zero-concentrated DP with \(\rho=\) . The converse is not true.

Frequently asked questions

What are all these weird definitions?

  • Pure DP is the name of the original definition of differential privacy. Check out this blog post series for a friendly introduction to the field.
  • Approximate DP introduces an additional parameter that allows for a small chance of privacy failure. Previous blog posts of mine explain what it can be used for, and provide a more precise characterization of the guarantee provided by this definition.
  • Zero-concentrated DP gives a bound on the average privacy loss, for many kinds of average at once. You can read more about it in this blog post.
  • Gaussian DP asserts that the privacy loss of a mechanism is bounded by the privacy loss of a Gaussian mechanism with certain parameters. It is a special case of a larger class of definitions called \(f\)-DP, introduced in this paper.

Are there conversion results in the reverse direction?

  • Converting from zero-concentrated DP to pure DP is impossible.
  • Converting from approximate DP to zero-concentrated DP or to Gaussian DP is also impossible (unless \(\delta=0\)).
  • Converting from zero-concentrated DP to Gaussian DP seems like it should be possible, but I don't know of any existing result in the literature.

How do you deal with floating-point issues?

The short answer is "not in a very robust way, don't do this in production".

The long answer is that I did somewhat of an effort to detect and avoid numerical stability issues, but all the math is still done in floating-point space, so there will be approximations errors, and rounding is not done in conservative directions. Here is an overview of what I did for each formula.

  • For pure DP to zero-concentrated DP, and for Gaussian DP to zero-concentrated DP, the formulas are pretty simple, so I didn't do anything special.
  • For zero-concentrated DP to approximate DP, there is one main failure mode: the conversion formula can return a \(\delta\) that is so small that it rounds to zero. The code checks that this doesn't happen and returns an error if it does.
  • The conversion from Gaussian DP to approximate DP is surprisingly tricky. First, the CDF of the Gaussian distribution, a critical building block of the conversion formula, is difficult to compute in an accurate way. I use the technique introduced in this paper to get a good approximation. Then, multiple things can go wrong.
    1. There's a multiplication by \(e^\varepsilon\) in the formula, so this can easily become \(+\infty\) in floating-point space if \(\varepsilon\) is large. The code returns an error if it happens1.
    2. For some parameters combinations, \(\delta\) can round down to zero. The code checks that this doesn't happen and returns an error if it does.
    3. The formula requires computing the difference between two terms \(a\) and \(b\), where \(a\) can be very close to \(b\). This can be very imprecise when done in floating-space. I'm not sure whether this can happen in this context, but if it does, the code should catch the problem and return an error.

In addition, a number of these conversions are implemented using a binary search. The code checks that the result of the binary search is "close enough" to the target value, and returns an approximation error if it's not.

This is all still very ad hoc, so for production use cases, I recommend using a library that does these conversions using symbolic or arbitrary-precision computation, like Tumult Analytics.

Why didn't you use symbolic or arbitrary-precision computation, then?

I couldn't find a JavaScript library that had support for all the mathematical building blocks I needed.

Why am I getting errors telling me that my parameter choices are bad?

The code contains various validation checks, besides the floating-point stuff outlined above. Some of these checks are for fairly obvious issues: all parameters must be strictly positive, and \(\delta\) must be smaller than 1. Some are for more subtle problems: the conversion from zero-concentrated DP to approximate DP only holds for \(\varepsilon\ge\rho\), which means that some conversions are impossible. Similar issues arise for the Gaussian DP to approximate DP conversion: \(\mu\)-Gaussian DP implies \((0,\delta)\) for some \(\delta\), so if you specify a smaller \(\delta\) than that, the formula will not be able to find a positive \(\varepsilon\).

I tried to catch all these possible problems in friendly error messages2. Please let me know if you encounter an issue that isn't caught by one.

Are you logging anything?

No. Everything runs locally, in your browser. You can check the source code or run this page while completely offline if you'd like to be sure.

(But please publish your privacy parameters!)

I'm grateful to Clément Canonne, Moshe Shenfeld, and Yu-Xiang Wang for helping me figure out the right conversion results, very grateful to Yaya D. Dia for helping me understand how to compute the formula necessary for Gaussian DP to approximate DP conversion in floating-point space, and extra super grateful to Thomas Steinke for properly writing up the proof of the tight conversion between pure DP and zero-concentrated DP.

  1. I think I could probably rearrange some of the terms in the formula to make it happen less (so, make it work for a wider range of parameters). If you need this, please let me know. (Or send me a patch. The source code is one right click → "View page source" away.) 

  2. In total, there are 11 different possible error messages you can get across the different converters. You can probably reach 10 of them fairly easily. If you manage to reach all 11, please let me know! 

All opinions here are my own, not my employer's.   |   Feedback on these posts is very welcome! Please reach out via e-mail (se.niatnofsed@neimad) or Twitter (@TedOnPrivacy) for comments and suggestions.   |   Interested in deploying formal anonymization methods? My colleagues and I at Tumult Labs can help. Contact me at oi.tlmt@neimad, and let's chat!