Differential Privacy on Finite Computers

arXiv:1709.05396v1 [] 15 Sep 2017

Victor Balcer∗
Salil Vadhan†
Center for Research on Computation & Society
School of Engineering & Applied Sciences
Harvard University
vbalcer@g.harvard.edu, salil vadhan@harvard.edu
September 19, 2017

Abstract
We consider the problem of designing and analyzing differentially private algorithms that
can be implemented on discrete models of computation in strict polynomial time, motivated
by known attacks on floating point implementations of real-arithmetic differentially private
algorithms (Mironov, CCS 2012) and the potential for timing attacks on expected polynomialtime algorithms. We use a case study the basic problem of approximating the histogram of
a categorical dataset over a possibly large data universe X . The classic Laplace Mechanism
(Dwork, McSherry, Nissim, Smith, TCC 2006 and J. Privacy & Confidentiality 2017) does not
satisfy our requirements, as it is based on real arithmetic, and natural discrete analogues, such
as the Geometric Mechanism (Ghosh, Roughgarden, Sundarajan, STOC 2009 and SICOMP
2012), take time at least linear in |X |, which can be exponential in the bit length of the input.
In this paper, we provide strict polynomial-time discrete algorithms for approximate histograms whose simultaneous accuracy (the maximum error over all bins) matches that of the
Laplace Mechanism up to constant factors, while retaining the same (pure) differential privacy
guarantee. One of our algorithms produces a sparse histogram as output. Its “per-bin accuracy” (the error on individual bins) is worse than that of the Laplace Mechanism by a factor
of log |X |, but we prove a lower bound showing that this is necessary for any algorithm that
produces a sparse histogram. A second algorithm avoids this lower bound, and matches the
per-bin accuracy of the Laplace Mechanism, by producing a compact and efficiently computable
representation of a dense histogram; it is based on an (n + 1)-wise independent implementation
of an appropriately clamped version of the Discrete Geometric Mechanism.

∗

Supported by NSF grant CNS-1237235 and CNS-1565387.
http://seas.harvard.edu/~ salil. Supported by NSF grant CNS-1237235, a Simons Investigator Award, and
a grant from the Sloan Foundation.
†

1

1

Introduction

Differential Privacy [DMNS06] is by now a well-established framework for privacy-protective statistical analysis of sensitive datasets. Much work on differential privacy involves an interplay between
statistics and computer science. Statistics provides many of the (non-private) analyses that we
wish to approximate with differentially private algorithms, as well as probabilistic tools that are
useful in analyzing such algorithms, which are necessarily randomized. From computer science,
differential privacy draws upon a tradition of adversarial modeling and strong security definitions,
techniques for designing and analyzing randomized algorithms, and considerations of algorithmic
resource constraints (such as time and memory).
Because of its connection to statistics, it is very natural that much of the literature on differential privacy considers the estimation of real-valued functions on real-valued data (e.g. the
sample mean) and introduces noise from continuous probability distributions (e.g. the Laplace
distribution) to obtain privacy. However, these choices are incompatible with standard computer
science models for algorithms (like the Turing machine or RAM model) as well as implementation
on physical computers (which use only finite approximations to real arithmetic, e.g. via floating
point numbers). This discrepancy is not just a theoretical concern; Mironov [Mir12] strikingly
demonstrated that common floating-point implementations of the most basic differentially private
algorithm (the Laplace Mechanism) are vulnerable to real attacks. Mironov shows how to prevent
his attack with a simple modification to the implementation, but this solution is specific to a single
differentially private mechanism and particular floating-point arithmetic standard. His solution increases the error by a constant factor and is most likely more efficient in practice than the algorithm
we will use to replace the Laplace Mechanism. However, he provides no bounds on asymptotic running time. Gazeau, Miller and Palamidessi [GMP16] provide more general conditions for which
an implementation of real numbers and a mechanism that perturbs the correct answer with noise
maintains differential privacy. However, they do not provide an explicit construction with bounds
on accuracy and running time.
From a theoretical point of view, a more appealing approach to resolving these issues is to avoid
real or floating-point arithmetic entirely and only consider differentially private computations that
involve discrete inputs and outputs, and rational probabilities. Such algorithms are realizable in
standard discrete models of computation. However, some such algorithms have running times that
are only bounded in expectation (e.g. due to sampling from an exponential distribution supported
on the natural numbers), and this raises a potential vulnerability to timing attacks. If an adversary
can observe the running time of the algorithm, it learns something about the algorithm’s coin tosses,
which are assumed to be secret in the definition of differential privacy. (Even if the time cannot
be directly observed, in practice an adversary can determine an upper bound on the running time,
which again is information that is implicitly assumed to be secret in the privacy definition.)
Because of these considerations, we advocate the following principle:
Differential Privacy for Finite Computers:
We should describe how to implement differentially private algorithms on discrete models of computation with strict bounds on running time (ideally polynomial in the bit
length of the input) and analyze the effects of those constraints on both privacy and
accuracy.
Note that a strict bound on running time does not in itself prevent timing attacks, but once we have
such a bound, we can pad all executions to take the same amount of time. Also, while standard
discrete models of computation (e.g. randomized Turing machines) are defined in terms of countable
2

rather than finite resources (e.g. the infinite tape), if we have a strict bound on running time, then
once we fix an upper bound on input length, they can indeed be implemented on a truly finite
computer (e.g. like a randomized Boolean circuit).
In many cases, the above goal can be achieved by appropriate discretizations and truncations
applied to a standard, real-arithmetic differentially private algorithm. However, such modifications
can have a nontrivial price in accuracy or privacy, and thus we also call for a rigorous analysis of
these effects.
In this paper, we carry out a case study of achieving “differential privacy for finite computers”
for one of the first tasks studied in differential privacy, namely approximating a histogram of a
categorical dataset. Even this basic problem turns out to require some nontrivial effort, particularly
to maintain strict polynomial time, optimal accuracy and pure differential privacy when the data
universe is large.
We recall the definition of differential privacy.
Definition 1.1. [DMNS06] Let M : X n → R be a randomized algorithm. We say M is (ε, δ)differentially private if for every two datasets D and D ′ that differ on one row and every subset
S⊆R
Pr[M(D) ∈ S] ≤ eε · Pr[M(D ′ ) ∈ S] + δ
We say an (ε, δ)-differentially private algorithm satisfies pure differential privacy when δ = 0
and say it satisfies approximate differential privacy when δ > 0.
In this paper, we study the problem of estimating the histogram of a dataset D ∈ X n , which is
the vector c = c(D) ∈ NX , where cx is the number of rows in D that have value x. Histograms can
be approximated while satisfying differential privacy using the Laplace Mechanism, introduced in
the original paper of Dwork, McSherry, Nissim and Smith [DMNS06]. Specifically, to obtain (ε, 0)differential privacy, we can add independent noise distributed according to a Laplace distribution,
specifically Lap(2/ε), to each component of c and output the resulting vector c̃. Here Lap(2/ε) is the
continuous, real-valued random variable with probability density function f (z) that is proportional
to exp(−ε · |z|/2). The Laplace Mechanism also achieves very high accuracy in two respects:
Per-Query Error: For each bin x, with high probability we have |c̃x − cx | ≤ O(1/ε).
Simultaneous Error: With high probability, we have maxx |c̃x − cx | ≤ O(log(|X |)/ε).
Note that both of the bounds are independent of the number n of rows in the dataset, and so the
fractional error vanishes linearly as n grows.
Simultaneous error is the more well-studied notion in the differential privacy literature, but
we consider per-query error to be an equally natural concept: if we think of the approximate
histogram c̃ as containing approximate answers to the |X | different counting queries corresponding
to the bins of X , then per-query error captures the error as experienced by an analyst who may be
only interested in one or a few of the bins of c̃. The advantage of considering per-query error is that
it can be significantly smaller than the simultaneous error, as is the case in the Laplace Mechanism
when the data universe X is very large. It is known that both of the error bounds achieved by the
Laplace Mechanism are optimal up to constant factors; no (ε, 0)-differentially private algorithm for
histograms can achieve smaller per-query error or simultaneous error [HT10, BBKN14].
Unfortunately, the Laplace Mechanism uses real arithmetic and thus cannot be implemented on
a finite computer. To avoid real arithmetic, we could use the Geometric Mechanism [GRS12], which
adds noise to each component of c according to the 2-sided geometric distribution, Geo(2/ε), which
is supported on the integers and has probability mass function f (z) ∝ exp(−ε·|z|/2). However, this
3

mechanism uses integers of unbounded size and thus cannot be implemented on a finite computer.
Indeed, while the algorithm can be implemented with a running time that is bounded in expectation
(after reducing ε so that eε/2 and hence all the probabilities are rational numbers), truncating long
executions or allowing an adversary to observe the actual running time can lead to a violation of
differential privacy. Thus, it is better to work with the Truncated Geometric Mechanism of Ghosh,
Roughgarden and Soundararajan [GRS12], where we clamp each noisy count c̃x to the interval
[0, n]. We observe that the resulting probability distribution of c̃x , supported on {0, 1, . . . , n}, can
be described explicitly in terms of cx , ε and n, and it can be sampled in polynomial time using
only integer arithmetic (after ensuring eε/2 is rational). Thus, we obtain:
Theorem 1.2 (Bounded Geometric Mechanism, informal statement of Thm. 3.7). For every finite
X , n and ε ∈ (0, 1], there is an (ε, 0)-differentially private algorithm M : X n → {0, 1, . . . , n}X for
histograms achieving:
• Per-query error O(1/ε).
• Simultaneous error O(log |X |)/ε.
• Strict running time |X | · poly(N ), where N is the bit length of the input (n, ε and a dataset
D ∈ X n ).
We note that while we only consider our particular definition of per-query accuracy, namely
that with high probability |c̃x − cx | ≤ O(1/ε), Ghosh et al. [GRS12] proved that the output of the
Bounded Geometric Mechanism can be used (with post-processing) to get optimal expected loss
with respect to an extremely general class of loss functions and arbitrary priors. The same result
applies to each individual noisy count c̃x output by our mechanism, since each bin is distributed
according to the Bounded Geometric Mechanism (up to a modification of ε to ensure rational
probabilities).
The Bounded Geometric Mechanism is not polynomial time for large data universes X . Indeed,
its running time (and output length) is linear in |X |, rather than polynomial in the bit length
of data elements, which is log |X |. To achieve truly polynomial time, we can similarly discretize
and truncate a variant of the Stability-Based Histogram of Bun, Nissim and Stemmer [BNS16].
This mechanism only adds Lap(2/ε) noise to the nonzero components of cx and then retains only
the noisy values c̃x that are larger than a threshold t = Θ(log(1/δ)/ε). Thus, the algorithm only
outputs a partial histogram, i.e. counts c̃x for a subset of the bins x, with the rest of the counts
being treated as zero. By replacing the use of the Laplace Mechanism with the (rational) Bounded
Geometric Mechanism as above, we can implement this algorithm in strict polynomial time:
Theorem 1.3 (Stability-Based Histogram, informal statement of Thm. 5.2). For every finite
X , n, ε ∈ (0, 1] and δ ∈ (0, 1/n), there is an (ε, δ)-differentially private algorithm M : X n →
{0, 1, . . . , n}⊆X for histograms achieving:
• Per-query error O(1/ε) on bins with true count at least O(log(1/δ)/ε).
• Simultaneous error O(log(1/δ)/ε).
• Strict running time poly(N ), where N is the bit length of the input (n, ε and a dataset
D ∈ X n ).
Notice that the simultaneous error bound of O(log(1/δ)/ε) is better than what is achieved by
the Laplace Mechanism when δ > 1/|X |, and is known to be optimal up to constant factors in this
4

