When Random Sampling Preserves Privacy

Kamalika Chaudhuri1 and Nina Mishra2

1
Computer Science Department, UC Berkeley, Berkeley, CA 94720?
2
Computer Science Department, University of Virginia, Charlottesville, VA 22904??

Abstract. Many organizations such as the U.S. Census publicly release

samples of data that they collect about private citizens. These datasets
are first anonymized using various techniques and then a small sample
is released so as to enable “do-it-yourself” calculations. This paper in-
vestigates the privacy of the second step of this process: sampling. We
observe that rare values – values that occur with low frequency in the
table – can be problematic from a privacy perspective. To our knowl-
edge, this is the first work that quantitatively examines the relationship
between the number of rare values in a table and the privacy in a re-
leased random sample. If we require -privacy (where the larger  is, the
worse the privacy guarantee) with probability at least 1 − δ, we say that
a value is rare if it occurs in at most Õ( 1 ) rows of the table (ignoring log
factors). If there are no rare values, then we establish a direct connection
between sample size that is safe to release and privacy. Specifically, if we
select each row of the table with probability at most  then the sample
is O()-private with high probability. In the case that there are t rare
values, then the sample is Õ(δ/t)-private with probability at least 1 − δ.

1 Introduction

Private data is collected by numerous organizations for a wide variety of pur-

poses including reporting, data mining, scientific discoveries, etc. In some cir-
cumstances, this data is in turn released in sanitized form for public consump-
tion. The purpose of releasing such sanitized data is to enable others to discover
large-scale statistical patterns, e.g., to learn averages, variances, clusters, deci-
sion trees, while hiding small-scale information, e.g., a particular individual’s
salary. The question we ask is: To what extent do these sanitized datasets pre-
serve people’s privacy?
While there are numerous examples of sanitization procedures, we investigate
one commonly used technique: random sampling. Some organizations routinely
collect data, anonymize it, and then release a sample so that others may use the
data for data mining purposes. Since samples are known to preserve statistical
characteristics of the data, samples can be a useful means for studying and
understanding the underlying population.
?
kamalika@[Link].
??
nmishra@[Link]. Research supported in part by NSF EIA-0137761.
1.1 Motivating Examples

There are many examples of released samples of private data. We describe two,
one from the U.S. Census and one from the Social Security Administration.
The U.S. Census Bureau releases a Public Use Microdata Sample (PUMS) [2].
This dataset contains private information in occupied housing units such as age,
weight, income, and race. The Census gathers this data once every 10 years,
anonymizes it and then releases a 1% or 5% sample. The purpose of releasing
this microdata is to allow “do-it-yourself” calculations. Our work is motivated
by such releases: Can we simply select each individual with probability 0.05 to
be included in the sample? What role do rare values play in deciding what to
release? What size sample is safe to release?
The Social Security Administration (SSA) also releases microdata, specifi-
cally Benefits and Earnings files [11]. Old-Age, Survivors, and Disability Insur-
ance (OASDI) is a government-sponsored insurance program that individuals
contribute to throughout their working careers. Benefits are paid to insured
workers and family members when they retire or become disabled. This dataset
contains annual earnings information for approximately 47 million individuals
who receive OASDI benefits each month. Personal identifying information and
distinguishing characteristics are removed or modified to prevent identification.
Records are randomly permuted. The SSA then releases a 1% sample of this
data.
Our work is a first attempt at formally understanding the privacy guarantees
of just one step of the sanitization process: random sampling. In practice, these
organizations employ multi-step anonymization processes prior to sampling that
this paper does not analyze.

1.2 The Model

We consider the following simplified setting. The sanitizer starts with a table
T consisting of k distinct private values. The k values can be anything, e.g.,
Boolean data over log k attributes, k real numbers, etc. The sanitizer then goes
through each row of the table and includes it in the sample with probability p
and does nothing with probability 1 − p. The sample is then randomly permuted
and released. We then ask the question: for what p can we guarantee privacy?
In order to understand this question, we next define privacy.

1.3 Privacy

The privacy definition that we use is motivated by [5]. The authors capture the
interaction between a sanitizer and a hypothetical attacker via a transcript. In
our case, the transcript is a random sample S of the data. Intuitively, for any pair
of tables T and T 0 that differ in only one position, privacy is preserved if a hypo-
thetical attacker upon seeing the transcript S is unable to distinguish between
the case when the actual table is T or T 0 . In other words, an attacker knowing
all but one person i’s private information does not gain much information about
i upon seeing the sample.
We consider two definitions of privacy, one where a hypothetical attacker
tries to distinguish between two tables that differ in one row, and the other,
where a hypothetical attacker tries to distinguish between two tables that differ
in c rows. We say that a sanitization scheme is (c, , δ)-private if for every table
T , with probability at least 1 − δ, the scheme produces a sample S such that for
any set of c rows in the table, P , and for any two sets of c assignments V and
Pr(S|T )
V 0 , Pr(S|T {P →V0} ) ≤ 1 + . The privacy definition is discussed in Section 3.
{P →V }

