Privacy Implications of Shuffling
Authors: Casey Meehan
Amrita Roy Chowdhury
Kamalika Chaudhuri
Somesh Jha
Venue: ICLR 2022 Poster (2022)
Keywords: local differential privacy
shuffle DP model

Abstract: \ldp deployments are vulnerable to inference attacks as an adversary can link the noisy responses to their identity and subsequently, auxiliary information using the \textit{order} of the data. An alternative model, shuffle \textsf{DP}, prevents this by shuffling the noisy responses uniformly at random.  However, this limits the data learnability -- only symmetric functions (input order agnostic) can be learned. In this paper, we strike a balance and show that systematic shuffling of the noisy responses can thwart specific inference attacks while retaining some meaningful data learnability. To this end, we propose a novel privacy guarantee, \name-privacy, that captures the privacy of the order of a data sequence. \name-privacy allows tuning the granularity at which the ordinal information is maintained, which formalizes the degree the resistance to inference attacks trading it off with data learnability.  Additionally, we propose a novel shuffling mechanism that can achieve \name-privacy and demonstrate the practicality of our mechanism via evaluation on real-world datasets. 

Published as a conference paper at ICLR 2022
PRIVACY IMPLICATIONS OF SHUFFLING
Casey Meehan Amrita Roy-Chowdhury 2, Kamalika Chaudhuri ' Somesh Jha" 2
UC Diego, University of Wisconsin, Madison
ABSTRACT
LDP deployments are vulnerable inference attacks as adversary can link the noisy responses to their identity and subsequently, auxiliary information using the order of the data. An alternative model, shuffle DP, prevents this by shuffling the noisy responses uniformly at random. However, this limits the data learnability only symmetric functions (input order agnostic) can be learned. In this paper, we strike balance and show that systematic shuffling of the noisy responses can thwart specific inference attacks while retaining some meaningful data learnability. To this end, we propose novel privacy guarantee, -l-privacy, that captures the privacy of the order of a data sequence. dr-pviaccy allows tuning the granularity at which the ordinal information is maintained, which formalizes the degree the resistance to inference attacks trading off with data learnability. Additionally, we propose a novel shuffling mechanism that can achieve dr dirppiiacy and demonstrate the practicality of our mechanism via evaluation on woal-world datasets.
INTRODUCTION
Differential Privacy (DP) and its local variant (LDP) are the most commonly accepted notions of data privacy. LDP has the significant advantage of not requiring a trusted centralized aggregator, and has become popular model for commercial deployments, such as those of Microsoft (Ding) jet al. 2017). Apple (Greenberg] 2016). and Google (Erlingsson et al.] (2044) Fanti et al. 2015 Bittau al. 2017b). Its formal guarantee asserts that an adversary cannot infer the value of an individual's private input by observing the noisy output. However in practice, a vast amount of public auxiliary information, such as address, social media connections, court records, property records, income and birth dates (La Corte 2019), is available for every individual. An adversary, with access to such auxiliary information, can learn about an individual's private data from several other participants' noisy responses. We illustrate this as follows.
Problem. An analyst runs a medical survey in Alice's community to investigate how the prevalence of a highly contagious disease changes from neighborhood to neighborhood. Community members report binary value indicating whether they have the disease.
Next, consider the following two data reporting strategies.
Strategy 1. Each data owner passes their data through an appropriate randomizer (that flips the input bit with some probability) in their local devices and reports the noisy output to the untrusted data analyst.
Strategy
The noisy responses from the local devices of each of the data owners are collected by an intermediary trusted shuffler which dissociates the device IDs (metadata) from the responses and uniformly randomly shuffles them before sending them to the analyst.
Strategy 1 corresponds to the standard LDP deployment model (for example, Apple and Microsoft's deployments). Here the order of the noisy responses is informative of the identity of the data owners the noisy response at index 1 corresponds to the first data owner and so on. Thus, the noisy responses can be directly linked with its associated device/account ID and subsequently. auxiliary information. This puts Alice's 's data under the threat of inference attacks. For instance, an adversary may know the home addresses of the participants and use this to identify the responses of all the individuals from Alice's household. Being highly infectious, all or most of them will have the same true value (0 or 1). Hence, the adversary can reliably infer Alice's 's value by taking simple majority vote of her and her household's 's noisy responses. Note that this does not violate the LDP guarantee since the inputs are appropriately randomized when observed in isolation. Additionally, on account of being
TTee analyst and the adversary could be same, we refer them separately for the ease of understanding.

---

Published as a conference paper at ICLR 2022
(b) LDP
(c) Our scheme: To
(d) Our scheme: Tb
(c) Uniform shuffle
(a) Original Data
(f) Attack: LDP
(g) Attack: na
(h) Attack: T6
(i) Attack: unif. shuff.
Figure 1: Demonstration of how our proposed scheme thwarts inference attacks different granularities. Fig. [epepicts the original sensitive data (such as income bracket) with eight color-coded labels. The position of the points represents public information (such as home address) used to correlate them. There are three levels of granularity: warm vs. cool clusters, blue vs. green and red vs. orange crescents, and light vs. dark within each crescent. Fig. Tb depicts
2.55 LDP. Fig. Ic and I correspond to our scheme, each with 1 (privacy parameter, Det. 4.3 The former uses a smaller distance threshold (r1, used to delineate the granularity of grouping - see Sec. (.2) that mostly shuffles each crescent. The latter uses a larger distance threshold (r2) that shuffles within each cluster. Figures in the bottom row demonstrate an inference attack (uses Gaussian process correlation) on all four cases. We see that LDP reveals almost the entire dataset (Fig. Ii while uniform shuflling prevents all classification [T).. However, the granularity can be controlled with our scheme (Figs. Th..
public, the auxiliary information is known to the adversary (and analyst) a priori - no mechanism can prevent their disclosure. For instance, any attempts to include Alice's s address as an additional feature of the data and then report via LDP is furile - the adversary would simply discard the reported noisy address and use the auxiliary information about the exact addresses identify the responses of her household members. We call such threats inference attacks recovering an individual's 's private input using all subset of other participants' noisy responses. It is well known that protecting against inference attacks that rely on underlying data correlations is heyond the purview of DP (Kifer & Machanavajhall 2014 Tschantz et al. 2020).
Strategy 2 corresponds to the recently introduced shuffle DP model, such as Google's Prochlo (Bittau al. 20176). Here, the noisy responses are completely anonymized the adversary cannot identify which LDP responses correspond to Alice and her household. Under such a model, only information that completely order agnostic (i.e., symmetric functions that can be computed over just the bag of values, such as aggregate statistics) can be extracted. Consequently, the analyst also fails to accomplish their original goal as all the underlying data correlation destroyed.
Thus, we see that the two models of deployment for LDP present trade-off between vulnerability to inference attacks and scope of data learnability. In fact, as demonstrated in Kifer & MachanavaiJhala (201T), it is impossible to defend against all inference attacks while simultaneously maintaining utility for learning. In the extreme case that the adversary knows everyone in Alice's s community has the same true value (but not which one), mechanism can prevent revelation of Alice's 's datapoint short of destroying all utility of the dataset. This then begs the question: Can we formally suppress specific inference attacks targeting each data owner while maintaining same meaningful learnability of the private data? Referring back to our example, can we thwart attacks inferring Alice's s data using specifically her houscholds' responses and still allow the medical analyst learn its target trends? Can we offer this to every data owner participating?
In this paper, we strike balance and propose generalized shuffle framework that meets the utility requirements of the above analyst while formally protecting data owners against inference attacks. Our solution is based on the key insight: the order of the data acts as the proxy for the identity of data owners as illustrated above. The granularity at which the ordering is maintained formalizes resistance to inference attacks while retaining some meaningful learnability of the private data. Specifically, we guarantee each data owner that their data is shuffled together with a carefully chosen group of other data owners. Revisiting our example, consider uniformly shufffing the responses from Alice's household and her immediate neighbors. Now adversary cannot use her household's 's responses to predict her value any better than they could with a random sample of responses from this group. In the same way that LDP prevents reconstruction of her datapoint using specifically her noisy response. this scheme prevents reconstruction of her datapoint using specifically her households' responses. The real challenge is offering such guarantees equally every data owner. Bob, Alice's
2

---

Published as a conference paper at ICLR 2022
neighbor, needs his households' responses shuffled in with his neighbors, as does Luis who is neighbor of Bob but not of Alice. Thus, we have n data owners with n distinct, overlapping groups. Our scheme supports arbitrary groupings (overlapping or not), introducing a diverse and tunable class of privacy/utility trade-offs which is not attainable with either LDP or uniform shuffling alone. For the above example, our scheme can formally protect each data owner from inference attacks using specifically their household, while still learning how disease prevalence changes across the neighborhoods of Alice's 's community.
This work offers two key contributions to the machine learning privacy literature:
Novel privacy guarantee. We propose a novel privacy definition, d de-privacy that captures the privacy of the order of data sequence (Sec. 4.2) and formalizes the degree of resistance against inference attacks (Sec. 4.3). do -privacy allows assigning an arbitrary group, G., to each data owner, DO,, E [n]. For instance, the groups can represent individuals in the same age bracket, 'friends' on social media, or individuals living in each other's 's vicinity (as in case of Alice in our example). Recall that the order is informative of the data owner's 's identity. Intuitively, d -p-privacy protects DO; from inference attacks that arise from knowing the identity of the members of their group G; (Sec. 4.3) Additionally, this grouping determines threshold of learnability any learning that is order agnostic within a group (disease prevalence in a neighborhood the data analyst's 's goal in our example) is utilitarian and allowed; whereas analysis that involves identifying the values of individuals within a group (disease prevalence within specific households - the adversary's goal) is regarded as a privacy threat and protected against. See Fig. for toy demonstration of how our guarantee allows laning the granularity al which trendy can be learned.
Novel shuffle framework. We propose novel mechanism that shuffles the data systematically and achieves dp-privacy. This provides a generalized shuffle framework that interpolates between no shuffling (LDP) and uniform random shuffling (shuffle model) in terms of protection against inference attacks and data learnability.
2 RELATED WORK
The shuffle model of DP (Bittau et al. 2017a Cheu et al. 2019 Erlingsson et al. 2019) differs from our scheme as follows. These works (1) study DP benefits of shuftling whereas we study the inferential privacy benefits, and (2) only study uniformly random shuffling where ours generalizes this to tunable, non-uniform shuffling (see App. A.15)..
steady line of work has studied inferential privacy (Kasiviswanathan Smith 2014 Kifer
Machanavaijhala 2011 Ghosh & Kleinherg, 2016, Dalenius 1977 Dwork & Naor 2010: T Tschantz
et 2020). Our work departs from those in that we focus on local inferential privacy and so via the new angle of shufiling.
Older works such as k-anonymity (Sweeney) 2002). (-diversity Machanavajjhala et al. (2007).
Anatomy (iiao & Taol (006) and others (Wong al. 2010 Tassa et al. [012]] Xue et al. 2012
Choromanski et al.] 20.3) [2013]Doka Doka et al. (015)) have studied the privacy risk of non-sensitive auxiliary information or "quasi identifiers'. These works (1) focus on the setting of dataset release, whereas
we focus on dataset collection, and (2) do not offer each data owner formal inferential guarantees, whereas do. The De Finetti attack (Kifer 2009) shows how shuffling schemes are vulnerable to inference attacks that correlate records to recover the original permutation of sensitive attributes. A strict instance of our privacy guarantee can thwart such attacks (at the cost of no utility, App. A.3)
3
BACKGROUND
Notations. Boldface (such as x = (ri,,... .xn) denotes a data sequence (ordered list); normal font (such 21) denotes individual values and {.} represents a multiset or bag of values.
3.1
LOCAL. DIFFERENTIAL. PRIVACY
The local model consists of set of data owners and an untrusted data aggregator (analyst); each individual perturbs their data using a LDP algorithm (randomizers) and sends it to the analyst. The LDP guarantee is formally defined as Definition 3.1. [Local Differennial Privacy, LDP Warner (1955); Evfimievski et al. (2003); Ka- siviswanathan al. [2008)] A randomized algorithm M : d is c-locally differentially private (or c-LDP) ), if for any pair of private values x; x' E X and any subset of output,
Pr[M(z)+ W] < et Pr[M(z'
W]
(I)
The shuffle model is an extension of the local model where the data owners first randomize their inputs. Additionally, intermediate trusted shuffler applies uniformly random permutation to
3

---

Published as a conference paper at ICLR 2022
all the noisy responses before the analyst can view them. The anonymity provided by the shuffler requires less noise than the local model for achieving the same privacy.
3.2 MALLOWS MODEL
A permutation of set S is a bijection S + S. The set of permutations of [n], N forms symmetric group Sn- As a shorthand, we use (xx) to denote applying permutation o E S, to a data sequence x of length n. Additionally, o E [m].o o E S, denotes the value at index in and 0 denotes its inverse. For example, if a = (1 3
5 2) and x (21, 33, 45, 65, 67), then
oxx) = (21, 45, 67, 65, 33), (2) = 3, = and Mallows model is popular probabilistic model for permutations (AALOWS 1957). The mode of the distribution is given by the reference permutation og - the probability of a permutation increases as we move 'closer' to on as measured by rank distance metrics, such as the Kendall's 's tau distance (Def. A.2). The dispersion parameter 8 controls how fast this increase happens.
(1 5 243).
Definition 3.2. For a dispersion parameter 8, a reference permutation d, E S.., and a rank distance measure ó Sp x Sn + IR, Pe, : oo) = (0,55)
-0d(r,00) is the Mallows model where (00 8)
Eoes.. e -(D(a,00) is a normalization term and a E S..
e-U + & pehioee
4 DATA PRIVACY AND SHUFFLING
D0:
In this section, we present d. -privacy and shuffling mech- anism capable of achieving the -prrvvacc guarantee.
D0:
00.
4.1 PROBLEM SETTING
Data
Trusted Shuller
Untrasted Aggrepater (Amiget)
In our problem setting, have n data owners i E [n] each with private input 2, E X' (Fig. 2h. The data owners first randomize their inputs via a cDLDP mechanism to generate y; -Mxx). Additionally,
Figure 2:
Trusted shuffler mediates on y
just like in the shuffle model, we have a trusted shuffler. It mediates upon the noisy responses
y (y1,- ........ : yn? to obtain the final output sequence z = A(y) (AA corresponds to Alg. which is
sent to the untrusted data analyst. The shuffler can be implemented via trusted execution environments (TEE) just like Google's ' Prochlo. Next, we formally discuss the notion of order and its implications.
Definition 4.1. (Order) The order of sequence values } and is represented by permutations from Sn-
(x ( refers to the indices of its set of
yn.) is represented by the identity permutation 0, = (1 2 n),, the value at index corresponds to DO, and so on. Standard LDP releases the identity permutation w.p. 1. The output of the shuffler, is some permutation of the sequence y, i.e.,
When the noisy response sequence y (y......
z = ayy) = (Wa(1), .Ho(n))
where a is determined via A(-). For example, for a = (4 23 1), we have z = (y4. ys U2. Vs. 31) which means that the value at index 1 (DO,) now corresponds to that of DO and so on.
4.2 DEFINITION OF PP-PRIVACY
Inferential risk captures the threat of an adversary who infers DO,'s 's private x; using all or a subset of other data owners' released y₁ s. Since we cannot prevent all such attacks and maintain utility, our aim is to formally limit which data owners can be leveraged in inferring DO,'s 's private ry To make this precise, each DO, may choose corresponding group, G2 C In), of data owners. d, d--privacy guarantees that yj values originating from a data owner's group G are shuffled together. In doing so, the LDP values corre- sponding to subsets of DO,'s group T C G; cannot be reliably identi- fied, and thus cannot be singled out make inferences about DO,'s T;, If Alice's group includes her whole neighborhood, LDP data originating from her household cannot be singled out recover her private Z,,
Figure 3: An example social me- dia connectivity graph ba.g
Any choice of grouping G = [G1, G G.,) can be accommodated under d do-priiacy. Each data owner may choose group large enough to hide anyone they feel sufficient risk from. We outline two systematic approaches to assigning groups as follows:
Let t = (t1,--. tt),t, 4 T denote some public auxiliary information about each individual. DO,'s 's group, G, could consist of all those DO,'s 's who are similar to DO, w.r.t. the public auxiliary information 4;, Lj according some distance measure d: T T R. Here, we define
4

---

Published as a conference paper at ICLR 2022
'similar' being under threshold r E R such that = E [nl]d(t,, S rr) example, d(-) can be Euclidean distance if T corresponds to geographical locations, thwarting inference attacks leveraging one's household or immediate neighbors. If represents a social media connectivity graph, d(-) can measure the path length between two nodes, thwarting inference attacks using specifically one's close friends. For the example social media connectivity graph depicted in Fig. 3 assuming distance metric path length and r 2, the groups are defined as G1 = (1. 7,8, 5, 6,, G2 = (2, 1, 7,75 5, 6, 3} and so on.
[n]. For
Alternatively, the data owners might opt for group of a specific size r < Collecting private data from a social media network, we may set r = 50, where each G; is encouraged to include the 50 data owners DO; interacts with most frequently.
Intuitively, d. privacy protects DO; against inference attacks that leverages correlations at a finer granularity than Gg, other words, under d, dp-privacy, one subset of data owners C G. (e.g. household) is no more useful for targeting z; than any other subset of l data owners C G. (e.g. some combination of neighbors). This leads to the following key insight for the formal privacy definition.
Key Insight. Formally, our privacy goal is to prevent the leakage of ordinal information from within a group. We achieve this by systematically bounding the dependence of the mechanism's output on the relative ordering (of data values corresponding to the data owners) within each group. First, we introduce the notion of neighboring permutations.
Definition 4.2. (Neighboring Permutations) Given a group assignment G. two permutations of E Spp are defined to be neighboring w.r.t. a group G; E g (denoted as o=a, ) if (ūi) = o'(i) G,. Neighboring permutations differ only in the indices of its corresponding group G,. For example, a = (124576 193 and o' = (73 6 1 10 9) are neighboring w.r.t G₁ (Fig. (3) since they differ only in a (2), (5)), (6), a (7) and (8)) We denote the set of all neighboring permutations
Ng = {a, o') o' RG, o', 3G, E gg} Now, we formally detine d, -prvaccy as follows.
Definition 4.3 (de-privacy) For a given group assignment G on a set of n entities and a privacy parameter E 12 a randomized mechanism A : ym + V is (a, G)-da private if for all y e y and neighboring permutations a, a, E Ng and any subset of output 0 C V, we have
Pr[A(a(y)) E O PPrAAoo(( (y)) O]
(y) and o'y) are defined to be neighboring sequences.
do -privacy states that, for any group G., the mechanism is (almost) agnostic of the order of the data within the group. Even after observing the output, an adversary cannot learn about the relative ordering of the data within any group. Thus, two neighboring sequences are indistinguishable to an adversary. An important property of de-privacy is that post-processing computations does not degrade privacy. Additionally, when applied multiple times, the privacy guarantee degrades gracefully. Both the properties are analogous to DP and presented in App. A.4
In) can be viewed as a two-tuple. (fz),a), where {x} denotes the bag of values and E Sn, denotes the corresponding indices of the values which represents the order of the data. The e-LDP protects the bag of data values, {z}, while d ---rrivacy protects the order, σ. Thus, the two privacy guarantees cater to orthogonal parts of a data sequence (see Thm. 4.2) ). Also, = co (0), 0 (n) represents the standard LDP (shuffle DP) setting.
Note. Any data sequence x = (II, (Z1,"..,,z))
4.3
PRIVACY IMPLICATIONS
The group assignment G delineates a threshold of learnability which determines the privacy/utility tradeoff as follows.
Learning allowed (Analyst's goal). d, d--privacy can answer queries that are order agnostic within groups, such as aggregate statistics of group. In Alice's case, the analyst can estimate the disease prevalence in her neighborhood.
Learning disallowed (Adversary's goal). Adversaries cannot identify (noisy) values of individu- als within any group. While they may learn the disease prevalence in Alice's 's neighborhood, they cannot determine the prevalence within her household and use that to recover her value I;.
To make this precise, we first formalize the privacy implications of the d,, guarantee in the standard Bayesian framework, typically used for studying inferential privacy. Next, we formalize the privacy provided by the combination of LDP and d, guarantees by way of decision theoretic adversary.
We could also have different thresholds, Ts, for every data owner, DO,-
5

---

Published as a conference paper at ICLR 2022
Bayesian Adversary. Consider Bayesian adversary with any prior P the joint distribution of noisy responses, Pro(y]: which models their beliefs on the correlation between the participants (such as the correlation between Alice and her households' discase status). Their goal is to infer DO,'s 's private input æ;. As with early DP works (Dwork et al. (006). we consider an informed adversary. Here, the adversary knows (1) the sequence (assignment) of noisy values outside Gi, Yo,- and (2) the (unordered) bag of noisy values in G, {yG. J. do de-privacy bounds the prior-posterior odds gap on T for such as informed adversary as follows:
Theorem 4.1. For given group assignment G on set of n data owners. if a shuffling mechanism A y y" is (ax, 9) -)ddpiivaee,, then for each data owner DO;, i E [n],
Prp = alz, {UG, ). N.G. - -log Prp [4 = bl Lya.).
Prp [ al Kuc, V..
max
log Prp(z: = blz, (yG, V..
aa
iEIn
a.EE.
for a prior distribution P, where z = A(y) and YG. the noisy sequence for data owners outside G.,
See Apple A.5 for the proof and further discussion on the semantic meaning of the above guarantee.
Decision Theoretic Adversary. Here, we analyse the privacy provided by the combination of LDP and de guarantees. Consider a decision theoretic adversary who aims to identify the noisy responses, }2r]. that originated from a specific subset of data owners, I C G2 (such as the members of Alice's household). We denote the adversary by a (possibly randomized) function mapping from the output sequence to set of l indices, DAde 3)mh + [n|]*. where & = 17|. These & indices, H E [m]*, represent the elements of z that Dade believes originated from the data owners in I. DAde wins if > k/2 of the chosen indices indeed originated from 1, i.e. |or (H) l7] /| > k/2, where 2 = = and o (H) = {a(i)= : E H}. DAde loses if most of H did not originate from I, i.e., (O(H) n 1| S k/2. We choose the above adversary because this re-identification a key step in carrying out inference attacks in failing to reliably re-identify the noisy values originating from J, one cannot make inferences on x, specifically from the subset T C G..
Theorem 4.2. For A(M(x)) = z where M(.) is e-LDP and A(-) is a doprivate, we have k Pr[D Adv loses) 1 Je |e- (2kkcta)) Pr(DAdv wins]
k
for any input subgroup I C G [Gi] and k r/2
The adversary's s ability to re-identify the {2/} values comes partially from the bag of values (quanti- fied by e) and partially from the order (quantified by a). We highlight two implications of this fact.
When is small (< 1), adversary's ability to re-identify the noisy values {2ı} originating from may very well be dominated by a. For instance, if c = 0.2 and k = 5, the adversary's advantage is dominated by for any a > 2. When using LDP alone (no shuffling), a xo and the adversary can exactly recover which values came from Alice's s household. As such, even moderate a value (obtained via dg-privacy) significantly reduces the ability re-identify the values.
When the loss is dominated by e (2ke >> a). the above expression allows us to disentangle the source of privacy loss. In this regime, adversaries get most of their advantage from the bag of values released, not from the order of the release. That is, even if a = 0 (uniform random shuffling), participants still suffer large risk of re-identification simply due to the noisy values being reported. Thus, no shuffling mechanism can prevent re-identification in this regime.
Discussion. In spirit, DP does not guarantee protection against recovering DO,'s private x; value. guarantees that- had user not participated (or equivalently submitted false value a;)) the adversary would have about the same ability to learn their true value, potentially from the responses of other data owners. In other words, the choice to participate unlikely to be responsible for the disclosure of z;. Similarly, d, -piivaay does not prevent disclosure of xi. By requiring indistinguishabiiiy of neighboring permutations, guarantees that had the data owners of any group G3 completely swapped identities the ad adversary would have about the same ability to learn T;. So most likely, Alice's household is not uniquely responsible for a disclosure of her de had her household swapped identities with any of her neighbors, the adversary would probably draw the same conclusion on z; Or, as detailed in Thm
an adversary cannot reliably resolve which {=} values originated from Alice's household, so they cannot draw conclusions based on her household's responses. In nutshell, Inference attacks can recover a data owner DO,'s 's private data I; from the responses of other data owners. The order of the data acts the proxy for the data owner's 's identity which can aid an adversary in corralling the subset of other data owners who correlate with DO, (required to make a reliable inference of 2.:).

---

Published as a conference paper at ICLR 2022
DP alleviates concerns that DO,'s 's choice to share data (4)) will result in disclosure of 2,. and do -privvacy alleviates concerns that DO,'s 's group's 's (G;) choice to share their identity will result in disclosure of z,,
4.4 d. PRIPATE SHUFFLING MECHANISM
Algorithm do do-private Shuffling Mech.
We now describe our novel shuffling mechanism that can achieve dr-piiiy In a nutshell, our mechanism samples a permutation from suitable Mallows model and shuffles the data sequence accordingly. We can characterize the do -rivvccy
Input: LDP sequence y = (UL, Moli Public aux. info. t = (tz,".. ....... t..): Dist. threshold r; Priv. param. a;
Output: z Shuffled output sequence;
guarantee of our mechanism in the same way
g = CropmpaterrouoAssiinnnn
(t, r);
as that of the DP guarantee of classic mecha-
Construct graph G with
nisms (Dwork & Roth 2014) with variance and sensitivity. Intuitively, larger dispersion parameter R (Def. 3.2) reduces randomness over permutations, increasing utility and increas- ing (worsening) the privacy parameter a. The maximum value of 0 for given guarantee depends on the sensitivity of the rank distance measure 5(-) over all neighboring permutations Nç. Formally, we define the sensitivity as
a) vertices V = (1,2, .n)
b) edges E {(1,)) i E G., G. e
root = arg max |Gil:
da (EFS(G,ro00)
A= ComputeSenssttvvtyylln 9)
0 = =/A;
ā F)
A(oo : g) max [b(0)))))) - -((rga', (a.0")EN,
o² = 0o o;
the maximum change in distance 8(-) from the ref- erence permutation dg for any pair of neighboring 10 Return z; permutations o') E Ng permuted by do. The
(Vo (1), "a (n));
privacy parameter of the mechanism is then proportional to its sensitivity 0- A(oo 5,
Given G and a reference permutation do the sensitivity of a rank distance measure 8(.) depends on the width, wg. which measures how, 'spread apart' the members of any group of G are in oo:
WG. (x
max 0 ())
(kk) i E [m]; wg max WG
G.E9
For example, for (137864529 10) and G₁ 2,, 6), w6, = (1) (2)) = 7. The sensitivity is an increasing function of the width. For instance, for Kendall's 7 distance 5z (.) we have A(ao d). = u@ (w0² + 1)/2.
If a reference permutation clusters the members of each group closely together (low width), then the groups are more likely permute within themselves. This has two benefits. First, for the same 0 (0 is an indicator of utility as it determines the dispersion of the sampled permutation), a lower value of width gives lower a (better privacy). Second. if a group is likely shuffle within itself, will have better (n, pr-preservaaiinn a novel utility metric, we propose, for a shuffling mechanism. Intuitively, mechanism is (17, -rppreseg w.r.t a subset of indices S C [n] if at least 17% of its indices are shuffled within itself with probability (1 - 5). The rationale behind this metric is that it captures the utility of the learning allowed by do-privacy - S is equal to some group E G. high (n, preeessrrvnoo allows overall statistics of G to be captured since 17% of the correct data values remain preserved. We present the formal discussion in App. A.7
Unfortunately, minimizing Wß is NP-hard problem (Thm. A.3 App. A.9 Instead, we estimate the optimal dg using the following heuristiq aaproaac based graph breadth first search.
Algorithm Description. Alg. above proceeds as follows. We first compute the group assignment, G. based on the public auxiliary information and desired threshold r following discussion in Sec. (Step 1). Then we construct op with a breadth first search (BFS) graph traversal.
We translate G into undirected graph (V, F.). where the vertices are indices V V= [n] and two indices i.j are connected by an edge if they are both in some group (Step 2). Next, is computed via a breadth first search traversal (Step i) the k-th node in the traversal is i, then (kk)) i The rationale is that neighbors of (members of G.) would be traversed in close succession. Hence, neighboring node j is likely to be traversed at some step near which means |a (i) on GG] = lt k| would be small (resulting in low width). Additionally, starting from the node with the highest degree (Steps 3-4) which corresponds to the largest group G (lower bound for wg for any a)) helps to curtail the maximum width in ag- See App. A. for evaluations of this heuristic's 's approximation.
'The heuristics only affect dg (and utility). Once do fixed, A computed exactly as discussed above.
7

---

Published as a conference paper at ICLR 2022
This is followed by the computation of the dispersion parameter, 0, for our Mallows model (Steps 5-6). Next, we sample a permutation from the Mallows model (Step 7) ā ~ Po(a : o)) and we apply the inverse reference permutation to it, o² og à to obtain the desired permutation for shuffling. Recall that is (most likely) close to on. which is unrelated to the original order of the data. to therefore brings a² back to shuffled version of the original sequence (identity permutation σ7). Note that since Alg. 1 is publicly known, the adversary/analyst knows og. Hence, even in the absence of this step from our algorithm, the adversary/analyst could perform this anyway, Finally, we permute y according to a² and output the result o(y) (Steps 9-10).
Theorem 4.3. Alg. / is (a, ()-d private where a = 0 A 9)
The proof is in App. A.11 Note that Alg. 1 provides the same level of privacy (a) for any two group assignment G, g as long as they have the same sensitivity, i.e, A(oo 9) = A(oo d,,9') This leads to the following theorem which generalizes the privacy guarantee for any group assignment.
Theorem 4.4. Alg. I satisfies (o', ,'') plavvvacyy for any group assignment G' with a' = a (,)))
A.a
(proof in App. (.72
Note. Producing a² is completely data (y) independent. It only requires access to the public auxiliary information Hence, Steps 1 can be performed in a pre-processing phase and do not contribute to the actual running time. See App. A.10 for illustration of Alg, and runtime analysis.
5
EVALUATION
Da Interred
Unil. Shuffi
LDD
(De teeerved
0.15
LDP
0.8
2.7X Improvement over LDP
Schame
0.25
0.30
0.7
Unif, Shuffic Schema
LDP
Erroe
0.6
LDP
0.1
Untt Shuttle
0:15
0.5
20
40
60
80
20
40
60
80
Distance
hhreshold
Uistance d
Group Size
(a) PUDF: Attack
(b) Twitch: Attack
(c) PUDF: Learnability
(d) Twitch: Learnability
Figure 4: Our scheme interpolates between standard LDP (orange line) and uniform shuffling (blue line) in both privacy and data Icarnability. All plots increase group size along x-axis (exeept (d)). (a) (b): The fraction of participants vulnerable to an inferential attack. (c) + (d): The accuracy of calibration model trained on z predicting the distribution of LDP outputs at any point é E T, such as the distribution of medical insurance types used specifically in the Houston area (not possible when uniformly shuffling across Texas).
The previous sections describe how our shuffling framework interpolates between standard LDP and uniform random shuffling. We now experimentally evaluate this asking the following two questions-
Q1. Does the Alg. I mechanism protect against realistic inference attacks? Q2. How well can Alg. tune a model's is ability to learn trends within the shuffled data, i.c., tune data learnability?
We evaluate on four datasets. We are not aware of any prior work that provides comparable local inferential privacy. Hence, we baseline mechanism with the extremes: standard LDP and uniform random shuffling. For concreteness, we detail our procedure with the PUDF dataset (PUD) (license), which comprises n 29k psychiatric patient records from Texas. Each data owner's sensitive value x; is their medical payment method, which is reflective of socioeconomic class (such as medicaid charity). Public auxiliary information /. E T is the hospital's geolocation. Such information is used for understanding how payment methods (and payment amounts) vary from town to town for insurances in practice (Eric Lopez 2020). Uniform shuffling across Texas precludes such analyses. Standard LDP risks inference attacks, since patients attending hospitals in the same neighborhood have similar socioeconomic standing and use similar payment methods, allowing an adversary to correlate their noisy y s. To trade these off, we apply Alg. with d(.) being distance (km) between hospitals, a = 4 and Kendall's 7 rank distance measure for permutations.
Our inference attack predicts DO,'s by taking a majority vote of the zj values of the 25 data owners within r* of t, and who are most similar to DO, w.r.t some additional privileged auxiliary information E E Tp. For PUDF, this includes the 25 data owners who attended hospitals that within r" km of DO,'s hospital, and are most similar in payment amount Py. Using an 2.5 randomized response mechanism, we resample the LDP sequence y 50 times, and apply Alg. I's chosen permutation to
8

---

Published as a conference paper at ICLR 2022
each, producing 50 z's. We then mount the majority vote attack each r; for each z. If the attack on a given ž, is successful across 2 90% of these LDP trials, we mark that data owner as vulnerable although they randomize with LDP, there is 2 90% chance that simple inference attack can recover their true value. We record the fraction of vulnerable data owners as p. We report 1-standard deviation error bars over 10 trials.
Additionally, we evaluate data learnability - how well the underlying statistics of the dataset are preserved across T. For PUDF, this means training a model on the shuffled to predict the distribution of payment methods used near, for instance, 4 = Houston for DO;, For this, we train a calibrated model, Cal: : T + D.. on the shuffled outputs where D₂ is the set of all distributions on the domain of sensitive attributes X. We implement Cal as a gradient boosted decision tree (GBDT) model Friedman ) calibrated with Platt scaling "Niculescu-Mizil & Caruana 2005). For each location 1, we treat the empirical distribution of values within r" as the ground truth distribution at 4,, denoted by Et,,) E Dr. Then, for each 4,, we measure the Total Variation error between the predicted and ground truth distributions (V (t), We then report X(r) - the average TV error for distributions predicted at each & E t normalized by the TV error of naively guessing the uniform distribution at each 4, With standard LDP, this task can be performed relatively well at the risk of inference attacks. With uniformly shuffled data, it is impossible to make geographically localized predictions unless the distribution of payment methods is identical in every Texas locale.
We additionally perform the above experiments on the following three datasets
Twitch (Rozemberezki al. 2019). This dataset, gathered from the Twitch social media platform, includes a graph of R 9K edges (mutual friendships) along with node features. The user's 's history of explicit language is private X' {0, 1). T is user's mutual friendships. i.e. is the i'th row of the graph's 's adjacency matrix. We do not have any Tp here and select the 25 neighbors randomly.
Syn. This is synthetic dataset of size 20K which can be classified at three granularities 8-way, 4-way and 2-way (Fig. salshows a scaled down version of the dataset). The eight color labels are private X = [8]: the 2D-positions are public = IR.2. For learnability, we measure the accuracy of 8-way, 4- 4-w and 2- way GBDT models trained on on an equal sized test set at each r.
Aduli (Dua & Graff 2017). This dataset is derived from the 1994 Census and has = 33K records. Whether DO, 's annual income is 2 50k is considered private, X (2 50k, < 50k). T = 17, 90) is age and Tr is the individual's marriage status. Due to lack of space figures are App. 1.12.2
Experimental Results.
Q1. Our formal guarantee on the inferential privacy loss (Thm. adversary (with access to { J.yc,) )- Here, we test how well does our proposed scheme (Alg. 1) protect against inference attacks on real-world datasets without any such assumptions. Additionally, to make our attack more realistic, the adversary has access to extra privileged auxiliary information
is described w.r.t to a 'strong'
Tp which is not used by Alg. 10 Fig. 4a 4b show that our scheme significantly reduces the attack efficacy. For instance, is reduced by 2.7X at the attack distance threshold r' for PUDF.
Additionally, p for our scheme varies from that of LDFT (minimum
1.0
privacy) to uniform shuffle (maximum privacy) with increasing r (equivalently group size as in Fig. (4b) thereby spanning the entire
Test Test Accuracy
0.8
Car Scain 4wer ana shatts
privacy spectrum. As expected, p decreases with decreasing privacy parameter a (Fig. Sb
0.6
0.4
4d show that À varies from that of LDP (maximum learnability ityy to that of uniform shuffle (minimum learnability) with
Q2. Fig 4c
0.2
10-1
10a
10'
increasing r (equivalently, group size), thereby providing tunability. Interestingly, for Adult our scheme reduces by 1.7.X at the same À as that of LDP for 1 (Fig. Sc) Fig. 5 shows that the distance threshold r defines the granularity at which the data can be classified. LDP allows 8-way classification while uniform shuffling allows none. The granularity of classification can be tuned by our scheme - Ts, T4 and 72 mark the thresholds for 8-way, 4-way and 2-way classifications, respectively.
Distance Threshold
Figure 5: Syw: Learnabllity
6 CONCLUSION
We have proposed new privacy definition, drippiyy that casts new light on the inferential privacy benefits of shuffling and a novel shuffling mechanism to achieve the same.
OOr scheme gives lower p than LDP at 0 because the resulting groups are non-singletons. For instance, for PUDE, G. includes all individuals with the same zipcode DO

---

Published as a conference paper at ICLR 2022
7 ETHIS STATEMENT
is the aim of this paper to formalize the enhanced privacy guarantees offered by shuffling, to provide intuition of what those formal guarantees semantically offer data owners, and to demonstrate an algorithm + experiments which offer these guarantees while meeting analyst utility requirements. We feel that all of these aims well as the public datasets used are ethical.
8 REPRODUCIBILITY STATEMENT
The majority of this paper formalizes a novel perspective on the privacy guarantees achieved by shuffling (i.e. randomizing the order of the data as opposed to the values). Detailed proofs as well as intuitive discussions are provided in the Appendix. All datasets are public. A zip file demonstrating code of each experiment has been uploaded as supplementary material.
REFERENCES
Hospital discharge data public data file. Hospitals/Downlocee shtm
https://www.dshh. tx. Wwt..S.TTHIC.CCC o
Derangement. https://en wwl./enwwiikkk... htt.:/pddd...ooww.//////aaaaaag
Simonetti N. Vazacopoulos A. Balas, E. Job shop scheduling with setup times, deadlines and precedence constraints. J Sched, 11:253-262, 2008. URL
910951-008-0067.
Victor Balcer and Albert Cheu. Separating local shuffled differential privacy via histograms, In ITC, 2020.
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. The privacy blanket of the shuffle model. In Alexandra Boldyreva and Daniele Micciancio (eds.), Advances in Cryptology CRYPTO 2019, pp. 338-667, Cham, 2019. Springer International Publishing. ISBN 978-3-030-26951-7.
R. Bassily, A. Groce, J. Katz, and A. Smith. Coupled-worte worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 439-448, 2013. doi: 10. SOIFFOOS..201..55.
Raghav Bhaskar, Abhishek Bhowmick, Vipul Goyal, Srivatsan Laxman, and Abhradeep Thakurta. Noiseless database privacy. In Dong Hoon Lee and Xiaoyun Wang (eds.), Advances in Cryptology - ASIACRYPT 2011, pp. 215-232, Berlin, Heidelberg, 2.11. Springer Berlin Heidelberg. ISBN 978-3-642-25385-00
Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, llya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP 17, pp. 441-459, New York, NY, USA, 2017a. Association for Computing Machinery. doi: 10.1145/3132747.31
ISBN 458350035
3132747 317.3113222 3132763
Andrea Bittau, Úlfar Erlingsson. Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP '17, pp.
New York, NY, USA, 2017b. ACM. ISBN 978 4500--5085---33 doi:
N0.1145/3132744.33322666
URLhttp::// /oi. acm. www.orggll... 114.0..1111110 3211117777.77 3132763277
Rui Chen, Benjamin C. Fung, Philip S. Yu, and Bipin C. Desai. Correlated network data publication via differential privacy. The VLDB Journal. 23(4) August 2014. ISSN 1066-8888. doi: 10. 1007/500778-013-000
01088-0133300000 0344
Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling, In Yuval Ishai and Vincent Rijmen (eds.), Advances in Cryptology - EUROCRYPT 2019, pp. 375-333-333 Cham, 2019. Springer International Publishing, ISBN 978-3- 030-17653-2.
10

---

Published as a conference paper at ICLR 2022
Krzysztof M Choromanski. Tony Jebara, and Kui Tang. Adaptive anonymity via b-matching. Ad- vances Neural Information Processing Systems, 26:3192-3200 2013.
Tore Dalenius. Towards a methodology for statistical disclosure control. Statistik Tidskrift, 15: 429 129-444, 1977.
Shaleen Deep and Paraschos Koutris. Ranked enumeration of conjunctive query results. In 24th International Conference on Database Theory (ICDT 2021). Schloss Dasstull-Lcibnii-ZZetttu für Informatik, 2021.
Shaleen Deep, Xiao Hu, and Paraschos Koutris. Enumeration algorithms for conjunctive queries with projection. In 24th International Conference on Database Theory (ICDT 2021). Schloss Dagstuhh-LcibnizzZZenttn für Informatik, 2021.
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data pri- vately. In I. Guyon, U. V. Luxburg, S. Bengio, H. Walllah, R. Fergus, S. Vish- wanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems 30, pp. 3571-3580. Curran Associates, Inc., 2017. URL htL:htt::///// //pppr///ppes.../ ciapppers.iips.... caapssccpppper 6948-co co ect ng- eme pri wat.aataaaaaaata..............
Jean-Pate Paul Doignon, Aleksandar Pekeč, and Michel Regenwetter, The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika, 69(1))33-54 March
2004. ISSN 1860-0980. doi: 10. N0.1007/BFO2299888. BFC2295838
Katerina Doka, Mingqiang Xue, Dimitrios Tsoumakos, and Panagiotis Karras, k-anonymization by freeform generalization. In Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, pp. 319-530, 2015.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL
ics. uci, edu/ml
Cynthia Dwork and Moni Naor. On the difficulties of disclosure prevention in statistical databases or the case for differential privacy. January 2010.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., pp. 211-401, August 2014. ISSN 1551-305X.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to
Sensitivity in Private Data Analysis, volume 3876. March 2006. ISBN 978-3-540-
/wwp:/ooooo...ooooooooooooooeooe 32731-8. URL oal.baatcecceeeec.reeetettt..eea cal
Gary Claxton Eric Lopez. Comparing private payer and medicare payment rates for select inpatient hospital services. Kaiser Family Foundation, Jul 2020.
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. CCS, 2014.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pp. 2468-2479, USA, 2019. Society for Industrial and Applied Mathematics.
Alexandre Eyfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the Twenty-secome ACM LIGMOD-SIGACE
SIGART Symposium on Principles of Database Systems, PODS '03, pp. 211-222, New York, NY, USA, 2003. ACM. ISBN --8113-670-4 doi: 10. 00.1145/773153.7731144 URL http:
7/doi acm. 2ttp/1..1145/77115..
Giulia Fanti, Vasyl Pihur, and Úlfar Erlingsson. Building a rappor with the unknown: Privacy- preserving learning of associations and data dictionaries, 2015.

---

Published as a conference paper at ICLR 2022
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling, 2020.
Jerome H Friedman. Greedy function approximation: a gradient boosting machine. Annals of statistics, pp. 1189-1232, 2001.
Johannes Gehrke, Edward Lui, and Rafacl Pass. Towards privacy for social networks: A zero- knowledge based definition of privacy. In Proceedings of the 8th Conference on Theory of Cryptog- raphy, TCC' 11, pp. 432 449, Berlin, Heidelberg, 2011 Springer-Verlag. ISBN 9783642195709.
Johannes Gehrke, Michael Hay, Edward Lui, and Rafael Pass. Crowd-blending privacy. In Reihanch Safavi-Naini and Ran Canetti (eds.)..dvancee Advances in Cryptology CRYPTO 2012, pp. 479-496, Berlin, Heidelherg, 2012. Springer Berlin Heidelherg. ISBN 978-3-642-32000-5.
Joseph Geumlek and Kamalika Chaudhuri. brofile-based privacy for locally private computations. In IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, July 7-12, 2019, pp. 537-541. IEEE, 2019. doi: 10. 00.1099/SSTT2201988444544 URL https:://doot /tg///00...or//
1109/TSTT TtT.//STT..119.... 8889549
Arpita Ghosh and Robert Kleinberg. Inferential privacy guarantees for differentially private mecha- nisms. CoRR, abs/1603.0150S. 2016. URL
Andy Greenberg. Apple's 'differential privacy' is about collecting your data but not your data. Wired, Jun 13 2016.
Krzysztof Grining and Marek Klonowski. Towards extending noiseless privacy: Dependent data and more practical approach. In Proceedings of the 20/7 ACM Asia Conference Computer and Communications Security, ASIA CCS '17, pp. 546-560, New York, NY, USA, 2017. Association
for Computing Machinery. ISBN 9781450349444. doi: 10.1145735529333355292. URL
3052992
Xi He, Ashwin Machanavajjhala, and Bolin Ding. Blowfish privacy: Tuning privacy-utility trade- off's using policies. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD '14, pp. 1447-1458, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 47814303..
doi: 10.1145/2588555.258885 2588888. URL
https::/doi.. org/10 0145/21885551118 000088855552288888 2588581
S. Kasiviswanathan and A. Smith. On the 'semantics" of differential privacy: A bayesian formulation. Priv. Confidentiality, 6, 2014.
S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 531-540, 2008. doi: (09/OOCS.2008.
Yusuke Kawamoto and Takao Murakami. Differentially private obfuscation mechanisms for hiding probability distributions. CoRR, abs/1812.00939, 2018. URL http://arxiv..rgg abs/
1812. 00939
Daniel Kifer. Attacks on privacy and deFinetti's theorem. Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, SIGMOD '09, pp. 127-138. Providence, Rhode Island, USA, June 2009. Association for Computing Machinery. ISBN 978- 778-1-600588551-22 doi:
10.1 (0.1144/15594451555999 /
000445511555888 01455884..00 1559861
Daniel Kifer and Ashwin Machanavajjhala. No free lunch in data privacy. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD 11, pp. 193-204, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 478145030661 doi: 1989345
http:///////........00..100 1ttp://.....11199111 10.1145/1989323.199 1989345. URL /oo. www.oo/ggo...o....
Daniel Kifer and Ashwin Machanavajjbala, Pufferfish: A framework for mathematical privacy
definitions. ACM Trans. Database Syst. 39(1), January 2014. ISSN 0362-5915. doi: 10.1145/
2514689. URL htt.hhttp://ddt org 11tpg//....1111111111
Rachel La Corte. Supreme court: State employee birthdates are public record. https:: /ttpp::/appewss apnews /bc2 2019.
12

---

Published as a conference paper at ICLR 2022
Katrina Ligett, Charlotte Peale, and Omer Reingold. Bounded-Leakage Differential Privacy. In Aaron Roth (ed.), 1st Symposium on Foundations of Responsible Computing (FORC 2020), volume 156 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 10:1-10:20, Dagstubl, Germany, 2020. Schloss Dagstuhi-Leibniz-Zennnne für Informatik. ISBN 978-3-95977-142299 doi: 10. FWW.WIIPIs..FOR..20000 2020/12026
de http:/ahhw..eeeepp/////ooleeeeee
Changchang Liu, Supriyo Chakraborty, and Prateek Mittal. Dependence makes you vulnberable:
Differential privacy under dependent tuples. In NDSS. The Internet Society, 2016. URI. http:
7/dblp. wwwuuuiitiiine tttttrrieee.. de /b/ coo//o//oooooooooooo f ndss/ hdss201g htm # 4LLUMC1 16
Ashwin Machanavajihala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishhan Venkitasubra- maniam. L-diversity: Privacy beyond k-amonymity. ACM Transactions on Knowledge Discovery
from Data, 1(1):3-es, March 2007. ISSN 1556-4681, doi: 10. 1..1445/1217299.2173399 URL
https://doi. wtgp/o..ooooo.o http://66o...o.......1//////3//9 115111117711799911777000
C. MALLOWS, NON-NULL RANKING MODELS. I. Biometrika, -40 06 1957.
ISSN 0006-3444. doi: 10. 10.1093/boocc/4441-.1144 URL httpp:://al..ogg/000...
bi omeom /4tett/44.. /44. 11.11-2.114 114
Alexandru Niculescu-Mizie and Rich Caruana. Predicting good probabilities with supervised learning. In Proceedings of the 22nd international conference on Machine learning, pp. 625-633 2005.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv preprint arXiv:1909.1300 13021, 2019. URL http:://saap.stanffoddeedd///// www.oiiia--eettwrr...... html
Shuang Song, Yizhen Wang, and Kamalika Chaudhuri. Pufferfish privacy mechanisms for cor- related data. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17, pp. 1291-1306, New York, NY, USA, 2017. Association for Com-
puting Machinery. ISBN 9781450341974. doi: 10.1145/3033918.306644 //doi.org/10. 00..1..114551133530 306405555159001355
URL https
Latanya Sweeney. Achieving k-anonymity privacy protection using generalization and suppression. International Journal of Uncertainty, Fuzziness and Knowledge- Systems, 10(5):571-588 October 2002. ISSN 02 0218-4885. doi: 10. 10.1142//021888888 1448/5002288880200006666 URL http:: /doi org 10.
Tamir Tassa, Arnon Mazza, and Aristides Gionis. k-concealment: An alternative model of k-type anonymity, Trans. Data Priv., 5(1):189-222, 2012.
M. C. Tschantz, S. Sen, and A. Datta. Sok: Differential privacy as causal property. In 2020 IEEE Symposium Security and Privacy (SP), pp.
2020. doi: 00.10999S440000220000000
Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60 60, no. 309:63-69, 1965.
Wai Kit Wong, Nikos Mamoulis, and David Wai Lok Cheung. Non-homogeneous generalization in privacy preserving data publishing. Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 747-758, 2010.
Xiaokui Xiao and Yufei Tao. Anatomy: Privacy and Correlation Preserving Publication. January 2006.
Mingqiang Xue, Panagiotis Karras, Chedy Raissi, Jaideep Vaidya, and Kian-Lee Tan. Anonymizing set-valued data by nonreciprocal recoding. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 1050-1058, 2012.
Bin Yang, Issei Sato, and Hiroshi Nakagawa. Bayesian differential privacy correlated data. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD 15, pp. 747-762, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 178445037588. 2723372. 2747644
doi: 10.114552723377.2777666 URL (htts:: /oi. oo..loogg/1..15...
13

---

Published as a conference paper at ICLR 2022
Wanrong Zhang, Olga Ohrimenko, and Rachel Cummings. Attribute privacy: mechanisms, 2020.
Framework and
Zhu, Xiong, G. Li, and W. Zhou. Correlated differential privacy: Hiding information in non-iid data set. IEEE Transactions on Information Forensics and Security, 10(2):229-242, 2015. doi:
A APPENDIX
A.I BACKGROUND CNTD.
A.2 LOCAL INFERENTIAL PRIVACY
Local inferential privacy captures what information a Bayesian adversary Kifer Machanavajihala (2014), with some prior, can learn in the LDP setting. Specifically, it measures the largest possible ratio between the adversary's posterior and prior belief's about individual's 's data after observing mechanism's output.
Definition A.I. (Local Inferential Privacy Loss Kifer Machanavajhhala (2014)) Let x
(...... .In) and let (W1.-.. Mn)) denote the input (private) and output sequences (observ- able to the adversary) in the LDP setting. Additionally, the adversary's 's auxiliary knowledge is modeled by prior distribution p x. The inferential privacy loss for the input sequence given by
Prp yy pr log
Prp [2; = aly]
Prp
(x(x) = max <E(a]
max Einn] a.bEX
log
log
(4)
Prp
Prp (2 = bly)
Pre J. =
a.EE
Bounding Lx(x) would imply that the adversary's belief about the value of any x; does change by much even after observing the output sequence y. This means that an informed adversary does not learn much about the individual i's private input upon observation of the entire private dataset y.
Here we define two rank distance measures
Definition A.2 (Kendall's Distance). For any two permutations, a, Sn, the Kendall's distance (a, π) counts the number of pairwise disagreements between and æ, i.e., the number of item pairs that have relative order in one permutation and different order the other. Formally,
(, .
: i
o()) (1) < x())
+()]]
(5)
For example, if = 2 10) and x (1 (123654775 then 8, 1)) 3.
Next, Hamming distance measure is defined as follows.
Definition A.3 (Hamming Distance). For any two permutations, o, т E S,, the Hamming distance 6z(0, R) counts the number of positions in which the two permutations disagree. Formally,
(H T) =
{i E [n] a(1) * =
Repeating the above example, = (1 SH (H(a, (T, πT) 2.
5 89 10) and π (12365478910) then
A.3 d PRIVIIYY AND THE DE FINETTI ATTACK
We now show that a strict instance of d privacy is sufficient for thwarting any de Finetti attack Kifer (2009) on individuals. The de Finetti attack involves a Bayesian adversary, who, assuming some degree of correlation between data owners, attempts to recover the true permutation from the shuffled data. As written, the de Finetti attack assumes the sequence sensitive attributes and side information (x1, ...,, (In, in) are exchangeable: any ordering of them is equally likely. By the de Finetti theorem, this implies that they are i.i.d. conditioned on some latent measure 8. To balance privacy with utility, the x sequence is non-uniformly randomly shuffled w.r.t. the t sequence producing a shuffled sequence z, which the adversary observes. Conditioning on z the adversary updates their posterior on (i.e. posterior model predicting 29 (t)( and thereby their posterior
14

---

Published as a conference paper at ICLR 2022
predictive the true The definition of privacy in Kifer (2009) holds that the adversary's posterior beliefs are close to their prior beliefs by some metric on distributions in X, 8(:,)):
8 Pr[p:
We now translate the de Finetti attack to setting. First, to align notation with the rest of the paper we provide privacy to the sequence of LDP values y since we shuffle those instead the x values as in Kifer (2009). We use max divergence (multiplicative bound on events used in DP ) for 8:
Pr(y, E O] S e Pr(y Olz) Pr(ys Olz) e" Pr(ys O]
which, for compactness, we write as
Pr(y: E E R Pr(ys E O|z]
(6)
We restrict ourselves to shuffling mechanisms, where we only randomize the order sensitive values. By learning the unordered values (y) alone, adversary may have arbitrarily large updates to its posterior (e.g. if all values are identical), breaking the privacy requirement above. With this in mind, we assume the adversary already knows the unordered sequence of values {y} (which they will learn anyway), and has prior permutations a allocating values from that sequence to individuals. We then generalize the de Finetti problem an adversary with an arbitrary prior on the true permutation and observes randomize permutation o' from the shuffling mechanism. We require that the adversary's prior belief that a(i) = is close their posterior belief for all i, E [n]]
Vo), where Σ., = f Sn (i) = j}. the set of permutations assigning element to DO,, Conditioning on any unordered sequence {y} with all unique values, the above condition is necessary satisfy Eq. equation 6 for events of the form O = {y: = a). since {y: = a} = {Eir} } for some j E [n]. For any
Pr(a E Exp] Ra Pr[o En,lo'] Vi,j [m], Vo' Sn
{y} with repeat values, it is sufficient since Pr(y; is the sum of probabilities of disjoint events of the form Pr[a E 3 for various k E [n]] values.
We now show that strict instance of do-privacy satisfies Eq. equation Let & be any group assignment such that at least one G; E & includes all data owners, G, 21,
Property 1. A (G. ad-- private shuffling mechanism o' A satisfies Pr(a E 5 R Pría E Engla') for all i,j E [ni] and all priors permutations Pr[o].
Proof.
Lemma 1. For any prior Pr[p]. Eq. equation 7 is equivalent to the condition
EdeE. Pr(a) Proo
Ra Eoes,, Pr[ő]
(8)
Eoer, Pr(o] Pr(a
Exer, Pr[p]
where the set Di, is the complement of Ei.-
Under grouping &. every permutation E Eij neighbors every permutation o Σnj. Fa Ri db for any j.j. By the definition of d, d-rivccc we have that for any observed permutation o' output by the mechanism:
Pría'la oa) Ra Pr(a'|a = os] Vo. Eig, 0b Enj.o' E S.
This implies Eq. 8 Thus, (9, (a)-dd-privan implies Eq. 8 which implies Eq, thus proving the property.
Using Lemmal I we may also show that this strict instance of d ---iiiaacy is necessary to block all de Finetti attacks:
Property (G, a)- -privvate shuffling mechanism o' necessary to satisfy
Pr(g E Ex,j] Ra Pría E Eoy
for all i, E [n]] and all priors on permutations Pr(a].
Proof. If our mechanism AA is not (G, a)--o-priivan then for some pair of true (input) permutations To * ob and some released permutation o' ~ A, we have that Pr(o' [oo] 2 Pr
15

---

Published as a conference paper at ICLR 2022
Under G, all permutations neighbor each other, da & ob. Since da ob. then for some i.j [n], Oa E Ei and σ, E g one of the two permutations assigns some j to some DO; and the other does not. Given this, we may construct a bimodal prior the true that assigns half its probability mass to a and the rest to db.
1
Pr(o.l = Pr[os]
2
Therefore, for released permutation o', the RHS of Eq.
8
is I, and the LHS is
Eeer Pr[o] Pr(o'|6] [ō] Eoez., Pr[o] Pr(o'|o]
1/2 Pr(a' [b)
1/2
e
violating Eq. 8, thus violating Eq. and failing to prevent de Finetti attacks against this bimodal prior.
Ultimately, unless we satisfy d -riivcyy shuffling the entire dataset, there exists some prior the true permutation Pr[a] such that after observing the shuffled z permuted by a', the adversary's 's posterior belief on one permutation is larger than their prior belief by a factor 2 e" If we suppose that the set of values {y} are all distinct, this means that for some {v), the adversary's 's belief that yi is signficantly larger after observing than was before.
Now to prove Lemma]
Proof.
Pr(a Engl Ra Pr(a E Ensla' Pr(a'la E Engl Pr(a E Eng)
Pr(o Eggl Ra Eses, Pr|o|[a)
Pr|o' [0] Na Prio'lo Enpl
dES
Σ
Pr(a) Pr(o'()) R. Pr(a E Engl
Pr(o'(a)
8ES
Σ
Pro
Σ Pr[j] ~. Pr/o E Ensl"
Σ
Pr(p
BEELs
Σ Pr(p'd)) Ra Σ
Pr(a) Pr(o
Pr(o Eigl 1)
deE.
deE,,
E DEER
Pr[o] Pr(o'la)
Eec Pr(d]
Za
Σ Exer, Pr[o] Pr
Eeer,, Pr(a]
As such, strict instance of do-privacy can defend against any de Finetti attack (i.e. for any prior Pr[o] on permutations), wherein at least one group G; E & includes all data owners. Furthermore, is necessary. This makes sense. In order to defend against any prior, we need to significantly shuffle the entire dataset. Without a restriction of priors as in Pufferfish Kifer & Machanavajhala (2014), the de Finetti attack (i.c. uninformed Bayesian adversaries) is indelicate metric for evaluating the privacy of shuffling mechanisms: to achieve significant privacy, we must sacrifice all utility. This in many regards is reminiscent of the free lunch for privacy theorem established in Kifer & Machanavajihala (201T). As such, there is a need for more flexible privacy definitions for shuffling mechanisms.
A.4 ADDITIONAL PROPERTIES OF d, -PRIVACY
Lemma 2 (Convexity). Let AI.... A ymh H V be a collection of k (a. --ddaprvvate mechanisms for a given group assignment G on a set of n entities. Let A y + V be convex combination of these k mechanisms, where the probability of releasing the output of mechanism A, is Pi. and Ek P; 1. A is also (a, -ridaatvv w.r.t. G.
16

---

Published as a conference paper at ICLR 2022
Proof. For any (a, Ng and y V
k
Pr[A([(y)) E =0 Σ p.Pr((((((s)) O
c Σ (. EO]
-Pr(A(d(y)) EO]
Theorem A.1 (Post-processing). Let A: y + y be (o, ---aaprivatee for a given group assignment on a set of n entities. Let f: V be an arbitrary randomized mapping. Then f A y" V also (a, privatee
Proof. Let g : V + V be a deterministic, measurable function. For any output event C V W be its preimage: W = (u Vlg(v) 2}. Then, for any (a, E Ng.
Pr Pr[g Pr(g(A(a())) E 2 = Pr Pr(A(((x)) ew]
Sea Pr Pr(A(d ew]
= -" Pr - ( E
This concludes proof because any randomized mapping can be decomposed into convex combination of measurable, deterministic functions Dwork & Roth (2014), and as Lemma shows, convex combination of (a, ())-d,privatt mechanisms also (a, G) private.
Theorem A.2 (Sequential Composition). If Ai and A2 are (01,9)- and (az, -)-doprivatte mecha- nisms, respectively, that use independent randomness, then releasing the outputs (Ai satisfies (a1 + a2
_ -> V" each satisfy de do-privacy for different values. Let A: yd + (V' x V") output (Ar(y), Ab(()), Then, we may write any event Z E (V' x V") as Z' x Z", where Z' E V and z" V" We have for any (a, (a, eg.
Proof. We have that Ar )m + V and A1 3
Pr(A(o(y)) 2] (r((A)())))) E
Pr ( Ez}]
S taut ( z")]
= Pr A(o E2
A.5 PROOF FOR THM. 4.1
Theorem
For a given group assignment G on a set of n data owners, if a shuffling mechanism nd is (a, 9) privvate then for each data owner DO,, i [n]. Prp [r; = alz, (yG. V.y log
A:
Prp(z; = a alflaaa...... l................
log
<a
iEin X
Pro(z; b/z, (VG. V..
Prp bly...
for prior distribution P. where Aly) and Yo, is the noisy sequence for data owners outside G,-
17

---

Published as a conference paper at ICLR 2022
Proof. We prove the above by bounding the following equivalent expression for any i [nx] and a, b E X.
Prp [z (uG, N..
Prp [ b, (ya.
I Prrly| = a, fvG, H. zyydy
[Prply|a; = b, Lua, Pr Pra|z/y]d
EoEs, Prplo(yč,)lu a, Pr Prulzlo(yč,,.vaa ya.
Exes, (plo(yy))l P
Pralol((sa)..v. (a.0'ES.)
(ya) max
Pra|zlo(y)]
max (a,o'ENa) Pra(z(o'(y))
The second line simply marginalizes out the full noisy sequence y. The third line reduces this to sum over permutations of of yG,, where r = G.ll and yč, is any fixed permutation of values (yG, }- This is possible since we given the values outside the group, yo, and the unordered set of values inside the group, {VG, J. Note that the permutations written here are possible permutations of the LDP input, not permutations output by the mechanism applied to the input as sometimes written in other parts of this document.
The fourth line uses the fact that the numerator and denominator are both convex combinations of Pralz)o(yy,,)) ). ya, over all S,.
The fifth line uses the fact that for any YG."
(o(y),) k,, >c, (d
This allows a further upper bound over all neighboring sequences w.r.t. G,, and thus over any permutation of ye. long it is the same in the numerator and denominator.
Discussion The above Bayesian analysis measures what can learned about DO,'s 's x; from observing the private release relative to some other known information (the conditioned information). Under -p-iviay,y, we condition on the bag of LDP values in Alice's s group {yG; } as well as the sequence (order and value) of LDP values outside her group YG, This implies that releasing the shuffled sequence z cannot provide much more information about Alice's 's x; than would releasing the LDP values outside her neighborhood (her group) and the unordered bag of LDP values inside her neighborhood, regardless of the adversary's prior knowledge P. This is communicable guarantee: Alice feels comfortable with the data collection knowing that her entire neighhorhood's responses will be uniformly shuffled together (including those of her household), then she ought to be comfortable with d, do-privacy. Now, have to provide this guarantee to Bob, neighbor of Alice, well as Luis, a neighbor of Bob but not of Alice. Thus, Bob, Alice and Luis have distinct and overlapping groups (neighborhoods). Hence, the trivial solution of uniformly shuffling the noisy responses of every group separately does not work in this case. d, de-privacy, however, offers the above guarantee to each user (knowing that their entire neighborhood is nearly uniformly shuffled) while still maintaining utility (estimate disease prevalence within neighborhoods). Semantically, this is very powerful, since it implies that the noisy responses specific to one's household cannot be leveraged to infer one's disease state Zz.
A.6 PROOF OF THROREM 4.2
Theorem 4.2
For A(M(x)) = z where M(-) is e-LDP and A(-) is a daprivate, we have Pr(D Adv loses) -1- k (2kcta) Pr(D Adu wins)
for any imput subgroup I G [Gil and k: r/2.
18

---

Published as a conference paper at ICLR 2022
Proof. We first focus on deterministic adversaries and then expand to randomized adversaries afterwards using the fact that randomized adversaries are mixtures of deterministic ones.
Our adversary Adu is then defined by deterministic decision function 1) 3 [n]*. Upon observing z, n2(z) selects & clements in z which believes originated from 1 C G.--
In the following, let Pr, be the probability of events conditioned the shuffled output sequence where randomness is over the c-LDP mechanism M and the a-d, -private shuffling mechanism ...
The adversary wins if it reidentifies f/r of the LDP values originating from I. Let H n7()) be the indices of elements selected by n. Let W fo E Sa (H(H) I| > 2) be the set of permutations where the adversary wins and let L for E S" o ni s k) be the set of permutations where the adversary loses.
Pr(n(z) wins] = Pr(o e W
=
Pr(n(() loses] = Pr(o E L]
where a is the shuffling permutation produced by A, = oly) i.e. = yo(a)- Concretely, this is equivalent to DO; releasing (O,(s) LDP response. Since the permutation and LDP outputs randomized, many subgroups of size k in G; could have produced the LDP values (zH, :-H,....; zH, and then been mapped to by a permutation. Concretely, there a reasonable probability that Alice's household output the LDP values of another k-member household in her neighborhood and they output her household's LDP values. In the worst case, this is e 2ke less likely than without swapping values, by group DP guarantees. Since both households are part of the same group Gs, the permutation that maps her household to elements H in the output is close in probability to that which maps the other household elements in the output. As such, we have the worst case (2ke+a) reduction probability of the other household having swapped LDP values with Alice's and permuting to subset H.
-
The above provides intuition on how could get the same output z many different ways, and how Alice's 's household could or could not contribute to elements H. It does not, however, explain why an adversary who is given output z has limited advantage choosing subset H such that they recover most of Alice's 's household's 's values. We formalize this fact as follows.
We may rewrite the probabilities of winning or losing by marginalizing out all possible LDP sequences y. Conditioning on the output sequence z, the only possible LDP sequences y are permutations z. Note that the probability of any sequenee y is determined by the input x and the LDP mechanism MM
Pr(n(z) loses] = Prllo E W] x
x
Pr[A(xx) = =oo Pr(ol)]///ppppppppppppppp Pr(z]
oEW
Note that Prz[oly] = Prz[a] for the mallows mechanism, which chooses its permutations indepen- dently of y. Now consider when 17(z) loses. By similar arguments as above:
Pr(n(z) loses] = Pr(o E L]
Σ
= ([a(x)====--00 Pr[ply] Pr[z]]
OEL
The odds of losing versus winning given by
EOEL Pr A(x) = y (z) Pr|p'|y]
Prg (z( loses]
Pr (z) wins]
EoEw Pr(A(x) = y = o- (z) Pr(aly]
We now show that for each a in the denominator, we may construct m a' in the numerator that are close in probability it.
distinct permutations
Lemma 3. For every E W there exists a of [= permutations, E(g), such that
$ As an abuse of notation, we assume the output space of the LDP randomizers. Y, have outcomes with non-zero measure e.g. randomized response. The following analysis can be expanded to continuous outputs (with outcomes of zero measure) by simply replacing the output sequence E y with an output event Z C y
19

---

Published as a conference paper at ICLR 2022
1. B(o) LL
2. 0- No; 0 --11
3. B(oa) n B(or) 0 for any pair oa, 0b E W
4. Pr[A(x)= = = o (z)] S e ahe =y= for any x E d and any
=y=
z E ym
Proof. Given W, construct F((o) by first taking the inverse 0 Recall that, since W, we have that (T) H| > k. (1) = could be interpreted as data owner i's LDP value will be output at position j). We then divide the remainder of the group G into m disjoint subsets of size each, J1, ,2,..., Jm. These represent the other distinct subsets of size k that Alice's household could swap LDP values with. We then produce m permutations, 0 3'-1 ....., d-11 by making (1) o (J;) and 0,- (J,) = =
(preserving order within those subsets) and
0- everywhere else.
On the first point, we know that every a' E [(r) is also in L. We know this because o, (1) (J.). Since a E W, we have that lo (J:) n H| < k since (o- 2 and In by definition. Thus, (1)
2
$ so (of( nd) < うタ and of L.
On the second point, we know that the inverse permutations are neighboring a-  G, o simply by construction they only differ on elements in G,.
On the third point, we know that the sets E(aa) and E(a,) are distinct since we can map any permutation o' E Fi(a.) uniquely back to aa for any oa E W. We do so by taking its inverse o' finding which subset J; has majority elements from H i.e. lo (J:) n H > Z. Swap elements back: - (J:) with o' (1). Invert back to Ta.
On the fourth point, we know that o (z) and σ (z) differ on most 2k indices. As such, by group DP guarantees, we know that their probabilities must be close to a factor of e 2kkr regardless of z and x.
Using the above Lemma may bound the odds of losing vs. winning.
ENEL Pr A(x = - (z) Pr(o'ly]
Prę (n( loses]
Prz[n [z)) wins]
Enew Pr(A(x)= = o-=o-(())) Prloly)
Eoew EOEECO Pr A(x) = y o' (z) Pr[o'ly]
Eoew Pr(A(x) = o Pr Pr(oty]
EvEE(O Pr A(x) y o (z) Prio'|y]
min nEW
Pr(A(x) =y= = 0z) =
Pr(pty]
Je (2ke+a)
k where the last line follows from the fourth point of the above Lemma (for the 2ke term) and the fact that the inverse permutations a'11, - are neighboring (second point of the Lemma) so the probabilities of the mechanism to produce vs. o' to reach z from these neighboring permutations must be close by a factor e
Since the above holds for any z and the bound holds on average across all outcomes z, thus r Pr(m loses] _ A:
-ー k.
(22keta) Pr[n wins]
for any deterministic adversary with decision function 17. Finally, may write any probabilistic adversary as mixture of decision functions. By convexity (same argument used in Lemma 2). the above bound still holds. As such,
20

---

Published as a conference paper at ICLR 2022
Pr(DAde loses] 2 r - Pr(DAde Ado wins]
-2kketa)
h
A.7 UTILITY OF SHUFFLING MECTIANISM
We now introduce a novel metric, (17. 8) preseervttion, for assessing the utiliity of any shuffling mechanism. Let S S [n] correspond a set of indices in y. The metric defined as follows.
Definition A.4. (17, 5) prreservvatinn) shuffling mechanism A )"h + ) is defined to be (1), 6)-
preserving (17, 5 E [0, 1]) w.r.t to given subset S C [m]. if
Pr [| n 2 n- |-|S|] 2 ES
where z - A(y) = oly) and S. - (o(1)
If A(-) permutes the output according to = ($32679814 10), then S, (5, 7,8,1] which preserves or 80% of its original indices. This means that for any data sequence at least fraction of its data values corresponding to the subset S overlaps with that of shuffled sequence z with high probability (1 6). Assuming. (us) {usli E 3} and {=s} = {z/li 5} = (Ve(olé E S) denotes the set of data values corresponding S data sequences y and z respectively, we have Pr [1 {Ms} {=s) )1 2 1 1-|s 2 6, Vy. For example, let S be the set of individuals from Nevada. Then, for a shuffling mechanism that provides (n 0.8, = 0.1) o.1)-preservation to S, with probability 2 0.9, 2 80% the values that are reported be from Nevada in z are genuinely from Nevada. The rationale behind this metric is that it captures the utility of the learning allowed by de fo-privacy - S is equal to some group G E G. (1), ô) preservation allows overall statistics of G to be captured. Note that this utility metric agnostic of both the data distribution and the analyst's 's query. Hence, it is a conservative analysis of utility which serves as a lower bound for learning from {=s)- We suspect that with the knowledge of the data distribution and/or the query, tighter utility analysis is possible.
For example, consider S (1,4,5,7,8).
formal utility analysis of Alg. 10 is presented in App. A.13 Empirical evaluation of (17 6)
preservation is presented in App. A.
A.8 DISCUSSION ON PROPERTIES OF MALLOWS MECHANISM
Property 3. For group assignment a mechanism A(-) that shuffles according permutation sampled from the Mallows model F. (.). satisfies (a, ---do--iivve where
A(ou S, G) (a.0 NeNg and
max b( σa) 5(aroa', ,0))
a 0 (oro: (. We refer to Alao 8, G, the sensitivity of the rank-distance measure 5(.)
Proof. Consider two permutations of the initial sequence y, ai (y), (2()) that neighboring w.r.t. some group G2 E G, 01 Ri, d2. Additionally consider any fixed released shuffled sequence z. Let Σ, Dg be the permutations that turn σ (y), (y()) into z. respectively:
Σ = {o E S, oo z}
Σg (a S, 002 (y) z}
In the case that } consists entirely of unique values, Σ, Dg will each contain exactly one permuta- tion, since only one permutation can map 0; (y) to z.
Lemma 4. For each permutation of En there exists a permutation in o2 E 2n such that of SG. o22
Proof follows from the fact that since only the elements j E G2 differ in o (y) and o2(y) only those elements need to differ to achieve the same output permutation. In other words, may define of.o% of at all inputs & G, identically, and then define all inputs E G2 differently as needed. As such, they are neighboring w.r.t. G..
21

---

Published as a conference paper at ICLR 2022
Recalling that Alg. applies o to the sampled permutation, must sample Jo (for some of E Σ1) for the mechanism to produce z from 01 (y). Formally, since oj (y = z we must sample Too to get z since we are going to apply do. to the sampled permutation.
Pr [r(A((())) - = = Pa (asoonn', o Σi o0)
Pr (r(2(()()) - =z] = Pa, (ouo' . E E2 o0)
Taking the odds, we have
P Pas (ono' o' E EL1:
Eo'es, Paslono' :0)
P Po,so000" o" ,0" E Σし 00)
E E P " oa)
Ex'ez, -0oooo'' .00)
Ex"Ex, e 00(000",00) oo(opuunno)
80(o0ss.oo)
0 Mo) (
00
where
Ab(aro .o) and
Ja arg max e'
aa = arg min e - .o0) e"E
Therefore, setting 0 A. achieve (a, -riipiiv.
Property 4.
The sensitivity of a vank-distance is an increasing function of the width ug" For instance, for Kendall's t distance 5,()), we have A Sr 9)
wg (w +1)
2
To show the sensitivity of Kendall's T, we make use of its triangle inequality.
Proof. Recall from the proof of the previous property that the expression 8(a, ((000,00).
where the actual rank distance measure e.g. Kendall's r. As such, we require that
4g 0n
(ug + +1)
b(ap)a, d(anas, oo)l
for any pair of permutations (aa, 0b) E Ng.
For any group G; G, let W; C n represent the smallest contiguous subsequence indices in do that contains all of G,,
For instance, ag [2, 4, 6, 8, 1, 3, 5, and G, = {2, 6, 8), then W; (2, 4, 6,. Then the group width width is wi [W; - 3. Now consider two permutations neighboring w.r.t. G,, da sG, db. so only the elements of G, are shuffled between them. We want to bound (8(00o,; oo) (()05,00))
For this, we use a pair of triangle inequalities: 8(ano 00o)) 8(000. σo) - 5(000) σo) & ((000a,0000
S(000,, σo) 6(0noa, σo)
so,
(( - b(ovos, 8(000 000,)
Since oo and 70% only differ in the contiguous subset W,, the largest number of discordant pairs between them is given by the maximum Kendall's distance between two permutations of size wi + +1:
Wi (wi + 1)
|800 onor))
Since w wi for all G; G, have that
Wg (w + 1)
A(ao 6, <
22

---

Published as a conference paper at ICLR 2022
A.9 HARDNESS OF COMPUTING THE OPTIMUM REFERENCE PERMUTATION
Theorem A.3. The problem of finding the optimum reference permutation, i.e. σō =
arg Es, wg is NP-hard.
Proof. We start with the formal representation of the problem as follows.
Optimum Reference Permutation Problem. Given n subsets g = {G, E 2lml, E [n]]} find the permutation oj arg min wg-
Now, consider the following job-shop scheduling problem.
Job Shop Scheduling. There is one job J with n operations o,, i [n] and machines such that o needs to run on machine M, Additionally, each machine has a sequence dependent processing time ps- Let S be the sequence till There are n subsets S; S [n)] each corresponding to a set of operations that need to occur in contiguous machines, else the processing times incur penalty as follows. Let P; denote the processing time for the machine running the i-th operation scheduled. Let Sy be the prefix sequence with i schedulings. For instance, if the final scheduling is 3 4 5 9 8 10 6 7 2 then $ = 1345. Additionally, let Ps, be the shortest subsequence such of Sy such that it contains all the elements in Sy n {S.). For example for S 5, Pa. 345.
P: = max(1 -S, (S,}))
(10)
*E[n]
The objective is to find scheduling for such that minimizes the makespan, i... the completion time of the job. Note that Pa. = max; hence the problem reduces to minimizing Pa.
Lemma 5. The aforementioned job shop scheduling problem with sequence-dependent processing time is NP-hard.
Proof. Consider the following instantiation of the sequence-dependent job shop scheduling problem where the processing time is given by P:=P:-1 + Wkk. P1 O where S - -] k: S, = and Wijjj E S, represents some associated weight. This problem is equivalent to the travelling salesman problem (TSP) Balas 2008) and is therefore, NP-hard. Thus, our aforementioned job shop scheduling problem is also clearly harh
Reduction: Let the subsets S, correspond to the groups in G. Clearly, minimizing wg minimizes Pu- Hence, the optimal reference permutation gives the solution to the scheduling problem as well.
A. ILLUSTRATION OF ALG.
We now provide a small-scale step-by-step example of how Alg. I operates.
Fig. 6a an example of a grouping G dataset of elements. The group of DO, includes i and its neighbors. For instance, Gs = (8, 3, 5). To build a reference permutation, Alg. starts at the index with the largest group.
(highlighted in purple), with G5 {5, 2, 3, 8, 4}. As shown in Figure 6bb the ao is then constructed by following BFS traversal from = 5. Each j E G5 is visited, queuing up the neighbors of each j G5 that haven' been visited along the way, and so on. The algorithm completes after the entire graph has been visited.
The goal is to produce reference permutation in which the width of each group in the reference permutation wi is small. In this case, the width of the largest group G5 is as small as it can be wi = 5
4. However, the width of G. = {4, 5, 7) is the maximum possible since -1( = and o (7) = 8,
7. This is difficult to avoid when the maximum group size is large as compared to the full dataset size n. Realistically, we expect n to be significantly larger, leading to relatively smaller groups
With the reference permutation place, we compute the sensitivity:
wa(w4 + 1)
A 6, 9)
28
23

---

Published as a conference paper at ICLR 2022
6
2
3
5
1
8
7
4
(a) Group graph
4(())
6x2))
a(3)
<g(4)
4y(6)
488)
2
8
6
7
queue
1
pos'n
8
6
2
7
(b) BES reference permutation
Figure 6: Illustration of Alg.
Which lets us set 0 = for any given privacy value. To reiterate, lower 0 results in more randomness in the mechanism.
We then sample the permutation ē P (oo). Suppose à =3 (32548176]
Then, the released is given as
[y] One can think of the above operation follows. What was in the reference permutation (oo(1) 5) is 3 in the sampled permutation (0(1) 3). So, index 5 corresponding to DO; now holds DO, 's noisy data ys- As such, we shuffle mostly between members of the same group, and minimally between groups.
V/ y7 yo Val
The runtime of this mechanism is dominated by the Repeated Insertion Model samplerDoignon Doignon et al. (2004), which takes (nz²) time. It is very possible that there are more efficient samplers available, RIM is standard and simple to implement for this first proposed mechanism. Additionally, the majority of this is spent computing sampling parameters which be stored in advanced with (n²)) memory. Furthermore, sampling from a Mallows model with some reference permutation do equivalent sampling from Mallows model with the identity permutation and applying it to de- As such, permutations may be sampled in advanced, and the runtime is dominated by computation of do which takes O(VVI + [E) time (the number of vertices and edges in the graph).
future direction could exploring even better heuristics for computing do- One possibility could be based on ranked enumeration of the permutations Deep Koutris 2021): Deep et al. (202)
24

---

Published as a conference paper at ICLR 2022
A.11
PROOF OF THM. 4.3
Theorem 4.3 Alg. is (at, Gd private.
Proof. The proof follows from Prop. Having computed the sensitivity of the reference permutation du. A, and set 0 = =a/ A, we are guaranteed by Property 3 that shuffligg according the permutation à guarantees (ox, -da
A.12
PROOF OF THM.
Theorem 4.4 Alg.
satisfies (a',9') ddoprivccyy for any group assignment G' where of
A
A(ro:..))
Proof. Recall from Property 3 that we satisfy (a, 9) do -r-iviyy by setting = a/Dlop : 8, s, Given alternative grouping G with sensitivity Aoo à, G"), this same mechanism provides
a'
Aloo : ))
a/D(ou 6,9)
A s g")
A b g')
a
A(oo b, g)
A.13 FORMAL UTILITY ANALYSIS OF ALG.
Theorem A.4. For a given set S C [n]] and Hamming distance metric, Sn(-), Alg. is (1) 6)- preserving for 8= ((b)s) Eh=2k+1 (e- cx) where k [(1 - 4) 1))1 and en is the number of permutations with hamming distance h from the reference permutation that do not preserve 1 of S and is given by
max((e,11/21) Σ
min(l, j.h
16
n2 11)
1 -
Σ
Ch
j=H+1
1=0
1 (1+)) f(i.j).
n (n- 1,
f(h 2j i.j)! f(i,0) =li, (0,
h h 2j -
min(<e)
(t) ( 9
f(i.j)
Σ
j! f(i (
400
n!
4= k (1 1)) la In
Proof. Let l, = |S] denote the size the set and = [[1 - 77) 7)-19 denote the maximum number of correct values that can be missing from S. Now. for given permutation e S,, let h denote its Hamming distance from the reference permutation op. i.c, h = Sn (a, oo). This means that a and do differ in indices. Now, h can be analysed in the the following two cases,
Case I. < 2k +
For (1 17) fraction of indices be removed from S, need at least l: + 1 indices from S to be replaced by + 1 values from outside S. This is clearly not possible for < 2h + Hence, here
Ch 0.
25

---

Published as a conference paper at ICLR 2022
Case II. h >>>2 2k
For the following analysis we consider we treat the permutations as strings (multi-digil numbers are treated single string character). Now, Let So, denote the non-contiguous substring of do such that it consists of all the clements of S, i.c.,
ls
(11)
Vi E [s] So, ES Let S. denote the substring corresponding to the positions occupied by Sog in a. Formally,
(12)
|S = ls
(13)
Vi [1s] S.. [1] o (S.. (i))
(14)
For example, for σo = 4235478110 -
- (1327854615)
and (2,4,5,8)
we have S. 2548 and S, = 3784 where h (0,000 - Let (S,} denote the set of the elements string S, Let be the set characters in S. such that they do not belong to S, i.e A (S, || S [1] S E [[s]] Let B be the set of characters in S that belong to S but differ from So, im position, i... = {S, | S i E S, S. k + So, [i] [(]]. Additionally, let C = S ( For instance, in the above example, A (3,7) B [4,8), (2, Now consider
initial arrangement of p + m distinct objects that are subdivided into two types objects Type A and m objects of Type B. Let f(p, m) denote the number of permutations of these p + m objects such that the m Type B objects can occupy any position but no object of Type A can occupy its original position.
For example, for [p, 0) this becomes the number of derangements der denoted as Ip 22 Therefore, B). [A)) denotes the number of permutations of & such that dy (So, S.) A B]. This is because if elements of B are allowed to occupy their original position then this will reduce the Hamming distance.
Now, let S., (S.,) denote the substring left out after extracting from S, (S.,) from (o)). For example, S, 1256109 and S,, 1371096 in the above example. Let be the of elements outside of S and A that occupy different positions in S, and S., (thereby contributing to the hamming distance), i.e., D = [Soois]
& S,So.14 + Solq. i E [n -ss}]- For instance, in
the above example f([D), (C1) represents the number of permutations of S, such that d (S., S..)
{9. 6, 10). Hence, = (a, 0o) | + B + [Cl + [D] and clearly
= |C| + (D]. Finally,
we have
max(I..I 14/2))
1
Ch Σ
1=k+1
ways of selecting set C. ways of selecting set A
min(1.
j.h- 2j)
Σ
((i,5)
1=0
# ways of selecting set
n1 1a -J 2j
([h 2iuh-2j-th0 i.j)
@ ways of selecting D
Now, for f(i,j) let E be the set of original positions of Type A that are occupied by Type objects in the resulting permutation. Additionally, let J' be the set of the original positions of Type B objects that still occupied by some Type B object. Clearly, Type B objects can occupy these E + |F| m in any way they like. However, the type A objects can only result in f(p - 9. 9) permutations. Therefore, [p, m) given by the following recursive function
f(p 0) =!p
f(0, m) m!
min p.m
f(, m) = Σ
m
9
ways of selecting
ways of selecting set
m! m../ m 9, 9)
26

---

Published as a conference paper at ICLR 2022
Thus, the total probability of failure is given by
n
Σ h=2k+2
(e 0 .c)
(15)
16 bH))
A.14
ADDITIONAL EXPERIMENTAL DETAILS
A.14.1
EVALUATION OF (7, 8) PRESERVATION
1.0
1.0
5-10% u-12
0.8
0.8
5--005
0.8
0.6
0.6
0.6
6-400
0.4
0.2
0.2
0.2
90
0.0
0.0
10
100
50
100
150
200
18.0%%
25%
50%
75%
100%
Privacy Parameter
Width
Subset
Variation with
(b) Variation with wi
Variation with 1s; a =
Figure 7: (n, Preeeeservttion Analysis
In this section, we evaluate the characteristics of the (7 preseervaiio for Kendall's distance (:,-).
Each sweep of Fig. fixes 8 = 0.01, and observes 77. We consider dataset of size 10K and a subset 5 of size is corresponding to the indices in the middle of the reference permutation do (the actual value of the reference permutation is not significant for measuring preservation). For the rest the discussion, we denote the width of a permutation by w for notational brevity. For each value of the independent axis, we generate 50 trials of the permutation from Mallows model with the appropriate 0 (given the w and a parameters). We then report the largest (fraction of subset preserved) that least 99% of trials satisfy.
In Fig. 7a we see that preservation is highest for higher a and increases gradually with declining width and increasing subset size 4,
Fig. 7b demonstrates that preservation declines with increasing width. A increases quadratically with width for 6,, resulting declining and increasing randomness. We also see that larger subset sizes result in a more gradual decline in 77. This is due to the fact that the worst-case preservation (uniform random shuffling) better for larger subsets. i.e. we cannot worse than 80% preservation for subset that is 80% of indices.
Finally, Fig. demonnsttts how preservation grows rapidly with increasing subset size. For large widths, we are nearly uniformly randomly permuting, preservation will equal the size of the subset relative to the dataset size. For smaller widths, we see that preservation offers diminishing returns as we grow subset size past some critical 4,. For = 30, we see that subset sizes much larger than quarter of the dataset gain little in preservation.
A. 14.2
ADULT DATASET
A.15 ADDITIONAL. RELATED WORK
In this section, we discuss the relevant existing work.
The anonymization of noisy responses to improve differential privacy was first proposed by Bittau et al. Bittau et al. (2017a) who proposed principled system architecture for shuffling. This model was formally studied later in EElingsson et al. (2019): Cheu et al. (2019). Erlingsson et al. [Erlingsson et al. (2019) showed that for arbitrary e- DDL randomizers, random shuffling results in privacy amplification. Cheu et al. Cheu et al. (2019) formally defined the shuffle DP model and analyzed the privacy guarantees of the binary randomized response in this model. The shuffle DP model
27

---

Published as a conference paper at ICLR 2022
1.0
% of Data Inferred
0.6
% of Data Inferred
0.6
2.7X Improvement
0.4
0.4
over LDP
TV Error A
0.8
0.6
0.2
1.7X improvement
0.2
over LDP
0.4
4
0
2
4
6
8
0
1
2
5
Distance Threshold
Privacy Parameter
Distance Threshold r
(a) Adult: Attack
(b) Adult: Attack (a)
(c) Adult: Learaaillity
Figure 8: Adult dataset experiments
differs from our approach in two ways. First, it focuses completely on the DP guarantee. The privacy amplification is manifested in the from of lower (roughly a factor of /n) when viewed in an
alternative DP model known as the central DP model. Erlingssson et al. (2019 x Cheu et al. (2019);
Balle et al. 2219);; Feldman et al. (2020); BBittau et al. (2017a) Balcer & Cheu (202)). However, our result caters to local inferential privacy. Second, the shuffle model involves an uniform random
shuffling of the entire dataset. In contrast, our approach the granularity at which the data is shuffled is tunable which delineates a threshold for the learnability of the data.
A steady line of work has sudied the inferential privacy setting Kasiviswanathan & Smith (2014);
Kifer & Machanavajjhala (201T); Ghosh & Kleinberg (2016); Dalenius (1977); Dwork Naor [2010) et al. (2020). Kifer et al. Kifer & Machanavaijhala (2011) formally studied privacy degradation in the face of data correlations and later proposed a privacy framework, Pufferfish Kiffr & Machanavajhaala (2014); Song al. (2017); He et al. (2014), for analyzing inferential privacy. Subsequently, several other privacy definitions have also been proposed for the inferential privacy
setting Liu et al. (2016); Yang et al. (2015); Chen al. (2014); Zhu et al. (2015); Bassily et al. (2013).
For instance, Gehrke et al. proposed a zero-knowledge privacy Gehrke et al. (2011) 2012) which
based simulation semantics. Bhaskar et al. proposed noiseless privacy Bhaskar et al. (20TT):
Grining & Klonowski (217)) by restricting the set of prior distributions that the adversary may
have access to. A recent work by Zhang al. proposes attribute privacy Zhang et al. (2020) which
focuses on the sensitive properties of whole dataset. In another recent work, Ligetr et al. study relaxation of DP that accounts for mechanisms that leak some additional, bounded information about the database Ligett et al. (2020). Some early work in local inferential privacy include profile-based based privacy Geumlek& & Chaudhuri (2019) by Gehmke et al. where the problem setting comes with a graph of data generating distributions, whose edges encode sensitive pairs of distributions that should be made indistinguishable In another work by Kawamoto et al., the authors propose distribution privacy Kawamoto & Murakami (2018) local differential privacy for probability distributions. The major difference between our work and prior research is that we provide local inferential privacy through a new angle data shuffling.
Finally, older works such as k-anonymity Sweeney| (2002), I-diversity Machanavajjhala et al. 2007
and Anatomy Xiao & Tao (2006) and other Wong al. (2010); Tassa al. (2012); Xue al. (0012) ;
Choromanski et al. (2013); Doka el al. (2013) have studied the privacy risk of non-sensitive auxiliary
information, or "quasi identifiers' (QIs). In practice, these works focus on the setting of dataset release, where we focus on dataset collection. As such, QIs can be manipulated and controlled, whereas we place no restriction on the amount or type of auxiliary information accessible to the adversary, nor do we control it. Additionally, our work offers each individual formal inferential guarantees against informed adversaries, whereas those works do not. We emphasize this last point since formalized guarantees are critical for providing meaningful privacy definitions. As established by Kifer and Lin in An Axiomatic View of Statistical Privacy and Utility (2012), privacy definitions ought to at least satisfy post processcnssing and convexity properties which our formal definition does.
28

---

Published as a conference paper at ICLR 2022
A.16
EVALUATION OF HEURISTIC
10F
Heur Rand.
10
10
10a
10a
10r
1014
100
10a
107
107
10a
10a
10a
10
100
10
10a
10a
10a
10'
10a
10'
10a
10'
101
107
10'
N
N
Figure 9: Comparison of our heuristic's performance with that of an optimal reference permutation a An optimal où is generated with every group having size A graph is generated from this optimal oú from which heuristic (blue) attempts reconstruct the optimal permutation. For baselining, the performance of random du selection is plotted (orange). We observe that worst, our heuristic picks reference permutation with width 2.5x that the optimal reference permutation (green). See Section 4.4 for definition of terms.
Algorithm 10 designed find reference permutation do with low width wg w.r.. the given grouping g. A low width is desirable, since it leads low sensitivity A 8, G), which in turn leads to higher dispersion parameter = a A, and thus less randomness over permutations (higher utility). Theorem A.33 | proves that computing the optimal reference permutation (minimum width) is hcuristic.
NP-hard. As such, we propose a
Comparison with optimal reference permutation
To demonstrate the value of the heuristic used Alg. TO we provide two evaluations of its compare the performance of our heuristic BFS reference permutation selection (an) with that of the optimal reference permutation and that of random reference permutation. As identified Theorem A.3) finding the optimal reference permutation for given grouping G is NP-hard. For these experiments, we first create an optimal reference permutation, where each group G2 G is equally sized and maximally compact. The optimal width, w is then min(n (n, w). We then generate a graph from this optimal reference permutation. Finally, we run the BFS reference permutation computation described in Alg. 10 attempting to approximate the optimal og and compute its width.
performance. For first evaluation,
To compare with naive approach, we also plot the performance of randomly chosen reference permutation. We expect the maximum width across groups wg to be large for this technique. If one of the groups has single entry low (near 0) in an and single entry high (near n) dg. the width will be near The random baseline is averaged over 10 trials with standard deviation envelope plotted (but difficult to see, since the variance is low).
Figure depicts our findings. Each plot has different group size listed at the top, used in the optimal reference permutation. We find that the random baseline (orange) consistently chooses a reference permutation such that wg is n, expected. Our method (blue), the other hand, closely tracks the optimal solution (green). We find that in the worst case, our algorithm's solution has width 2.5x larger than the optimal. Note that for 0 (upper left), all methods trivially
29

---

Published as a conference paper at ICLR 2022
have width of one, since the corresponding graph has edges. While there may be room for improvement, we find this to be sufficient for the present work.
000000
==0.025
==0.050
==0.075
10a
Heur.
Rand
10a
107
10a
10"
10
10"
10a
10r
10
==0.10
0=0.1
0=0.55
y= 0=0.00
10a
10a
107
10P
10a
10*
10
104
107
10
101
10a
10'
N1
11
N
Figure 10: example of our heuristic's performance randomly generated graphs. As increases, does the connectivity of the random graphs and the average group size (green). As shown Theorem computing the optimal wg NP-hard. The average group size (green) in G a loose lower bound on the optimal wg. The performance of a random de assignment (orange) is also plotted for reference. Our heuristic BFS algorithm (blue) consistently outperforms the random bascline.
Performance on randomly generated graphs For our second evaluation, we observe how well BFS heuristic (in Algorithm 10) performs randomly generated graphs. Here, we sample points uniformly on the unit interval. We then say that the ith point's group, GG, consists of all other points within of it. As increases, does the groups size. Since computing the optimal reference permutation is NP-hard (Theorem A.3). we do not show the optimal width. Instead,
show loose lower bound of the optimal width (green) by plotting the average group size for a given r (recall that the width greater than or equal to the largest group size, we evaluate the performance of a random ag choice as well. For both of these methods, we run 10 trials of generating random graph (and picking random aσ) each value of and plot the mean along with 1 standard deviation envelope, which is difficult to see due to low variance.
expect this to be loose lower bound, solely for reference). For comparison,
Figure 10 depicts our findings. We find that across values of and r our heuristic (blue) significantly outperforms the random baseline (orange). Additionally, we observe the trends expect. For low values, our heuristic BFS algorithm chooses do with width close to the lower bound (green) of the optimal width wg. As r increases, the graph become significantly more connected. Both the lower bound and our heuristic move closer to the width of the random baseline. Note that for 0 (upper left), all methods trivially have width of one, since the corresponding graph has no edges. Ultimately, these findings indicate that our heuristic for computing do significantly outperforms naive random choice, and follows the same trend the lower bound of the optimal.
30


Reviews:
[{"review_id": "svYZI_uHHyL", "reviewer": "Reviewer_ayWA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is original, motivated by allowing more data learnability in the shuffled LDP setting, the authors introduce a new notion of privacy called d_sigma-privacy and show it has desirable properties. Along with the new privacy notion they provide an algorithm that achieves it. \nThe paper is very well written, clear, and easy to follow, I appreciate the examples. The paper is relevant since it introduces new and useful ideas in the space of privacy and it has practical applications.\nI did not verify every single proof but what I looked at seemed correct.", "summary_of_the_paper": "This paper studies a variant of Local Differential Privacy with shuffling. Local DP is susceptible to inference attacks by using the order of the data. A way to fix the previous is to do “shuffling”, pool LDP responses, apply a permutation and pass that to the analyst. Shuffling gets rid of inference attacks however it severely hurts data learnability. This paper introduces d_sigma-privacy which provides a “tuning knob” between unshuffled LDP and shuffled DP, which rigorously allows trading off privacy and data learnability. Additionally, the authors provide a very general algorithm that achieve’s d_sigma-privacy and run experiments in some datasets validating their results.", "summary_of_the_review": "The paper is novel and well written. I recommend its acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Vw3-YB3Ga39", "reviewer": "Reviewer_f7JZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The paper deals with an interesting problem of bridging between local DP and shuffling-based global DP using a neighbouring-information based DP framework. As both the models represent two extremes of assuring DP and also lots of real-life data has a local neighbouring structure, it is pertinent problem to study.\n2. The paper proposes to encode the neighbouring information as an undirected graph and use it to define the d_{\\sigma} privacy definition. The definition is intuitive and reasonable. It also yields interesting resilience results against Bayesian and decision-theoretic adversaries. \n3. A shuffling mechanism is proposed to achieve d_{\\sigma} privacy. The mechanism applies Mallow's model while using a heuristic to choose the reference permutation.\n4. The experimental evaluations show utility of this new framework and its functionality to bridge between LDP and unif. shuffling DP, which is the central problem of the paper.\n\nWeakness:\n1. The heuristics used in the proposed privacy preserving mechanism is not well-analysed and well-justified. Depending on the choice of \\sigma_0, the sensitivity can vary exponentially on n or k. Though it is evident that the underlying problem of computing sensitivity is combinatorial and NP-hard, a methodological choice of stable \\sigma_0 is expected to ensure stability of the framework. It would be imperative to empirically or theoretically justify the heuristic for choosing \\sigma_0 and showing it leads to a stable estimate.\n2. How does the privacy level depend on the connectivity of the underlying graph G? For example, how would the privacy level \\alpha would vary if the graph changes from a clique to a chain or a completely disconnected graph? An insight on this will be useful to explicitly understand the dependency on existence of neighbouring structure.\n3. a. What is (\\eta, \\delta) preservation? A formal definition would have been helpful. Also, it seems a bit out of place and confusing in the main paper as it never discussed thereafter. \nb. though an empirical evaluation is proposed in A.14, it is not clear how to choose a good \\eta or \\delta, and what are the corresponding trade-offs.\n4. The images used in the paper are very hard to read. This part of the paper could probably be edited to have a better presentation. Specially from the beginning to the end, I find a gradual decline in readability and presentation.", "summary_of_the_paper": "The paper proposes a neighbouring-information based DP framework to bridge between local DP and shuffling-based global DP. The neighbouring information is represented as undirected graph. Depending on this structure, the concept of neighbouring permutations and d_{\\sigma} privacy is developed. d_{\\sigma} privacy shows interesting resilience results against Bayesian and decision-theoretic adversaries. Further a shuffling mechanism is proposed to achieve this definition. The utility of this framework is validated using experimental evaluations on three datasets.", "summary_of_the_review": "The paper addresses an interesting problem of assuring DP with a novel framework using neighbouring information of data. The results derived for the decision theoretic and Bayesian attackers are useful and provides insights. A mechanism is proposed to achieve this new DP definition but the method seems to be hastily presented and descriptions of certain concepts are unclear. This is the part where the contribution could be improved. The usefulness of the proposed framework is validated through reasonable experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QRUms7IlHaS", "reviewer": "Reviewer_FmCK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The model is interesting and strikes a good balance between LDP and Shuffle model. The experimental section also combines utility with plausibility of inference attacks.\n\nThe motivation behind the model (even though I think the model is nice) is confusing as the main example is that people in one's household can be used to infer a secret of a particular user. But then the approach proposed by the paper is to reveal that the user is part of some group. Cannot just belonging to this group also be used to infer the privacy parameter? That is, it seems the method just changes which group the user belongs to. It would be good to see why it is ok.\n\nThe privacy definition also feel a bit like k-anonymity which is is know to be susceptible to attacks based on belonging to a group. This and above question could probably be answered by providing a more-DP looking definition. That is, can one say you achieve shuffle DP for a group of users? Can one present your definition as a special case of shuffle model and LDP by change \\alpha?\n\nThe technical method in Alg 1 does not take as input privacy parameters. Hence, it seems that a permutation is chosen only based on G. Can this be changed, i.e., get \"more permuted\" data is one increases privacy parameters.", "summary_of_the_paper": "The paper proposes a privacy model in between the guarantees of local DP and shuffle DP. It does so by shuffling each user with a group of \"similar\" users as opposed to all users. As a result, it achieves better utility than LDP. The group that the user belongs to is publicly available, hence the adversary can tell that the user is one of k particular users but not which one. Hence, the \"shuffler\" instead of choosing a random uniform  permutation chooses a permutation that satisfies this per-group shuffle. It is intractable to choose a permutation with these properties, hence the authors propose a heuristic method for choosing such permutation.", "summary_of_the_review": "A very well written paper and nice experimental section.\nThe paper can be strengthened with motivation of the new definition and its (formal) relation to existing definitions.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission. The reviewers agree that this paper provides new contributions to data privacy. In particular, the proposed definition interpolates between the local differential privacy and shuffled differential privacy definitions. As argued in the paper, mechanisms under this framework can prevent certain inferential attacks based on the relationships across the individuals (e.g., which individuals belong to the same household). The paper also provides good evidence that their mechanism guards against a specific type of inferential attacks and provides stronger utility than mechanisms based on uniform shuffling.
Decision: Accept (Poster)