range of parameters (see Theorem 6.1). The fact that this error bound is independent of the data
universe size |X | makes it tempting to apply even for infinite data domains X . However, we note
that when X is infinite, it is impossible for the algorithm to have a strict bound on running time
(as it needs time to read arbitrarily long data elements) and thus is vulnerable to timing attacks
and is not implementable on a finite computer.
Note also that the per-query error bound only holds on bins with large enough true count
(namely, those larger than our threshold t); we will discuss this point further below.
A disadvantage of the Stability-based Histogram is that it sacrifices pure differential privacy. It
is natural to ask whether we can achieve polynomial running time while retaining pure differential
privacy. A step in this direction was made by Cormode, Procopiuc, Srivastava and Tran [CPST11].
They observe that for an appropriate threshold t = Θ(log(|X |)/ε), if we run the Bounded Geometric
Mechanism and only retain the noisy counts c̃x that are larger than t, then the expected number of
bins that remain is less than n + 1. Indeed, the expected number of bins we retain whose true count
is zero (“empty bins”) is less than 1. They describe a method to directly sample the distribution
of the empty bins that are retained, without actually adding noise to all |X | bins. This yields
an algorithm whose output length is polynomial in expectation. However, the output length is
not strictly polynomial, as there is a nonzero probability of outputting all |X | bins. And it is not
clear how to implement the algorithm in expected polynomial time, because even after making the
probabilities rational, they have denominators of bit length linear in |X |.
To address these issues, we consider a slightly different algorithm. Instead of trying to retain
all noisy counts c̃x that are larger than some fixed threshold t, we retain the n largest noisy
counts (since there are at most n nonzero true counts). This results in a mechanism whose output
length is always polynomial, rather than only in expectation. However, the probabilities still have
denominators of bit length linear in |X |. Thus, we show how to approximately sample from this
distribution, to within an arbitrarily small statistical distance δ, at the price of a poly(log(1/δ))
increase in running time. Naively, this would result only in (ε, O(δ))-differential privacy. However,
when δ is significantly smaller than 1/|R|, where R is the range of the mechanism, we can convert
an (ε, δ)-differentially private mechanism to an (ε, 0)-differentially private mechanism by simply
outputting a uniformly random element of R with small probability. (A similar idea for the case
that |R| = 2 has been used in [KLN+ 11, CDK17].) Since our range is of at most exponential size
(indeed at most polynomial in bit length), the cost in our runtime for taking δ ≪ 1/|R| is at most
polynomial. With these ideas we obtain:
Theorem 1.4 (Pure DP Histogram in Polynomial Time, informal statement of Thm. 4.14). For
every finite X , n and ε ∈ (0, 2], there is an (ε, 0)-differentially private algorithm M : X n →
{0, 1, . . . , n}⊆X for histograms achieving:
• Per-query error O(1/ε) on bins with true count at least O(log(|X |)/ε).
• Simultaneous error O(log(|X |)/ε).
• Strict running time poly(N ), where N is the bit length of the input (n, ε and a dataset
D ∈ X n ).
Both Theorems 1.3 and 1.4 only retain per-query error O(1/ε) on bins with a large enough true
count. We also prove a lower bound showing that this limitation is inherent in any algorithm that
outputs a sparse histogram (as both of these algorithms do).
Theorem 1.5 (Lower Bound on Per-Query Error for Sparse Histograms, Theorem 6.2). Suppose
that there is an (ε, δ)-differentially private algorithm M : X n → {0, 1, . . . , n}X for histograms that
5

always outputs histograms with at most n′ nonempty bins and has per-query error at most E on all
bins. Then


min{log |X |, log(1/δ)}
E≥Ω
,
ε

provided that ε > 0, ε2 > δ > 0 and |X | ≥ (n′ )2 .

This lower bound is similar in spirit to a lower bound of [BBKN14], which shows that no (ε, 0)differentially private PAC learner for “point functions” (functions that are 1 on exactly one element
of the domain) can produce sparse functions as hypotheses.
To bypass this lower bound, we can consider algorithms that produce succinct descriptions of
dense histograms. That is, the algorithm can output a polynomial-length description of a function
c̃ : X → [0, n] that can be evaluated in polynomial time, even though X may be of exponential size.
We show that this relaxation allows us to regain per-query error O(1/ε).
Theorem 1.6 (Polynomial-Time DP Histograms with Optimal Per-Query Accuracy, informal
statement of Thm. 7.3). For every finite X , n and ε ∈ (0, 1], there is an (ε, 0)-differentially private
algorithm M : X n → H for histograms (where H is an appropriate class of succinct descriptions of
histograms) achieving:
• Per-query error O(1/ε).
• Simultaneous error O(log(|X |)/ε).
• Strict running time poly(N ), where N is the bit length of the input (n, ε and a dataset
D ∈ X n ) for both producing the description of a noisy histogram c̃ ← M(D) and for evaluating
c̃(x) at any point x ∈ X .
The algorithm is essentially an (n+1)-wise independent instantiation of the Bounded Geometric
Mechanism. Specifically, we release a function h : X → {0, 1}r selected from an (n + 1)-wise
independent family of hash functions, and for each x ∈ X , we view h(x) as coin tosses specifying
a sample from the Bounded Geometric Distribution. That is, we let S : {0, 1}r → [0, n] be an
efficient sampling algorithm for the Bounded Geometric Distribution, and then c̃x = S(h(x)) is our
noisy count for x. The hash function is chosen randomly from the family conditioned on values c̃x
for the nonempty bins x, which we obtain by running the actual Bounded Geometric Mechanism
on those bins. The (n + 1)-wise independence ensures that the behavior on any two neighboring
datasets (which together involve at most n + 1 distinct elements of X ) are indistinguishable in the
same way as in the ordinary Bounded Geometric Mechanism. The per-query accuracy comes from
the fact that the marginal distributions of each of the noisy counts are the same as in the Bounded
Geometric Mechanism. (Actually, we incur a small approximation error in matching the domain of
the sampling procedure to the range of a family of hash functions.)
As far as we know, the only other use of limited independence in constructing differentially
private algorithms is a use of pairwise independence by [BBKN14] in differentially private PAC
learning algorithms for the class of point functions. Although that problem is related to the one we
consider (releasing a histogram amounts to doing “query release” for the class of point functions, as
discussed below), the design and analysis of our algorithm appears quite different. (In particular,
our analysis seems to rely on (n + 1)-wise independence in an essential way.)
Another potential interest in our technique is as another method for bypassing limitations of
synthetic data for query release. Here, we have a large family of predicates Q = {q : X → {0, 1}},
and are interested in differentially private algorithms that, given a dataset D = (x1 , . . . , xn ) ∈ X n ,
output a “summary” M(D) that allows one to approximate the answers to all of the counting queries
6

P
q(D) = i q(xi ) associated with predicates q ∈ Q. For example, if Q is the family of point functions
consisting of all predicates that evaluate to 1 on exactly one point in the data universe X , then this
query release problem amounts to approximating the histogram of D. The fundamental result of
Blum, Ligett, and Roth [BLR13] and successors show that this is possible even for families Q and
data universes X that are of size exponential in n. Moreover, the summaries produced by these
algorithms has the form of a synthetic dataset — a dataset D̂ ∈ X n̂ such that for every query q ∈ Q,
we have q(D̂) ≈ q(D). Unfortunately, it was shown in [UV11] that even for very simple families Q
of queries, such correlations between pairs of binary attributes, constructing such a differentially
private synthetic dataset requires time exponential in the bitlength log |X | of data universe elements.
Thus, it is important to find other ways of representing approximate answers to natural families Q
of counting queries, which can bypass the inherent limitations of synthetic data, and progress along
these lines was made in a variety of works [GRU12, CKKL12, HRS12, TUV12, CTUW14, DNT15].
Our algorithm, and its use of (n + 1)-wise independence, can be seen as yet another representation
that bypasses a limitation of synthetic data (albeit a statistical rather than computational one).
Indeed, a sparse histogram is simply a synthetic dataset that approximates answers to all point
functions, and by Theorem 1.5, our algorithm achieves provably better per-query accuracy than
is possible with synthetic datasets. This raises the question of whether similar ideas can also be
useful in bypassing the computational limitations of synthetic data for more complex families of
counting queries.

2

Preliminaries

Throughout this paper, let N be the set {0, 1, . . .}, N+ be the set {1, 2, . . .}. For n ∈ N, let [n] be
the nonstandard set {0, . . . , n}. Notice that |[n]| = n + 1. Given a set A and finite set B, we define
AB to be the set of length |B| vectors over A indexed by the elements of B.

2.1

Differential Privacy

We define a dataset D ∈ X n to be an ordered tuple of n ≥ 1 rows where each row is drawn from a
discrete data universe X with each row corresponding to an individual. Two datasets D, D ′ ∈ X n
are considered neighbors if they differ in exactly one row.
Definition 2.1. [DMNS06] Let M : X n → R be a randomized algorithm. We say M is (ε, δ)differentially private if for every pair of neighboring datasets D and D ′ and every subset S ⊆ R
Pr[M(D) ∈ S] ≤ eε · Pr[M(D ′ ) ∈ S] + δ
We say an (ε, δ)-differentially private algorithm satisfies pure differential privacy when δ = 0
and say it satisfies approximate differential privacy when δ > 0. Intuitively, the ε captures an
upper bound on an adversary’s ability to determine whether a particular individual is in the dataset.
And the δ parameter represents an upper bound of the probability of a catastrophic privacy breach
(e.g. the entire dataset is released). The common setting of parameters takes ε ∈ (0, 1] to be a
small constant and δ to be negligible in n.
The following properties of differentially private algorithms will be used in some of our proofs.
Lemma 2.2 (post-processing [DMNS06]). Let M : X n → Y be (ε, δ)-differentially private and
f : Y → Z be any randomized function. Then f ◦ M : X n → Z is (ε, δ)-differentially private.

7

Lemma 2.3 (group privacy [DMNS06]). Let M : X n → Y be (ε, δ)-differentially private. Let
D1 , D2 ⊆ X n be datasets such that D2 can be obtained by changing at most m rows of D1 . Then
for all S ⊆ Y
Pr[M(D1 ) ∈ S] ≤ emε · Pr[M(D2 ) ∈ S] + emε · δ/ε
Lemma 2.4 (composition [DL09]). Let M1 : X n → Y1 be (ε1 , δ1 )-differentially private and M2 :
X n → Y2 be (ε2 , δ2 )-differentially private. Define M : X n → Y1 ×Y2 as M(D) = (M1 (D), M2 (D))
for all D ∈ X n . Then M is (ε1 + ε2 , δ1 + δ2 )-differentially private.

2.2

Histograms

For x ∈ X , the point function cx : X n → N is defined to count the number of occurrences of x in
a given dataset, i.e. for D ∈ X n
cx (D) = |{i ∈ {1, . . . n} : Di = x}|
In this paper we focus on algorithms for privately releasing approximations to the values of all point
functions, also known as a histogram. A histogram is collection of bins, one for each element x
in the data universe, with the xth bin consisting of its label x and a count cx ∈ N.
2.2.1

Representations

The input to our algorithms is always a dataset (i.e. an element D ∈ X n ) and the outputs represent
approximate histograms. We consider the following histogram representations as our algorithms’
outputs:
• A vector in NX . We use {c̃x }x∈X to denote a histogram where c̃x ∈ N is the approximate
count for the element x.
• A partial vector h ∈ (X × N)∗ such that each element x ∈ X appears at most once in h with
each pair (x, c̃x ) ∈ X × N interpreted as element x having approximate count c̃x . Elements
x not listed in the partial vector are assumed to have count c̃x = 0. Implicitly an algorithm
can return a partial vector by releasing bins for a subset of X .
• A data structure, encoded as a string, which defines a function h : X → N where h(x),
denoted hx , is the approximate count for x ∈ X and hx is efficiently computable given this
data structure (e.g. time polynomial in the length of the data structure). In Section 7, this
data structure consists of the coefficients of a polynomial, along with some parameters.
Each representation is able to express any histogram over X . The difference between them is the
memory used and the efficiency of computing a count. For example, computing the approximate
count for x ∈ X , when using the data structure representation is bounded by the time it takes to
compute the associated function. But when using partial vectors, one only needs to iterate through
the vector to determine the approximate count.
We define the following class of histograms. Let Hn,n′ (X ) ⊆ NX be the set of all histograms
over X with integer counts in [0, n] (or N when n = ∞) and at most n′ of them nonzero. By using
partial vectors each element of Hn,n′ (X ) can be stored in O(n′ · (log n + log |X |)) bits, which is
shorter than the vector representation when n′ = o(|X |/ log |X |).

8

2.2.2

Accuracy

In order to preserve privacy, our algorithms return histograms with noise added to the counts.
Therefore, it is crucial to understand their accuracy guarantees. So given a dataset D ∈ X n we
compare the noisy count c̃x = M(D)x of x ∈ X (the count released by algorithm M) to its true
count, cx (D). We focus on the following two metrics:
Definition 2.5. A histogram algorithm M : X n → NX has (a, β)-per-query accuracy if
∀D ∈ X n ∀x ∈ X

Pr[|M(D)x − cx (D)| ≤ a] ≥ 1 − β

Definition 2.6. A histogram algorithm M : X n → NX has (a, β)-simultaneous accuracy if
∀D ∈ X n

Pr[∀x ∈ X |M(D)x − cx (D)| ≤ a] ≥ 1 − β

Respectively, these metrics capture the maximum error for any one bin and the maximum error
simultaneously over all bins. Even though simultaneous accuracy is commonly used in differential
privacy, per-query accuracy has several advantages:
• For histograms, one can provable achieve a smaller per-query error than is possible for simultaneous error. Indeed, the optimal simultaneous error for (ε, 0)-differentially private histograms
is a = Θ (log(|X |/β)/ε) whereas the optimal per-query error is a = Θ (log(1/β)/ε), which is
independent of |X | [HT10, BBKN14].
• Per-query accuracy may be easier to convey to an end user of differential privacy. For example,
it is the common interpretation of error bars shown on a graphical depiction of a histogram.

Figure 1: A histogram with error bars
• For many algorithms (such as ours), per-query accuracy is good enough to imply optimal
simultaneous accuracy. Indeed, an algorithm with (a, β)-per-query accuracy also achieves
(a, β · |X |)-simultaneous accuracy (by a union bound).
However, we may not always be able to achieve as good per-query accuracy as we want. So we will
also use the following relaxation which bounds the error only on bins with large enough true count.
Definition 2.7. A histogram algorithm M : X n → NX has (a, β)-per-query accuracy on
counts larger than t if
∀D ∈ X n ∀x ∈ X s.t. cx (D) > t