1.4 Discussion

Our results do not apply in the case that the data is a collection of distinct
points, say in Rd . The reason is that if every point is different from every other
point in the table then a sample of size even one violates the privacy of that
individual. As a simple example, suppose the table consists of five private values
h1, 2, 3, 4, 5i and we release the sample point 2. Then the attacker can now easily
tell that the data came from the actual table versus h1, 3, 3, 4, 5i. This violates
privacy since the attacker can now distinguish between two tables that differ in
one row.
Problems arise even if a value is not unique, but occurs a few times in the
table. We call such a value a rare value. Observing a rare value is problematic
because a rare value can be assumed by only a small group of individuals, and
then observing such a value can potentially increase the hypothetical attacker’s
confidence about the values assumed by this small select group of people. For
example, consider a table in which two individuals can have a salary of one
billion dollars, and an attacker knows the salary of one of them and not the
other. If we release a sample in which a row with a salary of one billion dollars
appears, then the confidence of the attacker about the second individual’s salary
increases. This is because such a sample is much more likely to have come from
a table in which two people have a salary of a billion dollars than from a table
in which one person’s salary is a billion dollars.
Unique values are known to be problematic in the literature. Indeed, the
phrase “population unique” is used to describe those individuals that are un-
like anyone else in the population, e.g., 13-year-old college graduate. Population
uniques are often first removed prior to data sanitization. To the best of our
knowledge, we have not seen work that quantifiably links rare values to privacy.
In this paper, we find such a link. If we desire  privacy with probability at least
1 − δ, we define a rare value to be one that occurs less than O( 1 log( 2k
δ )) times
in the table. If i rows with a certain rare value v appear in the sample, it can
lead to an O(i/ log(2k/δ)) breach of privacy.

One way to deal with rare values is to suppress such rows from the table.
Indeed, in practice, organizations remove population uniques. We do not consider
such sanitization algorithms because then the decisions made by the sanitizer
cannot be mimicked or simulated by the attacker – and as a result, information
may be leaked3 . This may seem unintuitive at first – how can private information
that we do not even release breach privacy? An example illustrates the point.
Suppose the sanitizer decides to suppress all values that occur < 100 times, and
rows 1 to 100 of a table take the value 0, and no other rows take the value 0.
Let p > 1/100. Now suppose that an attacker knows the value of the first 99
rows and is trying to decide what the value of the 100th row is. In this case, not
seeing any row with value 0 in the sample violates the privacy of this 100th row.
Another reason why removing rare values is problematic is that just the size
of the sample can leak information. In the case where the table contains n rows
and 1/10th of the rows contain rare values, then the expected sample size is
9np/10 instead of np. Alternatively, if the sanitization algorithm is to draw a
sample and remove “sample uniques” (those individuals that are one-of-a-kind
in a sample), then if every entry in the sample is unique, then nothing may be
released. Thus just the size of the sample can leak information.

Because unique and rare values can lead to privacy breaches, we assume that
k the number of distinct values is much smaller than n the number of individuals
in the dataset. In practice, this is not true because each individual in the table
has a uniquely identifying key. The assumption that k << n implies that identi-
fying information has been removed. This is admittedly a large assumption since
it is an open question what information is “identifying” (see, for example, [12]).
But we make this assumption so that we can focus our attention on understand-
ing the privacy consequences of sampling.

One limitation of sampling is the probability that the sanitization algorithm

fails to produce an output that preserves privacy is not negligble in n. Ideally, we
would like to say that the sanitization algorithm fails with very low probability,
e.g., 1/(2n ). With random sampling, we cannot guarantee a failure probability
better than 1/n. To see why, suppose the table has a unique value. If we sample
each row of the table with probability p = 1/n, then the probability we pick
this value is 1/n. But once a unique value appears in the sample then we have
completely breached this individual’s privacy. So the probability we fail is 1/n.

Even if there are no rare values at all, releasing a random sample of the data
cannot preserve privacy with probability 1. As an example, consider a table that
has n/2 rows with value 0 and n/2 rows with value 1, and a sample S from this
table of size n/2 consisting of all 0s. The attacker knows the value of all rows in
the table except for one row - that is, she is trying to decide whether the sample
S came from a table with n/2 0s and n/2 1s or from a table with n/2 + 1 0s
and n/2 − 1 1s. The latter event is about n/2 times more likely than the former.
The attacker will therefore conclude that the value of the missing row is 0, and
this will lead to a breach in privacy. It turns out that when we do sampling, we
3
The notion of simulatability is already known to be important in cryptography [8]
and also in privacy research [9, 3].
cannot avoid these situations entirely except to upper bound the relatively small
probability that such unlikely samples occur. We also note that the probability
of failure due to the occurrence of such unlikely samples is quite small compared
to the probability of failure to preserve privacy because of the occurrence of one
or more rows with rare values in the sample.

1.5 Contributions

Privacy For the case where an attacker tries to distinguish between two tables
that differ in one row, i.e., (1, , δ)-privacy, we define a rare value as one that
log( 2k )
occurs in at most 
δ
rows of the table, where k is the number of distinct
values in the table. We show that if there are no rare values, then a sampling
frequency of at most  preserves privacy. In the case where there are at most t
rare values, we show that a sampling frequency of at most Õ( δt ) preserves pri-
vacy. Observe that the higher the number of rare values, the lower the sampling
frequency, as one would expect. We also demonstrate that the upper bound on
the sampling frequency is tight up to log factors.
Furthermore, we consider the case where a hypothetical attacker already
knows n − c rows of the table and the goal is (c, , δ)-privacy. Now a rare value is
log( 2k )
one that occurs in at most 
δ
+c rows of the table. We prove that when there
are no rare values, a sampling frequency of at most  still preserves (c, O(c), δ)-
privacy. When there are at most t rare values, we show that a sampling frequency
of p < Õ( δt ) is (c, O(c), δ)-private.
The proof technique is similar in both cases. We partition the values in the
table T into rare, infrequent and common depending on how often they occur.
We then define a good sample to be one with no rare values, with infrequent
values that do not occur very frequently, and common values that occur close to
expectation. We prove that if we have a good sample, we have privacy. Then we
prove that with high probability, random sampling produces a good sample.

Utility For someone who is interested in discovering patterns in the released

data, it is natural to ask whether sampling preserves patterns. Samples are in
fact known to approximately preserve statistics about the actual table. But note
again that, in practice, sampling is used in concert with other anonymization
techniques. We are not making any claims about the utility of those anonymiza-
tion procedures – we only discuss the utility of sampling.
When we release a random sample of the data, we are essentially releasing
an estimate of the histogram – the frequency of each value v. Random sampling
q
t
can estimate the frequency of each value v with an additive noise of Õ( nδ )
when there are t rare values, and we want (1, , δ)-privacy.
Note that in contrast, [5] can release the histogram of a table by adding a
2
tiny O( n ) additive noise to the frequency of each possible value, a significantly
smaller additive noise. We also note that unlike sampling, the error in [5] is
independent of the number of rare values. Also the more privacy that is required,
the better [5] does compared to sampling.
If U is the total universe of values a row in the table can take, we note that [5]
needs to release |U | numbers in order to release a privacy-preserving histogram.
We in contrast, need to release only k numbers. When the size of U is much
larger than k, releasing a random sample is a more compact way of releasing the
histogram.

2 Related Work

We partition related work according to what the sanitizer does with the private
data. In the input perturbation family of methods, the private data is perturbed
and published as a one-time operation. The perturbed dataset must withstand
an unlimited number of queries. In the output perturbation family of methods,
the sanitizer receives queries about the private dataset from an attacker. The
sanitizer then outputs either the true answer, a perturbed answer, or refuses to
answer altogether.

2.1 Input Perturbation

While we assume that the dataset is not a collection of distinct points in Rd ,

another approach is to redefine privacy with respect to this higher dimensional
space. Such a compelling definition is given in [3] where a point is kept private if
it “blends with the crowd”. That paper offers simulatable methods for perturbing
the input so that privacy is preserved. Several utility results are given including
learning mixtures of Gaussians and k–Center clustering.
An alternate input perturbation technique was suggested in [7]. That paper
describes a method for modifying private data (adding and deleting purchase
behavior) so as to enable the discovery of frequent itemsets while maintaining
privacy. The privacy guarantees given in that paper are quite strong. But the
notion of utility is strongly tied to frequent itemsets.
An input perturbation technique based on pseudorandom sketches was given
in [10]. The idea is that each individual takes their own data over d bits, repre-
sents it as a vector of length 2d with a 1 in the single position corresponding to
their private value and a 0 everywhere else. Each bit of this vector of length 2d
is then flipped with probability p. This perturbed vector is then replaced with a
slightly biased coin that forms a seed s to a pseudorandom function. The authors
show that privacy is preserved in a strong sense, i.e., for all individuals xi and
for all values v, v 0 , Pr(s|xi = v) ≈ Pr(s|xi = v 0 ). Furthermore, various utility
results are given including estimating the fraction of individuals that satisfy any
conjunction of attributes, estimating the fraction of individuals that have private
values ≤ x, etc.
2.2 Output Perturbation

A different method for preserving privacy is output perturbation [4, 6, 1, 5, 9].

One specific output perturbation result that is very relevant to this paper is
due to Dwork et al [5]. The authors introduce the notion of the sensitivity of a
function which is how much the function f can change when one row of the data
changes. Privacy is then shown to be preserved if the sanitizer answers each query
with additive Laplacian noise that is proportional to the function’s sensitivity.
Specifically, the sanitizer returns the true answer plus Lap( sen(f

)
) where Lap(λ)
|y|
is the Laplace distribution with density proportional to p(y) ∝ e− λ . The more
sensitive the query, the more noise is added. The sensitivity of a sequence of
queries is the extent to which the sequence can change when one row of the
table changes. For example, the sensitivity of a histogram is 2 since changing
one row of the table at most removes a value from one bucket and adds it to
another.