2.3

Pr[|M(D)x − cx (D)| ≤ a] ≥ 1 − β

Probability Terminology

Definition 2.8. Let Z be an integer-valued random variable.
1. The probability mass function of Z, denoted fZ , is the function fZ (z) = Pr[Z = z] for
all z ∈ Z.
9

2. The cumulative distribution function of Z, denoted FZ , is the function FZ (z) = Pr[Z ≤
z] for all z ∈ Z.
3. The support of Z, denoted supp(Z), is the set of elements for which f (z) 6= 0.
Definition 2.9. Let Y and Z be random variables taking values in discrete range R. The total
variation distance between Y and Z is defined as
∆(Y, Z) = max Pr[Y ∈ A] − Pr[Z ∈ A]
A⊆R

=

1 X
Pr[Z = a] − Pr[Y = a]
·
2
a∈R

Lemma 2.10. Let Y and Z be random variables over discrete range R. Total variation distance
has the following properties:
1. Y and Z are identically distributed, denoted Y ∼ Z, if and only if ∆(Y, Z) = 0.
2. Let T : R → R′ be any function with R′ discrete. Then
∆(T (Y ), T (Z)) ≤ ∆(Y, Z)
3. Let Y1 , Y2 , Z1 and Z2 be random variables over discrete range R. Then
∆((Y1 , Y2 ), (Z1 , Z2 )) ≤ ∆(Y1 , Z1 ) +
2.3.1

max

a∈R,A⊆R

Pr [Y2 ∈ A | Y1 = a] − Pr[Z2 ∈ A | Z1 = a]

Sampling

Because we are interested in the computational efficiency of our algorithms we need to consider the
efficiency of sampling from various distributions.
A standard method for sampling a random variable is via inverse transform sampling.
Lemma 2.11. Let U be uniformly distributed on (0, 1]. Then for any integer-valued random variable
Z we have FZ−1 (U ) ∼ Z where FZ−1 (u) is defined as min{z ∈ supp(Z) : FZ (z) ≥ u}.
If Z, the random variable we wish to sample, has finite support we can compute the inverse
cumulative distribution by performing binary search on supp(Z) to find the minimum. This method
removes the need to compute the inverse function of the cumulative distribution function and is
used in some of our algorithms.
2.3.2

Order Statistics

Definition 2.12. Let Z1 , . . . , Zℓ be integer-valued random variables. The i-th order statistic of
Z1 , . . . , Zℓ denoted Z(i) is the i-th smallest value among Z1 , . . . , Zℓ .
Lemma 2.13. Let Z1 , . . . , Zℓ be i.i.d. integer-valued random variables with cumulative distribution
function F . Then
FZ(ℓ) (z) = (F (z))ℓ
and