3 Preliminaries

We use the term table to mean the original unperturbed data and denote it by
T . Each entry of the table is assumed to be a tuple of the form (i, j) where i is
some unique identifier, e.g., SSN, name, and j is an integer that represents the
individual’s private data, e.g., if the data is in binary form, then one can view j
as the integer representation of the binary data.
We assume that the table has n entries, where each entry can take an integer
value. We assume that the total number of distinct values taken by the rows of
the table is k.
We use the term sample or sanitized table to denote the result of the saniti-
zation process that the attacker observes and we denote it by S. Note that S is a
randomized object, whereas T is a deterministic input supplied to the sanitizer.
Given a table T , the goal of the sanitizer is to release a sample S of T where
the sample does not give the attacker any additional information about any row
of the table beyond what the attacker already knows from looking at the rest of
the table.

3.1 Privacy Definition

Our definition of privacy is closely related to (1, )-privacy proposed by [5] (where
it was called -indistinguishability).

Definition 1 A sanitization mechanism is (1, )-private if for every pair of ta-

bles T and T 0 that differ in one row

Pr[S|T ]
≤1+
Pr[S|T 0 ]
 Here Pr[S|T ] denotes the probability that the sanitization mechanism out-
puts S given as input the table T and it is taken over the random choices made
by the sanitizer. This definition states that the posterior probability that the
sample S came from table T is almost the same as the probability it came from
table T 0 ; therefore observing S does not enable the attacker to distinguish be-
tween these two tables reliably.
As mentioned in Section 1.4, we cannot ensure privacy with probability 1
as the table may have rare values or we may simply draw an unrepresentative
sample. Consequently, we allow our sanitizer a δ probability of failure.

Definition 2 A sanitization mechanism is (1, , δ)-private if, for every table T ,

with probability at least 1 − δ, the mechanism produces S such that for all values
v and v 0 :
Pr[S|T{i→v} ]
≤1+
Pr[S|T{i→v0 } ]
where the probability is taken over the random choices made by the sanitizer.

This definition states that regardless of the table T , with high probability, the
sample S produced does not significantly help the attacker distinguish between
any two values v and v 0 for the ith individual in the table. While this quantifies
over all possible values, it includes as a special case the ith individual’s actual
value and any other value.
Sometimes, there may be correlations between the values of a small number
of rows in a database and these correlations may be known to the attacker. For
example, the HIV status of a husband and wife are probably the same. This
can be thought of more generally as follows. Suppose the table is partitioned
into sets of rows {Pi } such that if the attacker knows the value of one row in
a partition Pj , she knows the value of every row in the partition. In such a
situation, we might want to consider an attacker who knows the value of all
rows in the table except for the rows in one partition, and examine what this
attacker can learn by looking at the sanitized data. This motivates the notion
of (c, )-privacy proposed by [5]. (c, )-privacy ensures that the probability that
the sanitized data came from two tables T and T 0 that differ in at most c rows
is almost the same.
Typically, more noise is needed to achieve (c, )-privacy than is needed to
achieve (1, )-privacy. This sounds counterintuitive at first; how could it be
harder to guarantee privacy for an attacker who knows the value of only n − c
rows of a table than it is to guarantee privacy for an attacker who knows the
value of n − 1 rows? This happens because we say that a violation of privacy oc-
curs when there is a deviation from what the attacker already knows. To ensure
that there is no deviation from the attacker’s knowledge, we need to hide more
from an attacker who knows less than from an adversary who knows more.
We can think of an analogous notion of (c, , δ)-privacy as well. The definition
is identical to (1, , δ)-privacy except for any set of c rows in the table T , Pi ,
and for any pair of states V and V 0 the sample does not substantially help the
attacker distinguish between T{Pi →V } and T{Pi →V 0 } .
 It is shown in [5] that a sanitization mechanism that is (1, c )-private is also
(c, )-private. This argument can be extended to show that a mechanism which
is (1, c , δc )-private is also (c, , δ)-private.

3.2 Some Notation

We use the following notation for the rest of the paper. Let n be the total number
of items in the table, and let n1 , n2 , . . . , nk denote the number of items in the
table with value 1, 2, . . . , k respectively. Let s denote the size of the sample, and
s1 , s2 , . . . sk denote the number of items in the sample with value 1, 2, . . . , k.
Let V = {v1 , v2 , . . . , vc } be a sequence of c values. We say that a sequence of
c rows has state V if row i in the sequence has value vi .
We use the notation T{i→v} to denote a table T in which row i is set to have
a value v, and T \ {i} to denote the set of all rows in table T except row i.
Similarly, for a set of rows Pi , we use the notation T{Pi →V } to denote a table T
in which the set of rows Pi have state V , and T \ {Pi } to denote the set of all
rows in table T except the rows in set Pi .

4 (1, , δ)-privacy

In this section, we show what sampling probability is (1, , δ)-private. Given ,

δ, a table T and k, the number of distinct values in the table, we provide p, a
sampling frequency that is (1, , δ)-private.
Our guarantees can be summarized as follows.

Theorem 3 Given a table T , let α = 2δ , k be the number of distinct values in

2 log( k )
T and t be the total number of values in T that occur less than 
α
times.
0 1
Also let  = max(2(p + ), 6p) and p +  < 2 .
 log( 1−α
1
)
Then, a sample S of T drawn with frequency p ≤ 4t log( k
)
is (1, 0 , δ)-private
α
when t > 0. When t = 0, a sample S of T drawn with frequency p ≤  is (1, 0 , δ)-
private.

We need the assumption p +  < 12 to make sure p is bounded away from

1 by a constant. (Any other constant than 12 would do, but would change the
constants in Theorem 3. ) We want this condition because if p is too close to
1, all rows containing a certain value may appear in the sample, leading to a
serious breach of privacy.
Note that for certain tables such as those consisting only of unique values,
the upper bound on p according to our theorem is less than 1/n. This should
be interpreted as the fact that we cannot guarantee (1, , δ)-privacy for a sample
even of size 1.
The theorem shows that for a given table T and a given failure probability δ,
1
the lower the value of p, the better the privacy guarantee. Since log( 1−α ) u α, p
varies linearly as δ. This means that δ, the failure probability, has to be at least
1
n to ensure we draw a random sample even of size 1. This is expected, because
in a table with a unique value v, the probability that any random sample selects
this value is at least n1 . We see in Observation 6 that this dependence of p on δ
is almost tight except for the factor of log( αk ).
Before we prove Theorem 3, we provide some intuition. For our proofs, we di-
vide the set of values in the table T into three categories – rare values, infrequent
values and common values.

Definition 4 A value is said to be a common value if it occurs in at least

k
12 log( α )
p rows of the table, where p is the sampling frequency. A value v is called
2 log( k )
a rare value if it occurs in at most 
α
rows of the table. A value that is
neither rare nor common is called an infrequent value.

A common value v has the property that the expected number of such values
in the sample S is at least Ω(log( αk )), and therefore the number of such values
in the sample is tightly concentrated around its mean.
If a value v is not a common value, we can only show using Chernoff Bounds
that the number of occurrences of v in T is away from its expected value by at
most O(log( αk )). If about log( αk ) rows with a rare value v occur in the released
sample, the posterior probability Pr[S|T{i→v} ] can increase by more than a (1+)
fraction. To deal with this, we hide all such rows. This is achieved by making p
less than the inverse of the total number of such rare values.
A value that is neither common nor rare is called an infrequent value. Such
a value may appear in a sample S, but the number of such values cannot be
guaranteed to be tightly concentrated around its expectation. However, releasing
about O(log( αk )) rows with such a value does not lead to an  breach in privacy.
As we showed earlier, releasing any sample drawn from a table does not ensure
(1, , δ)-privacy. We show that privacy is preserved when we draw a sample with
certain properties, and such a sample occurs with high probability. A sample
possessing these properties is called a good sample.

Definition 5 A good sample is one that has the following properties: (1) A rare
value v does not occur. (2) An infrequent value v occurs in at most nv p+2 log( αk )
q
rows. (3) A common value v occurs in at most nv p + 3nv p log( αk ) rows.

In Lemma 1, we show that releasing a good sample preserves privacy. In

Lemma 2, we show that a good sample occurs with high probability. Combining
Lemmas 1 and 2, we get a proof of Theorem 3.

Lemma 1. Let S be a good sample drawn from table T . Then for any row i and
any pair of values v and v 0 ,
Pr[S|T{i→v} ]
≤ 1 + 0
Pr[S|T{i→v0 } ]

where 0 = max(2(p + ), 6p) for p +  < 12 .

Proof. For any value u, let n1u be the number of rows in table T \ {i} with value
u, and let su be as usual the number of rows with value u in the sample S. Then,
T{i→v} has n1v + 1 rows with value v and n1v0 rows with value v 0 .
We now show that since S is a good sample, sv < n1v + 1. If row i of T takes
any other value than v, this holds trivially; otherwise, we claim that at most n1v
rows of T that take value v appear in S. If v is a rare value, there are no rows
with value v in a good sample. If v is an infrequent value, the maximum number
of rows with value v in the sample is at most (n1v +1)p+2 log( αk ) which is at most
n1v (p+)+p < n1v for p+ < 1/2. If v is a common value, the maximum
q number of
rows with value v in the good sample S is at most (n1v +1)p+ 3(n1v + 1)p log( αk ),
r !
k
3 log( α )
which is at most (n1v + 1)p 1 + (n1v +1)p ≤ 23 (n1v + 1)p < n1v + 1 when p < 12 .

Therefore,
n1v +1 n1v0 sv 0
1−