(
1
i
FZ(i) |Z(i+1) =vi+1 ,...Z(ℓ) =vℓ (z) = FZ(i) |Z(i+1) =vi+1 (z) =
F (z)/F (vi+1)

for all 1 ≤ i < ℓ and vi+1 ≤ vi+2 ≤ . . . ≤ vℓ all in the support of Z1 .
10

if z > vi+1
otherwise

From this lemma, we can iteratively sample random variables distributed identically to Z(ℓ) ,
Z(ℓ−1) , . . . , Z(i) without having to sample all ℓ of the original random variables. The inverse cumulative distributions for the order statistics are




−1
1/i
−1
1/ℓ
−1
u
·
F
(v
)
(u)
=
F
F
u
(u)
=
F
FZ−1
i+1
Z |Z
=vi+1 ,...Z =vℓ
(ℓ)
(i)

2.4

(i+1)

(ℓ)

Two-Sided Geometric Distribution

A common technique for creating differentially private algorithms is to perturb the desired output
with appropriately scaled Laplace noise. Because our algorithms’ outputs are counts, we focus on
a discrete analogue of the Laplace distribution as in [GRS12].
We say an integer-valued random variable Z follows a two-sided geometric distribution
with scale parameter s centered at c ∈ Z (denoted Z ∼ c + Geo(s)) if its probability mass
function fZ (z) is proportional to e−|z−c|/s . It can be verified that fZ and its cumulative distribution
function FZ are
!
( 1/s
e
· e−(c−z)/s
if z ≤ c
e1/s − 1
−|z−c|/s
e1/s +1
·
e
F
(z)
=
fZ (z) =
Z
1
1/s
−(z−c)/s
e +1
1 − 1/s · e
otherwise
e

+1

for all z ∈ Z. When c is not specified, it is assumed to be 0. The inverse cumulative distribution
of Z is
(

s ln (u) + s ln e1/s + 1 − 1
if u ≤ 1/2
−1

FZ (u) = c + 
1/s
−s ln (1 − u) − s ln e + 1
otherwise
or, equivalently,

&

FZ−1 (u) = c + s · sign(1/2 − u) ln(1 − |2u − 1|) + ln

2.5

e1/s + 1
2

!!'

+ ⌊2u⌋ − 1

Model of Computation

We analyze the running time of our algorithms with respect to the w-bit word RAM model
taking w = O(log N ) where N is the bit length of our algorithms’ inputs (D ∈ X n , ε and possibly
some additional parameters). In this model, memory accesses and basic operations (arithmetic,
comparisons and logical) on w-bit words are constant time. In addition, we assume the data
universe X = [m] for some m ∈ N. Some parameters to our algorithms are rational. We represent
rationals by pairs of integers.
Because our algorithms require randomness, we assume that they have access to an oracle that
when given a number d ∈ N+ returns a uniformly random integer between 1 and d inclusively.

3

The Geometric Mechanism

In this section we show how to construct a differentially private histogram using the Laplace Mechanism only requiring integer computations of bounded length.
As shown by Dwork, McSherry, Nissim and Smith [DMNS06], we can privately release a histogram by adding independent and appropriately scaled Laplace noise to each bin. Below we state
a variant that uses discrete noise, formally studied in [GRS12].

11

Algorithm 3.1. GeometricMechanism(D, ε) for D ∈ X n and ε > 0
1. For each x ∈ X , do the following:
(a) Set c̃x to cx (D) + Geo(2/ε) clamped to the interval [0, n]. i.e.


if Zx ≤ 0
0
where Zx = cx (D) + Geo(2/ε).
c̃x = n
if Zx ≥ n


Zx otherwise

(b) Release (x, c̃x ).

Note that the output of this algorithm is a collection of bins (x, c̃x ) which represents a partial
vector, but in this case we have a count for each x ∈ X so it defines a complete vector in Hn,|X |(X ) ⊆
NX . The privacy and accuracy properties of the algorithm are similar to those of the Laplace
Mechanism.
Theorem 3.2. GeometricMechanism(D, ε) has the following properties:
i. GeometricMechanism(D, ε) is (ε, 0)-differentially private [GRS12].
ii. GeometricMechanism(D, ε) has (a, β)-per-query accuracy for


2 1
a=
ln
ε β
iii. GeometricMechanism(D, ε) has (a, β)-simultaneous accuracy for


 

1
2 |X |
2
ln
ln
≤
a=
ε
ε
β
1 − (1 − β)1/|X |
Proof of ii-iii. Let Z ∼ Geo(2/ε). For any x ∈ X
Pr[|c̃x − cx (D)| ≤ a] ≥ Pr [|Z| ≤ ⌊a⌋]
= 1 − 2 · Pr[Z ≤ −⌊a⌋ − 1]
=1−2·
Now, for a =

l

2
ε

ln β1

m
Pr[|c̃x − cx (D)| ≤ a] ≥ 1 −

e−⌊a⌋·ε/2
eε/2 + 1

2·β
≥1−β
+1

eε/2

Part iii follows similarly after noting by independence of the counts that
Pr[∀x ∈ X |c̃x − cx (D)| ≤ a] ≥ Pr[|Z| ≤ ⌊a⌋]|X |

12

The accuracy bounds up to constant factors match the lower bounds for releasing a differentially
private histogram [HT10, BBKN14].
As presented above, this algorithm needs to store integers of unbounded size since Geo(2/ε)
is unbounded in magnitude. As noted in [GRS12], by restricting the generated noise to a fixed
range we can avoid this problem. However, even when the generated noise is restricted to a fixed
range, generating this noise via inverse transform sampling may require infinite precision. By
appropriately choosing ε, the probabilities of this noise’s cumulative distribution function can be
represented with finite precision, and therefore generating this noise via inverse transform sampling
only requires finite precision.
Proposition 3.3. For k ∈ N, n ∈ N+ and c ∈ [n], the algorithm GeoSample(k, n, c) has output
identically distributed to a two-sided geometric random variable with
 scale parameter 2/ε̃ centered
−k
at c clamped to the range [0, n] where we define ε̃ = 2 · ln 1 + 2
. Morever, GeoSample(k, n, c)
has running time poly(k, n).
We have chosen ε̃ so that the cumulative distribution function of a two-sided geometric random
variable with scale parameter 2/ε̃ clamped to [0, n] takes on only rational values with a common
denominator d. Therefore, to implement inverse transform sampling on this distribution we only
need to choose a uniformly random integer in {1, . . . , d} rather than a uniformly random variable
over (0, 1].
Algorithm 3.4. GeoSample(k, n, c) for k ∈ N, n ∈ N+ and c ∈ [n]
1. Let d = (2k+1 + 1)(2k + 1)n−1 .
2. Define the function


k(c−z) 2k + 1 n+z−c

2
n−1−z+c
F (z) = d − 2k(z−c+1) 2k + 1


d

if 0 ≤ z ≤ c
if c < z < n
if z = n

3. Sample U uniformly at random from {1, . . . , d}.

4. Using binary search find the smallest z ∈ [n] such that F (z) ≥ U .
5. Return z.

The function F is obtained by clearing denominators in the cumulative distribution function of
c + Geo(2/ε̃) clamped to [0, n].
Lemma 3.5. Let F (z) be defined as in Algorithm 3.4. Then for z ∈ [n], F (z) ∈ [d] and F (z)/d
equals the cumulative distribution function of c + Geo(2/ε̃) clamped to [0, n].
We prove this lemma after seeing how it implies Proposition 3.3.
Proof of Proposition 3.3. Let U be drawn uniformly at random from {1, . . . , d}. By construction,
for all z ∈ [n]
Pr[GeoSample(k, n, c) ≤ z] = Pr[U ≤ F (z)] = F (z)/d
13

implying GeoSample(k, n, c) ∼ c + Geo(2/ε̃) by Lemma 3.5.
We now bound the running time. Binary search takes O(log n) rounds. The largest number
used is d with bit length O(nk) and all operations are polynomial in the bit length of these numbers.
Therefore, GeoSample(k, n, c) has running time poly(k, n).
Proof of Lemma 3.5. The cumulative distribution function


0



 eε̃/2 · e−(c−z)·ε̃/2
ε̃/2
FZ (z) = e +1 1
1 − ε̃/2 · e(c−z)·ε̃/2

e +1



1

of Z ∼ c + Geo(2/ε̃) is
if z < 0
if 0 ≤ z ≤ c
if c < z < n
if z ≥ n

Consider the case when 0 ≤ z ≤ c.
FZ (z) =

−(c−z)
1 + 2−k 
eε̃/2
−(c−z)ε̃/2
−k
·
e
=
·
1
+
2
2 + 2−k
eε̃/2 + 1
 k c−z
2k + 1
2
= k+1
·
2
+1
2k + 1
2k(c−z)

=

c−z−1

(2k+1 + 1) (2k + 1)
n+z−c
2k(c−z) 2k + 1
=
d
F (z)
=
d

·



2k + 1
2k + 1

n−(c−z)

A similar argument holds when c < z < n and FZ (n) = 1 = F (n)/d. So FZ (z) = F (z)/d for all
z ∈ [n].
Using this algorithm we are ready to construct a private histogram algorithm with bounded
time complexity whose accuracy is identical to that of GeometricMechanism up to constant factors.
Algorithm 3.6. BoundedGeometricMechanism(D, ε) for D ∈ X n and rational ε ∈ (0, 1]
1. Let k = ⌈log(2/ε)⌉.
2. For each x ∈ X , do the following:
(a) Let c̃x = GeoSample(k, n, cx (D)).
(b) Release (x, c̃x ).

Theorem 3.7. Let rational ε ∈ (0, 1] and ε̃ = 2 · ln 1 + 2−⌈log(2/ε)⌉ ∈ (4/9 · ε, ε]. Then
BoundedGeometricMechanism(D, ε) has the following properties:
i. BoundedGeometricMechanism(D, ε) is (ε, 0)-differentially private.
ii. BoundedGeometricMechanism(D, ε) has (a, β)-per-query accuracy for

 

1
2 1
9
ln
ln
a=
≤
ε̃ β
2ε β
14

iii. BoundedGeometricMechanism(D, ε) has (a, β)-simultaneous accuracy for
 


|X |
9
2 |X |
ln
ln
≤
a=
ε̃
β
2ε
β
iv. BoundedGeometricMechanism(D, ε) has running time
|X | · poly(N )
where N is the bit length of the algorithm’s input (D ∈ X n and ε).
Proof of i-iii. By Proposition 3.3, GeoSample(k, n, cx(D)) generates a two-sided geometric random
variable with scale parameter 2/ε̃ centered at cx (D) clamped to [0, n]. So this algorithm is identically distributed to GeometricMechanism(D, ε̃). As ε̃ ∈ (4/9 · ε, ε], parts i-iii follows from Theorem
3.2.
Proof of iv. For each x ∈ X , computing cx (D) takes time O(n log |X |) and by Proposition 3.3
GeoSample(k, n, cx (D)) takes times poly(n, log(1/ε)) as k = O(log(1/ε)).

4

Improving the Running Time

For datasets over large domains X , the linear in |X | running time of Algorithm 3.6 can be prohibitive. We present an algorithm that reduces the running time’s dependence on the universe
size from nearly linear to poly-logarithmic based on the observation that most counts are 0 when
n ≪ |X |; this is the same observation made by Cormode, Procopiuc, Srivastava and Tran [CPST11]
to output sparse histograms.

4.1

Sparse Histograms

We start by reducing the output length of GeometricMechanism to release only the bins with the
heaviest (or largest) counts (interpreted as a partial vector).
Algorithm 4.1. KeepHeavy(D, ε) for D ∈ X n and ε > 0
1. For each x ∈ X , set c̃x to cx (D) + Geo(2/ε) clamped to [0, n].
2. Let x1 , . . . , xn+1 be the elements of X with the largest counts in sorted order, i.e.
c̃x1 ≥ c̃x2 ≥ . . . ≥ c̃xn+1 ≥

max

x∈X \{x1 ,...,xn+1 }

c̃x

3. Release h = {(x, c̃x ) : c̃x > c̃xn+1 } ∈ Hn,n (X ).

Observe that the output length has been improved to O(n · (log n + log |X |)) bits compared to
the O(|X | · log n) bits needed to represent the outputs of GeometricMechanism.
Theorem 4.2. KeepHeavy(D, ε) has the following properties:
i. KeepHeavy(D, ε) is (ε, 0)-differentially private.
15

ii. KeepHeavy(D, ε) has (a, β)-per-query accuracy on counts larger than t for




2 2
2 2|X |
ln
ln
and a =
t=2
ε
β
ε β
iii. KeepHeavy(D, ε) has (a, β)-simultaneous accuracy for


2 |X |
a=2
ln
ε
β
Note that, unlike GeometricMechanism, this algorithm only has (O(log(1/β)/ε), β)-per-query
accuracy on counts larger than t = O(log(|X |/β)/ε). This loss is necessary for any algorithm that
outputs a sparse histogram as we will show in Theorem 6.2.
Proof of i. Privacy follows from the (ε, 0)-differential privacy of GeometricMechanism (part i of
Theorem 3.2) along with differential privacy’s closure under post-processing (Lemma 2.2).
To prove the remaining parts, we start with the following lemma.
l
m
|
Lemma 4.3. For any β ′ ∈ (0, 1), let t′ = 2 2ε ln |X
and define the event
β′
Et′ = {∀x ∈ X |c̃x − cx (D)| ≤ t′ /2}

Pr[Et′ ] ≥ 1 − β ′ and Et′ implies that for all x ∈ X such that cx (D) > t′ we have c̃x > c̃xn+1 .
Proof. The probability of Et′ occurring follows from part iii of Theorem 3.2 as the {c̃x }x∈X are
identically distributed to the output of GeometricMechanism(D, ε).
Assume the event Et′ . Then for all x ∈ X such that cx (D) > t′ , we have c̃x > t′ /2 and for all
x ∈ X such that cx (D) = 0, we have c̃x ≤ t′ /2. Because there are at most n distinct elements in
D, we have c̃x > c̃xn+1 for all x ∈ X such that cx (D) > t′ .
Proof of part ii of Theorem 4.2. Let x ∈ X such that cx (D) > t. We have

Pr (|hx − cx (D)| > a) ≤ Pr c̃x ≤ c̃xn+1 + Pr (|c̃x − cx (D)| > a)
≤ β/2 + β/2

by Lemma 4.3 with β ′ = β/2 and t′ = t, and part ii of Theorem 3.2.
Proof of part iii of Theorem 4.2. Let t = 2 ⌈(2/ε) · ln(|X |/β)⌉. The event Et in Lemma 4.3 occurs
with probability at least 1 − β. Assume Et . By Lemma 4.3, for all x ∈ X such that cx (D) > t
we have c̃x > c̃xn+1 . This implies |hx − cx (D)| ≤ t/2. For the remaining x ∈ X we trivially have
|hx − cx (D)| ≤ t as hx = 0.
However, as described KeepHeavy still requires adding noise to the count of every bin. The
following algorithm M1 : X n × (0, 1] → Hn,n (X ) simulates KeepHeavy by generating a candidate
set of heavy bins from which only the heaviest are released. This candidate set is constructed from
all bins with nonzero true count and a sample representing the bins with a true count of 0 that
have the heaviest noisy counts.

16

Algorithm 4.4. M1 (D, ε) for D ∈ X n , ε > 0 and |X | ≥ 2n + 1

1

1. Let A = {x ∈ X : cx (D) > 0} and w = |X \ A|.
2. For each x ∈ A, set c̃x to cx (D) + Geo(2/ε) clamped to [0, n].
3. Pick a uniformly random sequence (q0 , . . . , qn ) of distinct elements from X \ A.
4. Sample (c̃q0 , . . . , c̃qn ) from the joint distribution of the order statistics (Z(w) , . . . , Z(w−n) ) where
Z1 , . . . , Zw are i.i.d. and distributed as Geo(2/ε) clamped to [0, n].
5. Sort the elements of A ∪ {q0 , . . . , qn } as x1 , . . . , x|A|+n+1 such that c̃x1 ≥ . . . ≥ c̃x|A|+n+1 .
6. Release h = {(x, c̃x ) : x ∈ {x1 , . . . , xn } and c̃x > c̃xn+1 } ∈ Hn,n (X ).2

Proposition 4.5. M1 (D, ε) is identically distributed to KeepHeavy(D, ε).
Proof. Let {ĉx }x∈X be the noisy counts set by KeepHeavy(D, ε) and let x̂1 , . . . , x̂n+1 be the sorted
ordering defined by these counts. We have c̃x ∼ ĉx for all x ∈ A and the Zi ’s are identically
distributed to {ĉx }x∈X \A .
{(qi , c̃qi )}ni=0 is identically distributed to the n + 1 bins with heaviest counts of {(x, ĉx )}x∈X \A .
Let the random variable B be the set of the labels of the n + 1 bins with heaviest counts of
{(x, ĉx )}x∈X \A . Therefore,
h = {(x, c̃x ) : x ∈ {x1 , . . . , xn } and c̃x > c̃xn+1 }
= {(x, c̃x ) : x ∈ A ∪ {q0 , . . . , qn } and c̃x ≥ c̃xn+1 }
∼ {(x, ĉx ) : x ∈ A ∪ B and ĉx ≥ ĉx̂n+1 }
= {(x, ĉx ) : x ∈ X and ĉx ≥ ĉx̂n+1 }
which shows that M1 (D, ε) is identically distributed to KeepHeavy(D, ε).
In order to sample from the order statistics used by M1 we construct the following algorithm
similar to GeoSample (Algorithm 3.4) from the previous section.
Proposition 4.6. Let k ∈ N and n, w ∈ N+ . Let v ∈ [n] and i ∈ {1, . . . , w}. Define the i.i.d.
random variables Z1 , . . . , Zw with each identically distributed to Geo(2/ε̃) clamped to [0, n] where
ε̃ = 2 · ln(1 + 2−k ). The following subroutine OrdSample(k, n, v, i) is identically distributed to the
i-th order statistic Z(i) conditioned on Z(i+1) = v. Also, OrdSample(k, n, v, i) has running time
poly(n, k, i).
1

|X | ≥ 2n + 1 ensures that |X \ A| ≥ n + 1. One can use GeometricMechanism(D, ε) when |X | ≤ 2n.
If instead we used continuous noise this last step is equivalent to releasing the n heaviest bins. However, in the
discrete case, where ties can occur, from the set A ∪ {x1 , . . . , xn } we cannot determine all bins with a count tied for
the n-th heaviest as there may be many other noisy counts tied with c̃xn . As a result, we only output the bins with
a strictly heavier count than c̃xn+1 .
2

17

As in BoundedGeometricMechanism (Algorithm 3.6), we have chosen ε̃ so that the cumulative
distribution function of Geo(2/ε̃) takes rational values with a common denominator of d. Therefore,
the cumulative distribution function of Z(i) conditioned on Z(i+1) = v is also rational and we can
sample from it with finite precision.
Algorithm 4.7. OrdSample(k, n, v, i) for k ∈ N; n, i ∈ N+ and v ∈ [n]
1. Let d = (2k+1 + 1)(2k + 1)n−1 .
2. Define the function
(
n−1−z
d − 2k(z+1) 2k + 1
F (z) =
d

if 0 ≤ z < n
if z = n

3. Sample U uniformly at random from {1, . . . , F (v)i }.
4. Using binary search find the smallest z ∈ [v] such that F (z)i ≥ U .
5. Return z.

Proof. By Lemma 3.5, F (z)/d is the cumulative distribution of Geo(2/ε̃) clamped to [0, n]. Therefore, by Lemma 2.13,
FZ(i) |Z(i+1) =v (z) =



F (z)/d
F (v)/d

i

=



F (z)
F (v)

i

for z ∈ [v]. Let U be drawn uniformly at random from {1, . . . , F (v)i }. Then, by construction,
i

Pr[OrdSample(k, n, v, i) ≤ z] = Pr[U ≤ F (z) ] =



F (z)
F (v)

i

implying OrdSample(k, n, v, i) ∼ Z(i) | Z(i+1) = v.
The binary search takes O(log n) iterations. Each iteration has running time polynomial in
the bit length of the numbers used. Therefore, this algorithm has running time poly(log d, i) =
poly(n, k, i).
Now from M1 we replace sampling from the joint distribution of the order statistics with
iterative calls to OrdSample to get the following algorithm.

18

Algorithm 4.8. M2 (D, ε) for D ∈ X n , rational ε ∈ (0, 1] and |X | ≥ 2n + 1
1. Let k = ⌈log(2/ε)⌉.
2. Let A = {x ∈ X : cx (D) > 0} and w = |X \ A|.
3. For each x ∈ A, let c̃x = GeoSample(k, n, cx (D)).
4. Pick a uniformly random sequence (q0 , . . . , qn ) of distinct elements from X \ A.
5. Let c̃q0 = OrdSample(k, n, n, w).
6. For each i ∈ {1, . . . , n}, let c̃qi = OrdSample(k, n, c̃qi−1 , w − i).
7. Sort the elements of A ∪ {q0 , . . . , qn } as x1 , . . . , x|A|+n+1 such that c̃x1 ≥ . . . ≥ c̃x|A|+n+1 .
8. Release h = {(x, c̃x ) : x ∈ {x1 , . . . , xn } and c̃x > c̃xn+1 } ∈ Hn,n (X ).
Theorem 4.9. Let rational ε ∈ (0, 1] and ε̃ = 2 · ln(1 + 2−⌈log(2/ε)⌉ ) ∈ (4/9 · ε, ε]. M2 (D, ε) is
identically distributed to KeepHeavy(D, ε̃). Therefore,
i. M2 (D, ε) is (ε, 0)-differentially private.
ii. M2 (D, ε) has (a, β)-per-query accuracy on counts larger than t for




2 2
2 2|X |
ln
ln
and a =
t=2
ε̃
β
ε̃ β
iii. M2 (D, ε) has (a, β)-simultaneous accuracy for


2 |X |
ln
a=2
ε̃
β
Proof. By Proposition 4.6, we have (c̃q0 , . . . , c̃qn ) is identically distributed to the joint distribution
(Z(w) , . . . , Z(w−n) ) used by M1 . Therefore, this algorithm is identically distributed to M1 (D, ε̃)
and, then by Proposition 4.5, identically distributed to KeepHeavy(D, ε̃). Parts i to iii follow from
Theorem 4.2.
This algorithm only has an output of length O(n · (log n + log |X |)). However, its running time
depends polynomially on |X | since sampling the wth order statistic, c̃q0 , using OrdSample takes time
polynomial in w ≥ |X | − n. Indeed, this is necessary since the distribution of the order statistic
Z(w) has probabilities that are exponentially small in w. 3

4.2

An Efficient Approximation

To remedy the inefficiency of M2 we consider an efficient algorithm that approximates the output
distribution of M2 .
3

Notice Pr[Z(w) = 0] = Pr[Z = 0]w where Z ∼ Geo(2/ε̃). And Pr[Z = 0]w =
coins to sample from this distribution.

19



eε̃/2 −1
eε̃/2 +1

w

. So we need to toss Ω(w)

Theorem 4.10. There exists an algorithm NonzeroGeometric : X n × (0, 1] × (0, 1) → Hn,n (X )
such that for all input datasets D ∈ X n , rational ε ∈ (0, 1] and δ ∈ (0, 1) such that 1/δ ∈ N
i. ∆ (M2 (D, ε), NonzeroGeometric(D, ε, δ)) ≤ δ.
ii. NonzeroGeometric(D, ε, δ) is (ε, (eε + 1) · δ)-differentially private.
iii. Moreover, the running time of NonzeroGeometric(D, ε, δ) is
poly(N )
where N is the bit length of this algorithm’s input (D, ε and δ).
Note that this algorithm only achieves (ε, δ)-differential privacy. By reducing δ, the algorithm
better approximates M2 , improving accuracy, at the cost of increasing running time (polynomial
in log(1/δ)). This is in contrast to most (ε, δ)-differentially private algorithms such as the stability
based algorithm of Section 5, where one needs n ≥ Ω(log(1/δ)/ε) to get any meaningful accuracy.
Now, we convert NonzeroGeometric to a pure differentially private algorithm by mixing it with
a uniformly random output inspired by a similar technique in [KLN+ 11, CDK17].
Algorithm 4.11. M∗ (D, γ) for D ∈ X n and rational γ ∈ (0, 1)
1. With probability 1 − γ release M′ (D).
2. Otherwise release a uniformly random element of R.
Lemma 4.12. Let M : X n → R be (ε, 0)-differentially private with discrete range R. Suppose
algorithm M′ : X n → R satisfies ∆ (M(D), M′ (D)) ≤ δ for all input datasets D ∈ X n with
parameter δ ∈ [0, 1). Then the algorithm M∗ has the following properties:
i. M∗ (D, γ) is (ε, 0)-differentially private whenever
δ≤

eε − 1
γ
1
·
·
eε + 1 1 − γ |R|

ii. M∗ (D, γ) has running time upper bounded by the sum of the bit length to represent γ, the
running time of M′ (D) and the time required to sample a uniformly random element of R.
By taking γ and δ small enough and satisfying the constraint in part i, the algorithm M∗
satisfies pure differential privacy and has nearly the same utility as M (due to having a statistical
distance at most γ + δ from M) while allowing for a possibly more efficient implementation since
we only need to approximately sample from the output distribution of M.
Proof of i. For all neighboring datasets D, D ′ ∈ X n and all r ∈ R
1
|R|
1
≤γ·
|R|
1
≤γ·
|R|
1
≤γ·
|R|

Pr[M∗ (D, γ) = r] = γ ·

+ (1 − γ) · Pr[M′ (D) = r]
+ (1 − γ) · (Pr[M(D) = r] + δ)
+ (1 − γ) eε · Pr[M(D ′ ) = r] + δ





+ (1 − γ) eε · Pr[M′ (D ′ ) = r] + δ + δ
20

Rearranging terms and using the upper bound on δ yields
1
+ (eε + 1) (1 − γ) · δ
|R|


1
1
ε
′
′
ε
≤ e (1 − γ) · Pr[M (D ) = r] + γ ·
+ (e − 1) γ ·
|R|
|R|


1
= eε (1 − γ) · Pr[M′ (D ′ ) = r] + γ ·
|R|
ε
∗
′
= e · Pr[M (D , γ) = r]

Pr[M∗ (D, γ) = r] = eε (1 − γ) · Pr[M′ (D ′ ) = r] + γ ·

Proof of ii. This follows directly from the construction of M∗ .
We can apply this lemma to NonzeroGeometric and under reasonable settings of parameters
get accuracy bounds identical to M2 up to constant factors.
Algorithm 4.13. PureNonzeroGeometric(D, ε, β) for D ∈ X n , rational ε ∈ (0, 1] and 1/β ∈ N
1. With probability 1 − β/3 release NonzeroGeometric(D, ε, δ) with
δ=

2−⌈log(1/ε)⌉ β
1
· ·
3
3 |Hn,n (X )|

2. Otherwise release a uniformly random element of Hn,n (X ).

Theorem 4.14. Let rational ε ∈ (0, 1], ε̃ = 2 · ln 1 + 2−⌈log(2/ε)⌉ ∈ (4/9 · ε, ε] and 1/β ∈ N.
PureNonzeroGeometric(D, ε, β) has the following properties:
i. PureNonzeroGeometric(D, ε, β) is (ε, 0)-differentially private.
ii. PureNonzeroGeometric(D, ε, β) has (a, β)-per-query accuracy on counts larger than t for




2 6
2 6|X |
ln
ln
and a =
t=2
ε̃
β
ε̃ β
iii. PureNonzeroGeometric(D, ε, β) has (a, β)-simultaneous accuracy for


2 3|X |
a=2
ln
ε̃
β
iv. PureNonzeroGeometric(D, ε, β) has running time
poly(N )
where N is the bit length of this algorithm’s input (D ∈ X n , ε and β).
Proof of i. Notice that 1/δ ∈ N (a constraint needed for NonzeroGeometric). Privacy follows from
Lemma 4.12 by taking M = M2 , M′ = NonzeroGeometric, γ = β/3 and R = Hn,n (X ) as
δ=

1
eε − 1
β/3
1
2−⌈log(1/ε)⌉ β
· ·
≤ ε
·
·
3
3 |Hn,n (X )|
e + 1 1 − β/3 |Hn,n (X )|
21

Proof of ii-iii. For any D ∈ X n and x ∈ X such that cx (D) > t define the set G = {h ∈ Hn,n (X ) :
|hx − cx (D)| ≤ a}. By construction,
Pr[PureNonzeroGeometric(D, ε, β) ∈ G] ≥ Pr[NonzeroGeometric(D, ε, δ) ∈ G] − β/3
where δ is defined in Algorithm 4.13. Notice that δ ≤ β/3. So by Theorem 4.10,
Pr[NonzeroGeometric(D, ε, δ) ∈ G] − β/3 ≥ Pr[M2 (D, ε) ∈ G] − 2 · β/3
And by part ii of Theorem 4.9, we have
Pr[M2 (D, ε) ∈ G] − 2 · β/3 ≥ 1 − β
Similarly, we can bound the simultaneous accuracy by using part iii of Theorem 4.9.
Proof of iv. By Lemma A1.1, it takes poly(n, log |X |) time to sample a uniformly random element
of Hn,n (X ) and compute |Hn,n (X )|. And by Theorem 4.10, NonzeroGeometric(D, ε, δ) with
δ=

2−⌈log(1/ε)⌉ β
1
· ·
3
3 |Hn,n (X )|

has running time poly(N ). So by Lemma 4.12, PureNonzeroGeometric has the desired running
time.

4.3

Construction of NonzeroGeometric

We finish this section with the construction of NonzeroGeometric. Notice that M2 passes arguments to OrdSample that result in OrdSample exponentiating an integer, which represents the
numerator of a fraction a/b = F (z)/F (v), to a power i ≥ |X | − n. We want to ensure that numbers
used by OrdSample do not exceed some maximum s.
The following algorithm will approximate s · (a/b)i by using repeated squaring and truncating
each intermediate result to keep the bit length manageable. The following lemma provides a bound
on the error and on the running time.
Proposition 4.15. There is an algorithm ExpApprox(a, b, i, s) such that for all b, i, s ∈ N+ and
a ∈ [b]:
i. ExpApprox(a, b, i, s) is a nondecreasing function in a and ExpApprox (a, b, i, s) = s when a = b.
ii. ExpApprox(a, b, i, s) satisfies the accuracy bound of
 
i
ExpApprox (a, b, i, s)  a i
≤2·
−
s
b
s
iii. ExpApprox(a, b, i, s) has running time poly(log b, log i, log s).
Proof. The algorithm is defined as follows.
Algorithm 4.16. ExpApprox(a, b, i, s) for b, i, s ∈ N+ and a ∈ [b]
 
1. If i = 1 return as
b .
(

r 2 /s

2. Otherwise let r = ExpApprox (a, b, ⌊i/2⌋, s) and return 
(a/b) · (r 2 /s)
22

if i is even
if i is odd

Proof of i. We proceed by induction. The case when i = 1 is trivial. Let i > 1 and assume that
ExpApprox(a, b, j, s) is a nondecreasing function in a for all j < i. Consider a ≤ a′ ≤ b. If i is odd,
then


a ExpApprox(a, b, ⌊i/2⌋, s)2
·
ExpApprox(a, b, i, s) =
b
s

 ′
a ExpApprox(a′ , b, ⌊i/2⌋, s)2
·
= ExpApprox(a′ , b, i, s)
≤
b
s
Likewise, the result holds when i is even. Therefore, ExpApprox(a, b, i, s) is a nondecreasing function
in a. It is trivial that ExpApprox (a, b, i, s) = s when a = b.
Proof of ii. For ease of notation define EA(i) = ExpApprox (a, b, i, s) as the other parameters do not
change in our analysis. By construction
EA (i) =
(
1
where mi =
a/b

mi · EA (⌊i/2⌋)2
+ ωi
s

if i is even
and |ωi | ≤ 1. We can now bound the error as
if i is odd

EA (i)  a i
EA (i) mi · EA (⌊i/2⌋)2
mi · EA (⌊i/2⌋)2  a i
≤
−
−
−
+
s
b
s
s2
s2
b
EA (⌊i/2⌋)  a ⌊i/2⌋
EA (⌊i/2⌋)  a ⌊i/2⌋
|ωi |
+ mi ·
+
·
−
≤
s
s
b
s
b


⌊i/2⌋
EA (⌊i/2⌋)
a
1
−
≤ +2·
s
s
b
When i = 1, we have
EA(1) a
=
−
s
b

as
b

+ ω1 a
1
≤
−
s
b
s

So solving the recurrence gives
 
i
EA (i)  a i
≤2·
−
s
b
s
Proof of iii. The running time follows from the observation that a call to ExpApprox (a, b, i, s) makes
at most O(log i) recursive calls with the remaining operations polynomial in the bit lengths of the
numbers used.
Now we can modify OrdSample using ExpApprox to keep the bit lengths of its numbers from
becoming too large, yielding an efficient algorithm whose output distribution is close to that of
OrdSample.

23

Algorithm 4.17. ApproxOrdSample(k, n, v, i, s) for k, n, i, s ∈ N+ and v ∈ [n]
1. Let d = (2k+1 + 1)(2k + 1)n−1 .
2. Define the function
(
n−1−z
d − 2k(z+1) 2k + 1
F (z) =
d

if 0 ≤ z < n
if z = n

3. Sample U uniformly from {1, . . . , s}.
4. Using binary search find the smallest z ∈ [v] such that
ExpApprox (F (z), F (v), i, s) ≥ U
5. Return z.

Proposition 4.18. Let k, n, i, s ∈ N+ and v ∈ [n]. Then
 
i
∆(OrdSample(k, n, v, i), ApproxOrdSample(k, n, v, i, s)) ≤ 2 · (n + 1) ·
s
In addition, ApproxOrdSample(k, n, v, i, s) has a running time of poly(k, n, log i, log s).
Proof. Let Y ∼ OrdSample(k, n, v, i) and Ye ∼ ApproxOrdSample(k, n, v, i, s). Let z ∈ [v]. Then
Pr[Y = z] =



F (z)
F (v)

i

−



F (z − 1)
F (v)

i

where we define F (−1) = 0. By part i of Proposition 4.15, ExpApprox(F (z), F (v), i, s) is an
increasing function in z. Therefore,
Pr[Ye = z] =

ExpApprox(F (z), F (v), i, s) ExpApprox(F (z − 1), F (v), i, s)
−
s
s

Therefore, by the triangle inequality and part ii of Proposition 4.15
| Pr[Y = z] − Pr[Ye = z]| ≤

z
X

z ′ =z−1

ExpApprox(F (z ′ ), F (v), i, s)
−
s



F (z ′ )
F (v)

i

 
i
≤4·
s

Summing over z ∈ [v] yields the desired bound on total variation distance (Definition 2.9).
The running time is dominated by the O(log n) calls to ExpApprox(F (z), F (v), i, s). By part iii
of Proposition 4.15, each call takes time
poly(log F (v), log i, log s) = poly(k, n, log i, log s)
as log F (v) ≤ log d = O(nk). So overall ApproxOrdSample has the desired running time.
Because M2 samples from a joint distribution obtained by iterated calls to OrdSample we must
also consider the accumulated distance between iterated calls to OrdSample and iterated calls to
ApproxOrdSample.
24

Corollary 4.19. Let k, n, w, s ∈ N+ with w > n. Consider the following random variables:
• Y0 ∼ OrdSample(k, n, n, w)
• Yj ∼ OrdSample(k, n, Yj−1 , w − j) for each j ∈ {1, . . . , n}
• Ye0 ∼ ApproxOrdSample(k, n, n, w, s)

• Yej ∼ ApproxOrdSample(k, n, Yej−1 , w − j, s) for each j ∈ {1, . . . , n}

Then

w 

∆ (Y0 , . . . , Yn ), (Ye0 , . . . , Yen ) ≤ 2 · (n + 1)2 ·
s

Proof. By part iii of Lemma 2.10 and Proposition 4.18,

n
w 

 X

e
e
e
∆ Yj |Yj−1 , Yej |Yej−1 ≤ 2 · (n + 1)2 ·
∆ (Y0 , . . . , Yn ), (Y0 , . . . , Yn ) ≤ ∆ Y0 , Y0 +
s
j=1

where


∆ Yj |Yj−1 , Yej |Yej−1 =

max

x∈[n],S⊆[n]

n

Pr[Yj ∈ S|Yj−1 = x] − Pr[Yej ∈ S|Yej−1 = x]}

o

We are ready to state the mechanism NonzeroGeometric and show it satisfies Theorem 4.10.
It is identical to M2 except we replace calls to OrdSample with calls to ApproxOrdSample.
Algorithm 4.20. NonzeroGeometric(D, ε, δ) for D ∈ X n , rational ε ∈ (0, 1], 1/δ ∈ N and
|X | ≥ 2n + 1
1. Let k = ⌈log(2/ε)⌉ and s = 2 · (n + 1)2 · |X |/δ.
2. Let A = {x ∈ X : cx (D) > 0} and let w = |X \ A|.
3. For each x ∈ A, let c̃x = GeoSample(k, n, cx (D)).
4. Pick a uniformly random sequence (q0 , . . . , qn ) of distinct elements from X \ A.
5. Let c̃q0 = ApproxOrdSample(k, n, n, w, s).
6. For each i ∈ {1, . . . , n}, let c̃qi = ApproxOrdSample(k, n, c̃qi−1 , w − i, s).
7. Sort the elements of A ∪ {q0 , . . . , qn } as x1 , . . . , x|A|+n+1 such that c̃x1 ≥ . . . ≥ c̃x|A|+n+1 .
8. Release h = {(x, c̃x ) : x ∈ {x1 , . . . , xn } and c̃x > c̃xn+1 } ∈ Hn,n (X ).

Theorem 4.10 (restated). The algorithm NonzeroGeometric(D, ε, δ) satisfies for all input datasets
D ∈ X n , rational ε ∈ (0, 1] and δ ∈ (0, 1) such that 1/δ ∈ N
i. ∆ (M2 (D, ε), NonzeroGeometric(D, ε, δ)) ≤ δ.
ii. NonzeroGeometric(D, ε, δ) is (ε, (eε + 1) · δ)-differentially private.
25

iii. Moreover, the running time of NonzeroGeometric(D, ε, δ) is
poly(N )
where N is the bit length of this algorithm’s input (D, ε and δ).
Proof of i. Let M∗2 : X n × (0, 1] → Hn,2n+1 (X ) be the algorithm M2 except, instead of releasing
the heaviest bins, M∗2 releases the bins for all elements of A ∪ {x0 , . . . , xn } (i.e. M∗2 releases (y, c̃y )
for all y ∈ A and (xi , c̃xi ) for all i ∈ [n]). Similarly, we define NonzeroGeometric∗ with respect to
NonzeroGeometric.
Notice that M∗2 and NonzeroGeometric∗ have the same distribution overs the bins with nonzero
true count. Only on the bins with counts sampled using OrdSample and ApproxOrdSample respectively do their output distributions differ. As a result, we can apply Corollary 4.19 to the output
distributions of M∗2 and NonzeroGeometric∗ . So for all D ∈ X n
w
∆ (M∗2 (D, ε), NonzeroGeometric∗ (D, ε, δ)) ≤ 2 · (n + 1)2 ·
≤δ
s

Now we consider the effect of keeping the heaviest counts. Define T : Hn,2n+1 → Hn,n (X ) to be
the function that sets counts not strictly larger than the (n + 1)-heaviest count of its input to 0.
Notice that T ◦ M∗2 ∼ M2 and T ◦ NonzeroGeometric∗ ∼ NonzeroGeometric. So for all D ∈ X n ,
by part ii of Lemma 2.10,
∆(M2 (D, ε), NonzeroGeometric(D, ε, δ)) = ∆(T (M∗2 (D, ε)), T (NonzeroGeometric∗ (D, ε, δ)))
≤ ∆(M∗2 (D, ε), NonzeroGeometric∗ (D, ε, δ))
≤δ

Proof of ii. Let D and D ′ be neighboring datasets. Let S ⊆ Hn,n (X ). By the previous part and
part i of Theorem 4.9,
Pr[NonzeroGeometric(D, ε, δ) ∈ S] ≤ Pr[M2 (D, ε) ∈ S] + δ
≤ eε · Pr[M2 (D ′ , ε) ∈ S] + δ


≤ eε · Pr[NonzeroGeometric(D ′ , ε, δ) ∈ S] + δ + δ

Therefore, NonzeroGeometric(D, ε, δ) is (ε, (eε + 1) · δ)-differentially private.

Proof of iii. We consider the running time at each step. Construction of the true histogram takes
O(n log |X |) time. And by Proposition 3.3, the at most n calls to GeoSample take poly(log(1/ε), n)
time. Sampling n random bin labels from X takes O(n log |X |) time.
Now, NonzeroGeometric makes n + 1 calls to ApproxOrdSample with no argument exceeding
each term of (k, n, n, |X |, s) respectively. So by Proposition 4.18, these calls take time
poly(log(1/ε), n, log |X |, log s) ≤ poly(log(1/ε), n, log |X |, log(1/δ))
Sorting the at most 2n + 1 elements of A ∪ {q0 , . . . , qn } and then releasing the heaviest counts
takes O(n log n + n log |X |) time.
Therefore, overall NonzeroGeometric has the desired running time.
We have constructed algorithms for releasing a differentially private histogram, both pure and
approximate, with running time polynomial in log |X | and simultaneous accuracy matching that of
GeometricMechanism up to constant factors.
26

5

Removing the Dependence on Universe Size

When we would like to have accuracy independent of |X |, we can use an approximate differentially private algorithm based on stability techniques [BNS16] (Proposition 2.20). We present a
reformulation of their algorithm using two-sided geometric noise instead of Laplace noise.
Algorithm 5.1. StabilityHistogram(D, ε, b) for D ∈ X n , ε > 0 and b ∈ [n]
1. Let A = {x ∈ X : cx (D) > 0}.
2. For each x ∈ A, set c̃x to cx (D) + Geo(2/ε) clamped to [0, n].
3. Release h = {(x, c̃x ) : x ∈ A and c̃x > b} ∈ Hn,n (X ).

Note that we only release counts for x ∈ X whose true count is nonzero, namely elements in
the set A. Thus, the output length is O(n · (log n + log |X |)). However, releasing the set A is not
(ε, 0)-differentially private because this would distinguish between neighboring datasets: one with
a count of 0 and the other with a count of 1 for some element x ∈ X . Thus, we only release noisy
counts c̃x that exceed a threshold b. If b is large enough, then a count of 1 will only be kept with
small probability, yielding approximate differential privacy.
Theorem 5.2. StabilityHistogram(D, ε, b) has the following properties:
i. StabilityHistogram(D, ε, b) is (ε, δ)-differentially private provided that
b≥1+

2 1
ln
ε δ

ii. StabilityHistogram(D, ε, b) has (a, β)-per-query accuracy on counts larger than t for




2 1
2 1
t=b+
ln
ln
and a =
ε β
ε β
iii. StabilityHistogram(D, ε, b) has (a, β)-simultaneous accuracy for


2 n
a=b+
ln
ε β
Proof of i. Let D and D ′ be neighboring datasets. Let x ∈ X such that cx (D) 6= cx (D ′ ) and
S ⊆ [n]. There are 3 cases to consider:
• cx (D) ≥ 1 and cx (D ′ ) ≥ 1. Then c̃x ∼ cx (D) + Geo(2/ε) and similarly on the neighboring
database we have a noisy count c̃′x ∼ cx (D ′ ) + Geo(2/ε). So by the differential privacy of
GeometricMechanism (part i of Theorem 3.2) we have
Pr[M(D)x ∈ S] ≤ eε/2 · Pr[M(D ′ )x ∈ S]

27

• cx (D) = 1 and cx (D ′ ) = 0. Notice Pr[M(D ′ )x 6= 0] = 0. c̃x is distributed as 1 + Geo(2/ε)
clamped to [0, n]. Thus,


2 1
Pr[M(D)x 6= 0] = Pr[c̃x > b] ≤ Pr c̃x > 1 + ln
ε δ


δ
2 1
δ
≤
≤ Pr Z > ln
= ε/2
ε δ
2
e +1
where Z ∼ Geo(2/ε). Therefore,
Pr[M(D)x ∈ S] ≤ Pr[M(D ′ )x ∈ S] + δ/2
• cx (D) = 0 and cx (D ′ ) = 1. This case follows similarly to the previous case by considering
Pr[M(D)x = 0].
Then overall
Pr[M(D)x ∈ S] ≤ eε/2 · Pr[M(D ′ )x ∈ S] + δ/2
Because there are at most two bins on which D and D ′ have differing counts and each count c̃x is
computed independently, by Lemma 2.4, this algorithm is (ε, δ)-differentially private.
Proof of ii. Let x ∈ X such that cx (D) > t. Then x ∈ A. So by part ii of Theorem 3.2, we have
Pr [|c̃x − cx (D)| ≤ a] ≥ 1 − β. |c̃x − cx (D)| ≤ a implies c̃x > t − a = b. Thus, (x, c̃x ) is included in
the output of StabilityHistogram(D, ε, b) giving the desired accuracy.
Proof of iii. Notice that the counts of elements not in A are trivially accurate. Therefore, we only
need to consider the counts of elements in A. By part iii of Theorem 3.2,



2 |A|
Pr ∀x ∈ A |c̃x − cx (D)| ≤
ln
≥1−β
ε
β
The final step can increase the error additively by at most b. Also, |A| ≤ n. Therefore,



2 n
ln
≥1−β
Pr ∀x ∈ X |hx − cx (D)| ≤ b +
ε β
By using GeoSample (see Proposition 3.3), we can construct a computationally efficient algorithm for releasing a histogram that is (ε, δ)-differentially private with the accuracies matching
Algorithm 5.1 up to constant factors.
Algorithm 5.3. BoundedStabilityHistogram(D, ε, b) for D ∈ X n , rational ε ∈ (0, 1] and b ∈ [n]
1. Let k = ⌈log(2/ε)⌉.
2. Let A = {x ∈ X : cx (D) > 0}.
3. For each x ∈ A, let c̃x = GeoSample(k, n, cx (D)).
4. Release h = {(x, c̃x ) : x ∈ A and c̃x > b} ∈ Hn,n (X ).

28


Theorem 5.4. Let rational ε ∈ (0, 1], ε̃ = 2 · ln 1 + 2−⌈log(2/ε)⌉ ∈ (4/9 · ε, ε] and b ∈ [n]. Then
BoundedStabilityHistogram(D, ε, b) satisfies the following properties:
i. BoundedStabilityHistogram(D, ε, b) is (ε, δ)-differentially private provided that
b ≥1+

2
ln(1/δ)
ε̃

ii. BoundedStabilityHistogram(D, ε, b) has (a, β)-per-query accuracy on counts larger than t
for




2 1
2 1
ln
ln
and a =
t=b+
ε̃ β
ε̃ β
iii. BoundedStabilityHistogram(D, ε, b) has (a, β)-simultaneous accuracy for


2 n
a=b+
ln
ε̃ β
iv. BoundedStabilityHistogram(D, ε, b) has running time
poly(N )
where N is the bit length of this algorithm’s input (D ∈ X n , ε and b).
Proof of i-iii. By Proposition 3.3, GeoSample(k, n, cx(D)) generates a two-sided geometric random
variable with scale parameter 2/ε̃ centered at cx (D) clamped to [0, n]. Therefore, this algorithm is
identically distributed to StabilityHistogram(D, ε̃, b). Parts i-iii follow from Theorem 5.2.
Proof of iv. Construction of the true histogram takes O(n log |X |) time. And by Proposition 3.3,
the at most n calls to GeoSample take poly(log(1/ε), n) time. Because the counts do not exceed n,
the final step takes poly(n, log |X |) time.
Therefore, we have constructed an efficient algorithm for releasing a sparse histogram with
approximate differential privacy.

6

Lower Bounds

In this section, we prove a lower bound on the per-query accuracy of histogram algorithms whose
outputs are restricted to H∞,n′ (X ) (i.e. sparse histograms) using a packing argument [HT10,
BBKN14]. First, for completeness we state and reprove existing lower bounds for per-query accuracy and simultaneous accuracy as well as generalize them to the case of δ > 0.
Theorem 6.1 (following [HT10, BBKN14]). Let M : X n → H∞,|X |(X ) be (ε, δ)-differentially
private and β ∈ (0, 1/2].
i. If M has (a, β)-per-query accuracy and δ/ε ≤ β, then

 

1
1
1
ln
− 1, n
a ≥ · min
2
ε
4β

29

ii. If M has (a, β)-simultaneous accuracy, then




ε
1
|X | − 1
1
1
− 1, n
log
− 1, log
a ≥ · min
2
ε
4β
ε
4δ
Proof of i. Assume a < n/2. Let x, x0 ∈ X such that x 6= x0 . Define the dataset D0 ∈ X n such
that all rows are x0 . And define the dataset D such that the first m = ⌊2a⌋ + 1 rows are x and the
remaining n − m rows are x0 . Notice that Pr[|M(D)x − cx (D)| > a] ≤ β by the (a, β)-per-query
accuracy of M. By Lemma 2.3 and the fact that cx (D) > 2a while cx (D ′ ) = 0,
Pr[M(D)x − cx (D)| > a] ≥ e−mε · Pr[M(D ′ )x − cx (D)| > a] − δ/ε
≥ e−mε · Pr[M(D ′ )x − cx (D ′ )| ≤ a] − δ/ε
≥ e−mε · (1 − β) − δ/ε
Therefore,
−(2a+1)·ε

e



1
δ
≤
· β+
≤ 4β
1−β
ǫ

Proof of ii. Assume a < n/2. Let x0 ∈ X . For each x ∈ X define the dataset D (x) ∈ X n such that
the first m = ⌊2a⌋ + 1 rows are x and the remaining n − m rows are x0 . For all x ∈ X , let
Gx = {h ∈ H∞,|X |(X ) : ∀x′ ∈ X |hx′ − cx′ (D (x) )| ≤ a}
By Lemma 2.3, for all x ∈ X
Pr[M(D (x0 ) ) ∈ Gx ] ≥ e−mε · Pr[M(D (x) ) ∈ Gx ] − δ/ε
≥ e−mε · (1 − β) − δ/ε
Notice that Pr[M(D (x0 ) ) ∈
/ Gx0 ] ≤ β and {Gx }x∈X is a collection of disjoint sets. Then
X
Pr[M(D (x0 ) ) ∈
/ Gx0 ] ≥
Pr[M(D (x0 ) ) ∈ Gx ]
x∈X :x6=x0


≥ (|X | − 1) · e−mε · (1 − β) − δ/ε

Therefore,
−(2a+1)·ε

e

1
·
≤
1−β



β
δ
+
|X | − 1 ε



which implies the desired lower bound.
We now state our lower bound over sparse histograms.
Theorem 6.2. Let M : X n → H∞,n′ (X ) be (ε, δ)-differentially private with (a, β)-per-query accuracy with β ∈ (0, 1/2] and δ/ε ≤ β. Then






1
|X |
ε
1
1
ln
ln
−
1,
−
1,
n
a ≥ · min
2
2ε
16βn′
2ε
16βδ

30

The histogram algorithms of Sections 4 and 5 achieve (O(log(1/β)/ε), β)-per-query accuracy on
large enough counts. However, on smaller counts we can only guarantee (a, β)-per-query accuracy
with a = O(log(|X |/β)/ε) and a = O(log(1/(βδ))/ε) (by taking threshold b = O(log(1/δ)/ε))
for algorithms from Sections 4 and 5 respectively. Theorem 6.2 shows these bounds are the best
possible when |X | ≥ poly(n′ ) and δ ≤ poly(1/ε).
Proof. Assume a < n/2. Let x0 ∈ X . For each x ∈ X define the dataset D (x) ∈ X n such that the
first m = ⌈2a⌉ rows are x and the remaining n − m rows are x0 . By definition of (a, β)-per-query
accuracy and the fact that cx (D (x) ) ≥ 2a, we have
h
i
h
i
Pr M(D (x) )x ≥ a ≥ Pr M(D (x) )x − cx (D (x) ) ≤ a ≥ 1 − β
Then, by Lemma 2.3 and that D (x) is at distance at most m from D (x0 ) , we have
h
i
Pr M(D (x0 ) )x ≥ a ≥ (1 − β)e−mε − δ/ε
Thus, by linearity of expectations
hn
oi

E
x ∈ X : M(D (x0 ) )x ≥ a
≥ |X | · (1 − β)e−mε − δ/ε

On the other hand, as M(D (x0 ) ) ∈ H∞,n′ (X ) we have
hn
oi
E
x ∈ X : M(D (x0 ) )x ≥ a
≤ n′
Therefore,

e−⌈2a⌉·ε ≤

1
·
1−β



n′
δ
+
|X | ε



which along with ⌈2a⌉ ≤ 2a + 1 implies the lower bound of




1
1
|X |
1 ε
a ≥ · min
− 1, n
ln
− 1, ln
2
ε
4n′
ε
4δ
Therefore, along with part i of Theorem 6.1, we have





 



1
1
|X |
1
1
1 ε
a ≥ · min max min
− 1 , ln
ln
− 1, ln
−1 , n
2
ε
4n′
ε
4δ
ε
4β

 


 



1
1
1
1
|X |
1
1 ε
≥ · min
− 1 + ln
· min
ln
− 1, ln
−1 , n
2
2
ε
4n′
ε
4δ
ε
4β






1
1
|X |
ε
1
≥ · min
ln
ln
−
1,
−
1,
n
2
2ε
16βn′
2ε
16βδ

7

Better Per-Query Accuracy via Compact, Non-Sparse Representations

In this section, we present a histogram algorithm whose running time is poly-logarithmic in |X |, but,
unlike Algorithm 4.13, is able to achieve (a, β)-per query accuracy with a = O(log(1/β)/ε). Our
histogram algorithm will output a histogram from a properly chosen family. This family necessarily
contains histograms that have many nonzero counts to avoid the lower bound of Theorem 6.2.
31

Lemma 7.1. Let k ∈ N, n ∈ N+ and Z ∼ GeoSample(k, n, 0). There exists a multiset of histograms
Gk,n (X ) satisfying:
i. Let h be drawn uniformly at random from Gk,n (X ). For all x ∈ X and c ∈ [n]
−k+1

e−(2/3)·2

−k+1

· Pr[Z = c] ≤ Pr[hx = c] ≤ e(1/3)·2

· Pr[Z = c]

ii. Let h be drawn uniformly at random from Gk,n (X ). For all x ∈ X and a ∈ [n]
Pr[hx ≤ a] ≥ Pr[Z ≤ a]
iii. Let h be drawn uniformly at random from Gk,n (X ). For all B ⊆ X such that |B| ≤ n + 1 and
c ∈ [n]B
Y
Pr[∀x ∈ B hx = cx ] =
Pr[hx = cx ]
x∈B

iv. For all h ∈ Gk,n , the histogram h can be represented by a string of length poly(k, n, log |X |)
and given this representation for all x ∈ X the count hx can be evaluated in time
poly (k, n, log |X |)
v. For all A ⊆ X such that |A| ≤ n and c ∈ [n]A sampling a histogram h uniformly at random
from {h′ ∈ Gk,n (X ) : ∀x ∈ A h′x = cx } can be done in time
poly (k, n, log |X |)
Parts i and ii state when a histogram is sampled uniformly at random from Gn,k (X ) the marginal
distribution on each count is closely distributed to a two-sided geometric distribution centered at
0 clamped to [0, n].
Proof. (Construction) Let d = (2k+1 + 1)(2k + 1)n−1 . We would like to construct a (n + 1)-wise
independent hash family consisting of functions p : X → {1, . . . , d}, i.e. for all x ∈ X , p(x) is
uniformly distributed over {1, . . . , d} and for all distinct x1 , . . . , xn+1 ∈ X , the random variables
p(x1 ), . . . , p(xn+1 ) are independent.
Given any function p in this family we can construct a histogram by using p(x) as the randomness
for evaluating the noisy count of x via inverse transform sampling in a similar manner to Algorithm
3.4 as the marginal distribution of p(x) is uniformly distributed over {1, . . . , d}.
The set of all degree at most n polynomial over a finite field Fq is a (n + 1)-wise independent
hash family. Ideally, we would have |X | ≤ d and take q = d. In this case, we can map X to a subset
of Fq and use a bijection between {1, . . . d} and Fq to get the desired family of functions.
However, |X | may be larger than d and d is not a prime power. Therefore, we must pick a large
enough field Fq so that |X | ≤ q and that when mapping Fq to {1, . . . , d}, the resulting marginal
distributions are approximately uniform. So let
n
l
mo
m = max ⌈log |X |⌉ , log(3 · 2k−1 · d)
′ (X ) as the family of polynomials over the finite field F m with degree at most n. We
and define Gk,n
2
′ (X ) by taking
construct a histogram h ∈ Gk,n (X ) for each polynomial ph ∈ Gk,n

hx = min z ∈ [n] : F (z) ≥ (T (ph (T −1 (x))) mod d) + 1

32

for all x ∈ X where T : F2m → [2m − 1] is a bijection such that T and T −1 have running time
poly(m) and

if z < 0

0
n−1−z
k(z+1)
k
F (z) = d − 2
2 +1
if 0 ≤ z < n


d
if z = n

as defined in Algorithm 3.4 for c = 0. Notice that if h is drawn uniformly at random from Gk,n (X ),
′ (X ).
then ph is drawn uniformly at random from Gk,n
Proof of i. Let Z ∼ GeoSample(k, n, 0). For all x ∈ X and v ∈ [n], we have

Pr[hx = v] = Pr[min z ∈ [n] : F (z) ≥ (T (ph (T −1 (x))) mod d) + 1 = v]
= Pr[F (v − 1) < (T (ph (T −1 (x))) mod d) + 1 ≤ F (v)]
1
= m · |{y ∈ F2m : F (v − 1) < (T (y) mod d) + 1 ≤ F (v)}|
2

 m
2
1
+ 1 (F (v) − F (v − 1))
≤ m·
2
d


d
= 1 + m · Pr[Z = v]
2

(by Lemma 3.5)

m

≤ ed/2 · Pr[Z = v]

Similarly, because d/2m ≤ 2/3
 m

2
1
− 1 (F (v) − F (v − 1))
Pr[hx = v] ≥ m ·
2
d


d
≥ 1 − m · Pr[Z = v]
2
m

≥ e−2·d/2 · Pr[Z = v]

Now, part i follows as d/2m ≤ (1/3) · 2−k+1 by choice of m.
Proof of ii. Pick q ∈ N and r ∈ [d − 1] such that 2m = q · d + r. We proceed by splitting the
probability of Pr[hx ≤ a] based on whether or not the integer value of its randomness lies within
one of the q intervals of length d. Let U be drawn uniformly at random from [2m ], D be drawn
uniformly at random from {1, . . . , d} and Z ∼ GeoSample(k, n, 0). For all x ∈ X and a ∈ [n]

Pr[hx ≤ a] = Pr[min z ∈ [n] : F (z) ≥ (T (ph (T −1 (x))) mod d) + 1 ≤ a]
= Pr[(T (ph (T −1 (x))) mod d) + 1 ≤ F (a)]

= Pr[(U mod d) + 1 ≤ F (a)]
q·d
r
= m · Pr[D ≤ F (a)] + m · Pr[D ≤ F (a) | D ≤ r]
2
2
q·d
r
≥ m · Pr[D ≤ F (a)] + m · Pr[D ≤ F (a)]
2
2
= Pr[Z ≤ a]

33

(by monotonicity of F )

′ (X ) is a (n + 1)-wise independent hash family, for all B ⊆ X such that
Proof of iii. Because Gk,n
|B| ≤ n + 1 and c ∈ [n]B


Pr[∀x ∈ B hx = cx ] = Pr ∀x ∈ B F (cx − 1) < (T (ph (T −1 (x))) mod d) + 1 ≤ F (cx )
Y


=
Pr F (cx − 1) < (T (ph (T −1 (x))) mod d) + 1 ≤ F (cx )
x∈B

=

Y

Pr[hx = vx ]

x∈B

Proof of iv. F2m can be represented by an irreducible polynomial of degree m over F2 encoded as
a binary string of length m. Likewise, all elements of F2m can be represented by a polynomial
of degree at most m − 1 over F2 (requires m bits). This encoding defines an efficient bijection T
between F2m and [2m − 1] by also interpreting the string as the binary representation of an element
in [2m − 1].
For all h ∈ Gk,n (X ), h can be represented by k, n, the coefficients of ph and a description of the
field F2m . This representation can be encoded in poly(k, n, log |X |) bits.
Now, given this encoding, evaluation of ph (x) can be done in poly(m) = poly (k, n, log |X |) time.
And computing

hx = min z ∈ [n] : F (z) ≥ (T (ph (T −1 (x))) mod d) + 1
to get an approximate count takes poly (k, n, log |X |) time.

Proof of v. Let A ⊆ X such that |A| ≤ n and c ∈ [n]A . We can sample h given by the coefficients
a0 , . . . , an ∈ F2m uniformly at random from Gk,n (X ) such that hx = cx for all x ∈ A with the
following steps.
1. Construct F2m by finding an irreducible polynomial of degree m over F2 .
2. For each x ∈ X , sample ũx uniformly at random from the set
Sx = {y ∈ F2m : cx = min {z ∈ [n] : F (z) ≥ (T (y) mod d) + 1}}
We can sample from this set by observing that
Sx = {y ∈ F2m : F (cx − 1) < (T (y) mod d) + 1 ≤ F (cx )}
= {y ∈ F2m : ∃i, r ∈ N such that T (y) = i · d + r and F (cx − 1) < r + 1 ≤ F (cx )}
= T −1 ({i · d + r ∈ [2m − 1] : i ∈ N and F (cx − 1) < r + 1 ≤ F (cx )})
 m

⌊2 /d⌋−1
[
{i · d + r ∈ [2m − 1] : F (cx − 1) < r + 1 ≤ F (cx )}
= T −1 
i=0

3. Let B ⊆ X such that A ⊆ B and |B| = n + 1. For all x ∈ B \ A, sample ũx uniformly at
random from F2m .
4. Take the coefficients a0 , . . . , an ∈ F2m to be the coefficients of the interpolating polynomial
over F2m given the set of points (x, ũx ) for all x ∈ B. This polynomial exists and is unique.

34

We first prove correctness. Notice this procedure can only return a histogram h ∈ Gk,n (X ) such
that hx = vx for all x ∈ A. Let h be any such histogram. Then
Pr[Sampling h] = Pr[(a0 , . . . , an ) are the coefficients of ph ]
= Pr[∀x ∈ B ũx = ph (x)]
Y
=
Pr[ũx = ph (x)]
x∈B

=

Y 1
|Sx |

x∈A

!  
1 |B\A|
·
2m

Therefore, these steps output h ∈ Gk,n (X ) uniformly at random such that hx = vx for all x ∈ A.
Construction of F2m can be done in O(m4 ) time [Sho90]. Integer operations are limited to
numbers not exceeding 2m . And polynomial interpolation takes O(n2 ) · poly(m) time [BP70].
Therefore, this procedure runs in time poly(k, n, log |X |).
Algorithm 3.6 (BoundedGeometricMechanism) has on each bin a count with marginal distribution Geosample(k, n, cx (D)) and its counts are independent. By using the previously defined
family, the following algorithm has essentially the same marginal distributions as Algorithm 3.6,
but the counts are only (n + 1)-wise independent. This yields an efficient algorithm as we only
need a small number of random bits (polynomial in log |X |) compared to the amount required for
all counts to be independent (linear in |X |).
Algorithm 7.2. CompactHistogram(D, ε) for D ∈ X n and rational ε ∈ (0, 1]
1. Let k = ⌈log(4/ε)⌉.
2. Let A = {x ∈ X : cx (D) > 0}.
3. For each x ∈ A, let c̃x = GeoSample(k, n, cx (D)).
4. Release h drawn uniformly at random from {h′ ∈ Gk,n (X ) : ∀x ∈ A h′x = c̃x }.

Theorem 7.3. Let rational ε ∈ (0, 1] and ε̃ = 2 · ln 1 + 2−⌈log(4/ε)⌉ ∈ (2ε/9, ε/2]. Then
CompactHistogram(D, ε) has the following properties:
i. CompactHistogram(D, ε) is (ε, 0)-differentially private.
ii. CompactHistogram(D, ε) has (a, β)-per-query accuracy for


2 1
ln
a=
ε̃ β
iii. CompactHistogram(D, ε) has (a, β)-simultaneous accuracy for


2 |X |
ln
a=
ε̃
β

35

iv. CompactHistogram(D, ε) has running time
poly(N )
where N is the bit length of this algorithm’s input (D ∈ X n and ε)
Proof of i. Let D, D ′ ∈ X n be neighboring datasets. Let A = {x ∈ X : cx (D) > 0}. Similarly,
define A′ = {x ∈ X : cx (D ′ ) > 0}. Let B = A ∪ A′ . Notice |B| ≤ n + 1. Let g ∈ Gk,n (X ). Let h be
drawn uniformly at random from Gk,n (X ). Then
Pr[CompactHistogram(D, ε) = g]
= Pr[∀x ∈ B CompactHistogram(D, ε)x = gx ] · Pr[h = g | ∀x ∈ B hx = gx ]

!
Y
Y
Pr[Zx (D) = gx ] 
Pr[hx = gx ] · Pr[h = g | ∀x ∈ B hx = gx ]
=
x∈A

x∈B\A

where Zx (D) ∼ GeoSample(k, n, cx (D)). Now, because |B \ A| = 1 and and |B \ A′ | = 1 along with
Proposition 3.3 and part i of Lemma 7.1
Pr[CompactHistogram(D, ε) = g]
Pr[h = g | ∀x ∈ B hx = gx ]

!
Y
Y
Pr[Zx (D) = gx ] 
Pr[hx = gx ]
=
x∈A

(1/3)·2−k+1

≤e

·

Y

x∈B\A

Pr[Zx (D) = gx ]

x∈B
−k+1

≤ eε̃+(1/3)·2

·

Y

Pr[Zx (D ′ ) = gx ]

x∈B

≤

ε̃+(1/3)·2−k+1

e

·

Y

x∈A′

≤ eε ·


!
Y
−k+1
Pr[Zx (D ′ ) = gx ] e(2/3)·2
·
Pr[hx = gx ]
x∈B\A′

Pr[CompactHistogram(D ′ , ε)

= g]
Pr[h = g | ∀x ∈ B hx = gx ]

as ε̃ ≤ ε/2 and 2−k+1 ≤ ε/2. Therefore, CompactHistogram(D, ε) is (ε, 0)-differentially private.
Proof of ii. Let h ∼ CompactHistogram(D, ε) and A = {x ∈ X : cx (D) > 0}. Let x ∈ A. Then,
by construction, hx ∼ GeoSample(k, n, cx (D)) and (a, β)-per-query accuracy follows from part ii of
Theorem 3.7.
Let x ∈ X \ A and h′ be drawn uniformly at random from Gk,n (X ). Notice cx (D) = 0 and
|A| ≤ n. By parts ii and iii of Lemma 7.1
Pr[|hx | ≤ a] = Pr[h′x ≤ a | ∀x ∈ A h′x = hx ]
= Pr[h′x ≤ a]
≥ Pr[Z ≤ a]
where Z ∼ GeoSample(k, n, 0). Thus, (a, β)-per-query accuracy follows from part ii of Theorem
3.7.
36

Proof of iii. A union bound over each x ∈ X along with the previous part gives a bound on the
(a, β)-simultaneous accuracy.
Proof of iv. CompactHistogram(D, ε) makes at most n calls to GeoSample. Therefore, by Proposition 3.3 and by part v of Lemma 7.1, we get the desired bound on running time.
Therefore, we have constructed a histogram algorithm with running time polynomial in and
accuracy matching lower bounds for releasing private histograms up to constant factors.

Acknowledgments
We thank the Harvard Privacy Tools differential privacy research group, particularly Mark Bun
and Kobbi Nissim, for informative discussions and feedback, and the anonymous TPDP reviewers
for helpful comments.

References
[BBKN14] Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds
on the sample complexity for private learning and private data release. Machine learning, 94(3):401–437, 2014.
[BLR13]

Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM (JACM), 60(2):12, 2013. URL
https://arxiv.org/pdf/1109.2229.pdf.

[BNS16]

Mark Bun, Kobbi Nissim, and Uri Stemmer.
Simultaneous private learning
of multiple concepts.
In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 369–380. ACM, 2016.
URL
https://arxiv.org/pdf/1511.08552.pdf.

[BP70]

Åke Björck and Victor Pereyra. Solution of vandermonde systems of equations. Mathematics of Computation, 24(112):893–903, 1970.

[CDK17]

Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv’it: Private and
sample efficient identity testing. arXiv preprint arXiv:1703.10127, 2017. URL
https://arxiv.org/pdf/1703.10127.pdf.

[CKKL12] Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, and Homin K Lee. Submodular
functions are noise stable. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1586–1592. Society for Industrial and Applied
Mathematics, 2012. URL https://arxiv.org/pdf/1106.0518.pdf.
[CPST11]

Graham Cormode, Magda Procopiuc, Divesh Srivastava, and Thanh TL Tran. Differentially private publication of sparse data. arXiv preprint arXiv:1103.0825, 2011. URL
https://arxiv.org/pdf/1103.0825.pdf.

[CTUW14] Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan.
Faster private release of marginals on small databases. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 387–402. ACM, 2014.
URL https://arxiv.org/pdf/1304.3754.pdf.
37

[DL09]

Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings
of the forty-first annual ACM symposium on Theory of computing, pages 371–380.
ACM, 2009.

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise
to sensitivity in private data analysis. In Theory of Cryptography Conference, pages
265–284. Springer, 2006.
[DNT15]

Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrete & Computational Geometry,
53(3):650–673, 2015. URL https://arxiv.org/pdf/1308.1385.pdf.

[GMP16]

Ivan Gazeau, Dale Miller, and Catuscia Palamidessi. Preserving differential privacy
under finite-precision semantics. Theoretical Computer Science, 655:92–108, 2016. URL
https://arxiv.org/pdf/1306.2691.pdf.

[GRS12]

Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utilitymaximizing privacy mechanisms. SIAM Journal on Computing, 41(6):1673–1693, 2012.

[GRU12]

Anupam Gupta, Aaron Roth, and Jonathan Ullman.
Iterative constructions
and private data release. Theory of Cryptography, pages 339–356, 2012. URL
https://arxiv.org/pdf/1107.3731.pdf.

[HRS12]

Moritz Hardt, Guy N Rothblum, and Rocco A Servedio. Private data release via learning thresholds. In Proceedings of the twenty-third annual ACM-SIAM symposium on
Discrete Algorithms, pages 168–187. Society for Industrial and Applied Mathematics,
2012. URL https://arxiv.org/pdf/1107.2444.pdf.

[HT10]

Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings
of the forty-second ACM symposium on Theory of computing, pages 705–714. ACM,
2010. URL https://arxiv.org/pdf/0907.3754.pdf.

[KLN+ 11] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and
Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–
826, 2011. URL https://arxiv.org/pdf/0803.0924.pdf.
[Knu05]

Donald E Knuth. Combinatorial Algorithms, Part 1, volume 4 of The Art of Computer
Programming. Addison-Wesley Professional, 2005.

[Mir12]

Ilya Mironov. On significance of the least significant bits for differential privacy. In
Proceedings of the 2012 ACM conference on Computer and communications security,
pages 650–661. ACM, 2012.

[Sho90]

Victor Shoup. New algorithms for finding irreducible polynomials over finite fields.
Mathematics of Computation, 54(189):435–447, 1990.

[TUV12]

Justin Thaler, Jonathan Ullman, and Salil Vadhan. Faster algorithms for privately releasing marginals. In International Colloquium on Automata, Languages, and Programming, pages 810–821. Springer, 2012. URL https://arxiv.org/pdf/1205.1758.pdf.

[UV11]

Jonathan Ullman and Salil P Vadhan. PCPs and the hardness of generating private synthetic data. In TCC, volume 6597, pages 400–416. Springer, 2011. URL
https://pdfs.semanticscholar.org/bf6f/e68b91283787b9ad28494a78b4cead10fa12.pdf.

38

A1

Generating a Sparse Histogram Uniformly at Random

Being able to efficiently compute |Hn,n′ (X )| and sample a uniformly random element from Hn,n′ (X )
is needed for an efficient implementation of Algorithm 4.13.
Lemma A1.1. |Hn,n′ (X )| can be calculated and a uniformly random element of Hn,n′ (X ) can be
sampled in time
poly(n′ , log n, log |X |)
Proof. We show HistSample(X , n, n′ ) defined below efficiently samples a uniformly random element
of Hn,n′ (X ) by using a bijection between Hn,n′ (X ) and {1, . . . , |Hn,n′ (X )|}.
Algorithm A1.2. HistSample(X , n, n′ ) for n, n′ ∈ N+ with n′ ≤ |X |
P ′
1. Pick U uniformly at random from {1, . . . , |Hn,n′ (X )|} = {1, . . . , ni=0

P
2. Find the smallest ℓ ∈ [n′ ] such that ℓi=0 |Xi | ni ≥ U .
i
Pℓ−1 |X | i h |X | ℓ
3. Let u′ = U − 1 − i=0
n
∈
·
n
−
1
.
i
ℓ
4. Use integer division to find q ∈

h

|X |
ℓ −

|X | i
i n }.

i


1 and r ∈ nℓ − 1 such that u′ = qnℓ + r.

5. Map q to a corresponding subset of X of size ℓ specified by sorted elements q1 < . . . < qℓ .
Specifically, we can let q1 , . . . , qℓ ∈ X be the sequence representing q in the combinatorial
number system of degree ℓ, i.e. the unique sequence satisfying
 
 
qℓ
q1
q=
+ ... +
ℓ
1
This sequence can be found P
greedily; for each j decreasing from ℓ to 1, using binary search,
find the largest qj such that ℓi=j qii ≤ q [Knu05].

6. Let r0 , . . . , rℓ−1 ∈ [n − 1] be the digits of the base n representation of r, i.e.
r = rℓ−1 nℓ−1 + . . . + r1 n + r0
7. For each i ∈ {1, . . . , ℓ}, release (qi , ri−1 + 1).

Steps 3 and 4 define a bijection mapping u to (ℓ, u′ ). Step 5 defines a bijection mapping (ℓ, u′ )
to (ℓ, q, r). In steps 6 and 7, the decompositions of q and r into their respective number systems are
bijections. Likewise, there is a bijection mapping (q1 , . . . , qℓ , r0 , . . . , rℓ−1 ) to an element of Hn,n′ (X ).
Therefore, our mapping from {1, . . . , |Hn,n′ (X )|} to Hn,n′ (X ) is bijective proving correctness.

P ′
Computing |Hn,n′ (X )| = ni=0 |Xi | ni takes poly(n′ , log n, log |X |) time. The remaining steps
can be done in poly(n′ , log n, log |X |) time as no number used exceeds |Hn,n′ (X )|, all numbers used
are expressible as the sum of at most n′ other numbers and steps 5-7 each consist of at most n′
iterations.

39