Pr[S|T{i→v} ] sv sv 0 n1v0 +1
= =
Pr[S|T{i→v0 } ] n1v n1v0 +1 1 − n1s+1
v



sv sv 0 v

For a rare value v, sv = 0. Therefore,

sv 0
1− n1v0 +1 sv0
=1− ≤1
1 − n1s+1
v
n1v0 + 1
v

For an infrequent value v, since there are at most n1v + 1 rows with value v in
k
2 log( α )
the table T , sv ≤ (n1v + 1)p + 2 log( αk ) and n1v + 1 ≥  . This implies that,
sv
n1 +1 ≤ p +  and assuming p +  < 1/2,
v

sv 0
1− n1v0 +1 p+
≤1+ ≤ 1 + 2(p + )
1 − n1s+1
v
1 − (p + )
v

For a common value v, as there q are either n1v or n1v + 1 rows with value v in the
table, sv is at most (n1v + 1)p + 3(n1v + 1)p log( αk ), and (n1v + 1)p ≥ 12 log( αk ).
sv
Therefore n1v +1 ≤ 32 p which implies that
sv 0
1− 3
n1v0 +1 2p
≤1+ ≤ 1 + 6p
1 − n1s+1
v
1 − 32 p
v

for p < 1/2. t

u

We now state a condition on p that ensures S is a good sample with high

probability.
 log( 1−α
1
)
Lemma 2. If the sampling frequency p < k
4t log( α )
, the probability that a good
2
sample is drawn is at least (1 − α) .
Proof. We observe that given a fixed table T , the number of rows in S with
0
value u is independent of the number of rows in S with any other value
q u.
For a common value v, the probability that S has more than nv p+ 3nv p log( αk )
rows with value v is at most
k α
e−3 log( α )/3 =
k
using Chernoff Bounds.
For an infrequent value v, the probability that S has more than nv p+2 log( αk )
rows with value v is at most
k α
e−2 log( α )/2 =
k
Since there are k values altogether, the total probability that the sample has the
requisite number of common and infrequent values is at least 1 − k · αk = 1 − α.
The probability that a rare value v does not occur in S is (1 − p)nv . If there
are at most t rare values, then the probability that none of these values occur in
1
k k log( )
S is at least (1 − p)2t log( α )/ ≥ e−4pt log( α )/ . For p <  4t log(
1−α
k , this probability
α)
is at least 1 − α.
The total probability of seeing a good sample is therefore at least (1 − α)2 .
t
u
Finally, we present an example to show that the upper bound on p is tight
up to a log( αk ) factor.

Observation 6 There exists a table T for which a sampling frequency p <

1
 log( 1−α )
t violates (1, 2 , α)-privacy. Here t + 1 is the number of values with fre-
quency at most 1 .

We illustrate this through an example. Consider a table T with t + 2 dis-

tinct values; values 1, 2, . . . , t each occur in 1 rows, value t + 1 occurs in all the
remaining rows except for one row, and value t + 2 occurs in row i.
Consider a sample S drawn from this table with the property that su > 0
for some u ∈ [1, . . . , t]. Consider an attacker who knows the value of all rows of
the table except for row i and is trying to find out what the value of row i is. If
Pr[S|T ]
st+2 > 0, Pr[S|T{i→u} ] = 0 for any u other than value t + 2, and Pr[S|T{i→t+2} {i→u} ]
is unbounded.
Otherwise, st+2 = 0. Let u be a value in [1, . . . , t] for which su > 0. If nv is
the number of rows with value v in the table T \ {i},
nu nt+2 +1



Pr[S|T{i→t+2} ] su st+2 su
= nu +1
nt+2
= 1 −
Pr[S|T{i→u} ] s s
n u+1
u t+2

Since su ≥ 1 and nu = this quantity is at most 1− 2 for any  < 1. In other

1
,
words, if we see a sample S with the property mentioned above, (1, /2)-privacy
is violated.
 Now the probability of choosing a sample S with this property is (1 − (1 −
1
t pt  log( 1−α )
p) ) ≥ 1 − e−  . If p >

t , this probability is more than α. This means
1
 log( 1−α )
that we need a sampling frequency p < t to ensure (1, 2 , α)-privacy.

5 (c, , δ)-privacy

The techniques of [5] show that a mechanism which is (1, c , δc )-private is also
(c, , δ)-private. The proof looks at a sequence of intermediate tables, each of
which differs from the previous one by one row, and shows that (1, c , δc )-privacy
for each of these tables implies (c, , δ)-privacy for the original table. It is not
apparent that the proof applies to us : we do not guarantee (1, , δ)-privacy for all
tables for a uniform value of p, so a sampling frequency that is (1, , δ)-private for
the starting table may not maintain the same , δ guarantees for an intermediate
one. In this section, we show an upper bound on the sampling frequency p so
that (c, , δ)-privacy is ensured. Our guarantees are better than the guarantees
in [5] in terms of δ and slightly worse in terms of .
As in the previous section, given , δ, a table T and k, the total number of
distinct values in the table and c, we provide a sampling frequency p that is
(c, , δ)-private. Our main guarantees can be summarized as follows.

1
Theorem 7 Given a table T , let α = 2 δ, k be the number of distinct values
2 log( k )
in T and t be the total number
  of values in  T that
 occur less than  
α
+c
times. Also let 0 = max 6c 1 + 2 log(
c
k
)
p, 2c 1 + c
2 log( k )
(p + ) and let
α α
c 1
(1 + k )(p
2 log( α )
+ ) < 2. Then a sample S of T drawn with frequency p <
 log( 1−α
1
)
k
4t log( α )(1+ c
)
is (c, 0 , δ)-private for t > 0. When t = 0, a sample S of T
2 log( k )
α
drawn with frequency p ≤  is (c, 0 , δ)-private.

c 1
We need the assumption (1 + k )(p + )
2 log( α )
< 2 to make sure p is bounded
away from 1 by a constant and also  is small compared to c. (Any other constant
than 12 would do, but would change the constants in Theorem 7. ) If p is too
close to 1 or if c is too big, all rows containing a rare value may appear in the
sample, leading to a serious breach of privacy.
Comparing these guarantees with those in Section 4, we observe that for a
table T , a sampling frequency p that is (1, c(1+  c ) , δ)-private is also (c, , δ)-
2 log( k )
α
private. We therefore do better than the kind of bound given in [5] in terms of
δ and a little worse in terms of .
Consider all sets of n − c rows in table T and let ncv be the minimum number
of rows with value v in any such set. In this section, we call a value v a rare value
k k
2 log( α ) 12 log( α )
if ncv <  . A common value v has ncv > p , where p is the sampling
frequency. A value that is neither rare nor common is called an infrequent value.
 Just as in the previous section, we show that privacy is preserved when
we draw a sample with certain properties. We call a sample possessing these
properties a good sample, with the same definition as in Section 4.
In Lemma 3, we show that releasing a good sample preserves privacy. Because
the definition of rare and infrequent values have changed, the fact that a good
sample occurs with high probability does not automatically follow from Lemma
2. Instead in Lemma 4, we show that a good sample occurs with high probability.
Combining Lemmas 3 and 4, we get a proof of Theorem 7.
Lemma 3. Let S be a good sample drawn from table T . Then for any set of c
rows Pi and any pair of states V and V 0 ,
Pr[S|T{Pi →V } ]
≤ 1 + 0
Pr[S|T{Pi →V 0 } ]
     
where 0 = max 6c 1 + 2 log(
c
k
)
p, 2c 1 + c
2 log( k )
(p + ) , assuming that (1+
α α
c
k )(p
2 log( α )
+ ) < 21 .
Proof. Without loss of generality, we assume that the state V has c rows with
value v and no rows with value V 0 and the state v 0 has no rows with value v
and c rows with value v 0 . The proofs go through when this assumption does not
hold, and so we simplify the notation accordingly.
For any value u, let ncu denote the number of rows in T \{Pi } with value u, and
let su be the number of rows with value u in the sample S. Note that T{Pi →V }
has ncv + c rows with value v and ncv0 rows with value v 0 , whereas T{Pi →V 0 } has
ncv0 + c rows with value v 0 and ncv rows with value v.
We now show that since S is a good sample, sv < ncv + 1. If the set of rows
Pi in T includes no row with value v, this holds trivially; otherwise, we claim
that at most ncv rows of T that take value v appear in S. Note that T can have
at most ncv + c rows with value v.
If v is a rare value, there are no rows with value v in a good sample. If
v is an infrequent value, the maximum number of rows with value v in the
sample is at most (ncv + c)p + 2 log( αk ) which is at most ncv (1 + ncc )(p + ) <
v
c c 1
ncv (1 + 2 log( c
k )(p + ) < nv for (1 + k )(p + ) < 2 . If v is a common value,
α) 2 log( α )
the maximum number of rows with value v in the good sample S is at most !
q r
k
c k c 3 log( )
(nv + c)p + 3(ncv + c)p log( α ), which is at most (nv + c)p 1 + (nc +c)p ≤ α
v

3 c c c 1
2 nv (1
+ k )p
2 log( α )
< ncv + 1 when (1 + k )p
2 log( α )
< 2.
Therefore,
ncv +c ncv0



Pr[S|T{Pi →V } ] sv sv 0 1
= ncv ncv0 +c ≤ sv sv sv
(1 − )(1 − ) . . . (1 −



Pr[S|T{Pi →V 0 } ] sv sv 0 ncv +1 ncv +2 ncv +c )

For a rare value v, sv = 0. Therefore,

1
sv sv sv ≤1
(1 − ncv +1 )(1 − ncv +2 ) . . . (1 − ncv +c )
 Note that for any value v, ncv ≤ nv ≤ ncv + c. For an infrequent value v,
2 log( k )
sv ≤ (ncv + c)p + 2 log( αk ) and nv ≥ ncv ≥ 
α
. This implies that ncs+1 v
≤
v
c c c
(1 + nc )(p + ) ≤ (1 + 2 log( k ) )(p + ). Assuming (1 + 2 log( k ) )(p + ) < 1/2,
v α α

!
1 c
sv sv sv ≤ 1 + 2c 1 + (p + )
(1 − nc +1 )(1 − nc +2 ) . . . (1 − nc +c )
v v v
2 log( αk )
c
Because v is not a rare value, this quantity is at most 1+2c(1+ 2 log( k )(p+).
q α)

For a common value v, sv is at most (ncv + c)p + 3(ncv + c)p log( αk ), and
sv
ncv p ≥ 12 log( αk ). Therefore ncv +1 ≤ 32 (1 + c
ncv )p ≤ 32 (1 + c
k )p.
2 log( α )
This implies that
!
1 c
≤1+6 1+ pc
(1 − ncs+1
v
)(1 − ncs+2
v
) . . . (1 − ncsv+c ) 2 log( αk )
v v v

c
for p(1 + k )
2 log( α )
< 1/2. t
u

 log( 1−α
1
)
Lemma 4. If the sampling frequency p < k
4t log( α )(1+ c
)
, the probability that
2 log( k )
α
a good sample is drawn is at least (1 − α)2 .

Proof. Following exactly the same argument as in Lemma 2, the probability that
the number of common and infrequent values lie within the requisite bounds is
at least 1 − α.
The probability that a rare value v does not occur in S is (1 − p)nv . Now
2 log( k )
there are at most c + 
α
rows with a rare value v. If there are at most
t rare values, then the probability that none of these values occur in S is at
1
k k log( )
least (1 − p)2t log( α )/+tc ≥ e−4pt(2 log( α )/+c) . For p <  4t log( k )(1+
1−α
c
)
, this
α 2 log( k )
α
probability is at least 1 − α.
The total probability of seeing a good sample is therefore at least (1 − α)2 .
t
u

6 Future Work
There are many avenues for future work. Our work assumes that the random
sample is published in unperturbed form. But it is quite possible that one can
draw larger random samples if noise is added to the sample. Such a technique
may be useful when k is large. One would have to also understand what impact
such noise would have on utility.
Another direction for future research is the study of data streams where
individual data points arrive in sequential, not necessarily random order and the
question is how to maintain a random sample of the stream without breaching
privacy. In this context, the attacker may know who the next person is in the
stream, but not know their private values. Existing techniques for maintaining
random samples over a stream such as reservoir sampling [13] violate privacy
since the sample only changes to include a new person’s value when that person
arrives.
Finally, in practice, prior to sampling, organizations typically employ other
anonymization procedures including, for example, top-coding, where individuals
with values above a certain percentage of the distribution are placed into a
single category, geographic population thresholds, where individuals that live in
a geographic unit below a specified population level are not disclosed, random
rounding, wherein numbers that are not multiples of say 10 are randomly rounded
to one of the two nearest multiples. Analysis of the privacy/utility of these multi-
step anonymization procedures that precede sampling would be an interesting
direction for future work.

7 Acknowledgements

We are very grateful to Kobbi Nissim for extensive discussions. We thank Cyn-
thia Dwork for her insights and Amit Agarwal for early discussion. We thank
Shankar Bhamidi for useful suggestions. Finally, we thank the anonymous re-
viewers for their many thoughtful suggestions.

References
1. A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the sulq
framework. In PODS, pages 128–138, 2005.
2. U.S. Census Bureau. Public use microdata sample (pums). In
[Link] 2003.
3. S. Chawla, C. Dwork, F. McSherry, A. Smith, and H. Wee. Toward privacy in
public databases. In Theory of Cryptography Conference, pages 363–385, 2005.
4. I. Dinur and K. Nissim. Revealing information while preserving privacy. In PODS,
pages 202–210, 2003.
5. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity
in private data analysis. In Theory of Cryptography Conference, pages 265–284,
2006.
6. C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned
databases. In CRYPTO, pages 528–544, 2004.
7. A. Evfimievski, J. Gehrke, and R. Srikant. Limiting privacy breaches in privacy
preserving data mining. In PODS, pages 211–222, 2003.
8. O. Goldreich. Foundations of Cryptography, Volumes I and II. Cambridge Univer-
sity Press, 2004.
9. K. Kenthapadi, N. Mishra, and K. Nissim. Simulatable auditing. In PODS, pages
118–127, 2005.
10. N. Mishra and M. Sandler. Privacy via pseudorandom sketches. In PODS, 2006.
11. Social Security Administration: Office of Policy Data. Benefits and earnings public-
use file. In [Link] 2004.
12. L. Sweeney. Guaranteeing anonymity when sharing medical data, the datafly sys-
tem. In Proceedings AMIA Annual Fall Symposium, 1997.
13. J. Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical
Software, 11(1):37–57, March 1985.