Posthoc privacy guarantees for collaborative inference with modified Propose-Test-Release
Authors: Abhishek Singh
Praneeth Vepakomma
Vivek Sharma
Ramesh Raskar
Venue: NeurIPS 2023 poster (2023)
Keywords: privacy
deep learning
neural networks
adversarial learning
reconstruction guarantees
collaborative inference
MLaaS
TL;DR: We design a framework for guaranteeing privacy of neural networks using mixed integer programming.

Abstract: Cloud-based machine learning inference is an emerging paradigm where users query by sending their data through a service provider who runs an ML model on that data and returns back the answer. Due to increased concerns over data privacy, recent works have proposed Collaborative Inference (CI) to learn a privacy-preserving encoding of sensitive user data before it is shared with an untrusted service provider. Existing works so far evaluate the privacy of these encodings through empirical reconstruction attacks. In this work, we develop a new framework that provides formal privacy guarantees for an arbitrarily trained neural network by linking its local Lipschitz constant with its local sensitivity. To guarantee privacy using local sensitivity, we extend the Propose-Test-Release (PTR) framework to make it tractable for neural network queries. We verify the efficacy of our framework experimentally on real-world datasets and elucidate the role of Adversarial Representation Learning (ARL) in improving the privacy-utility trade-off.

Posthoc privacy guarantees for collaborative inference with modified Propose-Test-Releat
Abhishek Singh', Praneeth Vepakomma', Vivek Sharma 1.2.3,* Ramesh Raskar' MIT Media Lab, 2MGH, Harvard Medical School, 'Sony Al
Abstract
Cloud-based machine learning inference is an emerging paradigm where users query by sending their data through service provider who runs MI model on that data and returns back the answer. Due to increased concerns over data privacy, recent works have proposed Collaborative Inference (CI) to learn privacy- preserving encoding of sensitive user data before it is shared with an untrusted service provider. Existing works so far evaluate the privacy of these encodings through empirical reconstruction attacks. In this work, we develop a new framework that provides formal privacy guarantees for an arbitrarily trained neural network by linking its local Lipschitz constant with its local sensitivity. To guarantee privacy us- ing local sensitivity, we extend the Propose- Rest-ee (PTR) framework to make it tractable for neural network queries. We verify the efficacy of our framework experimentally on real-world datasets and elucidate the role of Adversarial Repre- sentation Learning (A (ARL) in improving the privacy-utility trade-off. The source code and other details are available at (trembler's Z. w...giiiin github. is /pppsthcc
Introduction
While training MI. models privately has seen tremendous progress years, protecting privacy during the inference phase remains elusive as these models get deployed by cloud-based service providers. Cryptographic techniques[43) 31 40 27 address this challenge by computing over encrypted data. To combat the high computational cost of encryption techniques,
45
10 26 in the last few
56 57 have proposed Collaborative Inference (CT) an alternate paradigm where users share a lower dimensional embedding of raw data where task-irrelevan information suppressed. However, CI techniques are currently incompatible with formal privacy frameworks and their evaluation is currently based on empirical reconstruction attacks. The central issue in CI the usage of Deep Neural Networks (DNNs) making unsuitable for formal and worst-case privacy analysis. In this work, we take the first step towards formal privacy framework for CI that will enable more rigorous evaluation and a reliable understanding the CI techniques.
several recent works 66 65
5
The key aspect of any CI algorithm is an obfuscator (typically a DNN), which is trained to encode user's private data such that an attacker can not reconstruct the original data from its encoding. Hence, CI techniques typically evaluate the privacy of their representations by empirically measuring the information leakage using a proxy adversary. However, existing works [57 66 18 56) show that
proxy adversary's 's performance as a measure of protection could be unreliable because a future adversary can come up with a stronger attack. Alternately a few existing CI techniques have used 39 for measuring information leakage empirically. However, most of these works analyze specific obfuscation techniques and lack formal privacy definitions. Therefore, we first introduce privacy definition applicable to CI by adopting a different threat model from that of differential privacy [1] because (as we explain detail in See 2 protecting membership inference is at odds with achieving non-trivial privacy-utilic trade-off in CL.
theoretical tools 20 69 4
68 62
*art of this work was carried out while he was at MIT and MGH, Harvard Medical School.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our threat model for the reconstruction attack is motivated by the intuition that the obfuscator discloses coarse- -rersee-rainddd and filters out fine-graines information for preventing reconstruction. We hypothesize that to do so, the obfuscator should act as a contractive mapping, and as a result, increases the stability of the (obfuscation) function in the local neighborhood of data. We formalize this intuition by introducing a privacy definition in the metric space of data and experimentally validate it in S Our privacy definition is an instantiation of metric-DP by Chatzikokolakis et al. Instead of evaluating the global Lipschitz constant of DNNs, we evaluate the Lipschitz constant only in the local neighborhood of the user's sensitive data. We then extend the Propose- Test- Release (PTR) framework to formalize our local neighborhood based measurement of the Lipschitz constant.
We adopt the PTR framework due to its posthoc and data-adaptive nature - as the privacy of encoding is evaluated in the neighborhood of the private user input and after the obfuscator has been trained. This approach different from conventional privacy mechanisms where the mechanism is fixed and the perturbation does not depend on data. Existing seminal works in data-adaptive privacy such as Propose- Rele-ee (PTR) [1] smooth sensitivity 41 and Lipschitz extensions 488 have exploited this posthoc approach to enhance the utility of the mechanisms. Data adaptive mechanisms are an important area of study as quoted in a recent workshop report on the challenges in Differential Privacy [9] "Going data-adaptive is crucial step in bringing DP algorithms to acceptable level of utility in applications." " In the context of our work the benefit of using the PTR framework is two-fold i) Utility- the obfuscator is expected to behave better samples that match the data distribution from its training dataset are sampled, and ii) Computation instead of computing global sensitivity, we only need to compute sensitivity in the small neighborhood around private data points. While the original PTR is intractable due to a well-known [9] expensive computation step, we design new formulation that substitutes the expensive computation step with tractable alternate.
Computational tractability is generally the main concern that makes CI incompatible with formal privacy because giving worst-case guarantees for obfuscator is generally difficult. While training and convergence guarantees for DNNs remain elusive, we find that the certified robustness community has made rapid progress in the past few years in giving worst-case guarantees during the inference stage of DNNs. Specifically, we utilize recent efficient formulations for the Lipschitz constant computation of DNNs [25] [55]. We measure the stability of the learned obfuscator model using the Lipschitz constant and link it with the local sensitivity under our privacy definition. We bridge the gap between the Lipschitz constant and our extended PTR framework by proposing a binary search algorithm that computes this Lipschitz constant multiple times in the neighborhood of sensitive data. This bridge makes our work amenable any differentiable obfuscator with ReLU non-linearity.
The scope of our paper is to provide privacy guarantees against reconstruction attacks for existing CI techniques, i.e., our goal is not to develop new CI algorithm but rather to develop a formal privacy framework compatible with existing algorithms. A majority of the CI techniques protect either sensitive attribute reconstruction of the input. We only consider sensitive input in this work. Furthermore, we only focus on protecting the privacy of data during the inference stage, and assume that ML models can be trained privately. Our privacy definition and the mechanism are built upon dx-privacy [ and PTR [1]. Existing instantiations of dx-privacy include geo- indistinguishabiliiy (2 and docation-dependen privacy (32 that share a similar goal ours of sharing coarse-grained information. Our work differs because we use DNN queries and high-dimensional datasets. We refer the reader to the supplementary for a detailed literature review.
In See 2 we begin with the preliminaries of DP and its variant for metric spaces. Then, we introduce the privacy definition relevant for CI in Sec 3
Next, we design our framework by extending PTR and proving its privacy guarantees in See 4 In See 5 we experimentally demonstrate the feasibility of our framework. We now give the summary of our contributions:
1. Proposing a privacy defimition that formalizes reconstruction privacy in the context of CL. Protect- ing against membership inference (meaningfully) is not possible in CI and hence traditional DP can not be applied directly as discussed in Sec 2]
2. Extending the (PTRR algorithm to guarantee privacy using the local Lipschitz constant. The stan- dard PTR can not be applied due to its intractability for queries beyond median and mode (see- Page 152, 2nd paragraph of Dwork et al. and Sec 4.
3. Experiments 1) to verify efficacy for both utility and computability, 2) ablation on different design choices, 3) empirical reconstruction attacks, and 4) identifying the role ARL techniques play in improving privacy-utiliy trade-off in CI.
2

---

lagg Space
Trusted Device
Olfasere Space
Untrusted Service Provider
Obfiseator
Peahoc
Pe
Gavdizr
Inforually Privaic
Fornally
Private
Figure 1: Posthoc Privacy framework: We project high dimensional data instance to lower dimensional embedding. The goal of the embedder to measure a semantically relevant distance between different instances. The embedding is fed to the Obfuscator that compresses similar inputs small volume. In traditional ARL, the obfuscated instance shared with the untrusted service provider without any formal privacy guarantee. In this work, by analyzing the stability of the obfuscator network, we perturb the obfuscated instance to provide a formal privacy guarantee.
Preliminaries
Differential privacy 12 is a widely used framework for answering query, f. dataset E X' by applying mechanism M(.) such that the probability distribution of the output of the mechanism M(x) similar regardless the presence absence of any individual in the dataset More formally, M satisfies (c, 5)-DP if Vx, E X such that du (x, x') S 1, and for all (measurable) output S over the range of M
P(M(x) E S) S <<P((M())) E S) +
where dy is the hamming distance. This definition is based trusted central server model, where a trusted third party collects sensitive data and computes M(x) to share with untrusted parties. In DP22), this model has been extended such that each user shares M(x), and the service provider is untrusted. Our threat model is the same as local DP. However, unlike local DP, data is not aggregated over multiple individuals. Specifically, every sample is evaluated independently by the service provider and there is no aggregation involved. For ex.- user shares face image to receive an age prediction from the service provider, here the answer to the query depends exactly on the user's input. With traditional local DP, it is "impossible" to achieve good utility and privacy at the same time because any two samples (no matter how different) are neighboring databases, more formally, du (x, x') < 1, Vx, x' E X for ML inference. Informally, this notion of neighboring databases under the standard DP definition would imply that the outcome for any two samples should be almost indistinguishable
matter how different the samples are. This privacy definition could be too restrictive for our ML inference application where the data instance necessarily needs a certain degree of distinguishability to obtain utility from the service provider. This observation is formalized the impossibility result of instance encoding 7 for private learning. To subside this fundamental conflict between the privacy definition and our application, look the definition of dx-prrivacy [ that generalizes the DP definition to a general distance metric beyond hamming distance as follows:
P(M(x) E S) <
((x(' E S),
(1)
here dx (x, x') a function that gives a level of indistinguishabiiit between two datasets x and x'. DP can be viewed as special case of dx-privacy by keeping dx x') ed (x, x'). Choosing a different distance metric yields a stronger or weaker privacy guarantee. Due the impossibility of achieving both privacy and utility with hamming distance, we move towards a weaker privacy definition by only focusing on achieving privacy against reconstruction attacks instead of membership inference. Intuitively, we choose a distance metric that provides indistinguishability only within neighborhood similar looking samples.
Privacy Definition and Threat Model
To formalize reconstruction privacy, we hypothesize that semantically similar points are close to each other on data manifold, i.e. semantically similar samples are closer in a space where distance is defined geodesic the data manifold. Therefore, one way to bound the reconstruction of

---

is by making it indistinguishable among semantically similar points. The extent of reconstruction privacy would therefore depend upon the radius of the neighborhood. We formalize it with a privacy parameter R that allows user to control how big this indistinguishable neighhorhood should be.
Definition 1. A mechanism M satisfies (e, 6, R)rrcosstririii privacy if Vx, x' E X s.t. dx((x, x') S R and S S Range(M)
P(M(X) E E S <(F(((X)) E S)+ +
(2)
Note that the above equation is exactly the same as (c, 6)-DP except for the definition of neighboring databases. In this way, our privacy definition can be seen as a mix of standard DP and dxx-rrvvac.
3.1 Threat and Attack model
Our threat and attack model is the same as previous collaborative inference works 66 655 Specif- ically, we focus on attackers that aim to reconstruct the original sample from its encoding. That is, given an encoding M(x) obtained from a sample x, an attacker will attempt to recover the original sample (x). Our threat model is the same as local DP. Specifically, all side information including access to the obfuscator model, embedder model, and the framework in Fig known to the adversary and it can interact with them much it wants. The attacker can this information to improve its attack algorithm. We (informally) note that an attacker always has a prior about raw data P(x) and it will update its belief based on the posterior (x)( The goal of our privacy mechanism is to ensure that the distance between the prior and posterior distribution is bounded. Our definition indeed enjoys such interpretation due to being instantiation of dxx-privacy. A more formal description of this Bayesian formulation is given by Chatzikoko laiis et al. in Theorem 4. We emulate such attackers in See 5 by training an ML model on a dataset of M(x) as input and x as output, then we evaluate its reconstruction error on encodings of previously unseen M(x).
3.2 Comparison with Differential Privacy
Conceptually, the usage of hamming distance in DP for neighboring databases provides a level of protection at the sample level. Such privacy requirement can be at odds with the goal of prediction that necessarily requires discrimination between samples belonging to different concept classes. We relax this dichotomy by changing the distance metric to account for reconstruction privacy, Intuitively. an attacker can only obtain an accurate reconstruction of data up to a neighborhood in the space of data. Therefore, the size of the neighborhood is a privacy parameter R such that a higher value of R provides higher privacy. This privacy parameter is equivalent to the group size [12] used often in the DP literature. By default, this value is kept at in DP but can be kept higher if correlated individuals (multiple samples, family) are present in database instead of single individual. We state the equivalence between the group privacy definition and standard DP informally Lemma 2.2 in [60]: Any (e, d)-differentially private mechanism is (Re, Re (R- ()= diifeerrirret private for groups of size R.
This lemma also applies to our proposed definition. However, we emphasize that privacy parameters of (e, 8D mechanism can not be compared trivially with (c, 8, R)reesstttinniinnn privacy mechanism because same value of and 5 provide different levels of protection due to different definitions of neighboring databases. We experimentally demonstrate this claim in Sec.
3.3 Choice of dxx(x, x') and its impact on the privacy guarantees offered
Our privacy definition is an instantiation of dx x') that permits broad class of distance metrics for the privacy definition. Since the goal of our work is to protect against reconstruction L or &g distance
a reasonable choice. However, the space over which norm should be considered is a challenging question. Existing papers have used metrics such & or & norm in the raw data space [21 6 I7 for guaranteeing reconstruction privacy when training ML models. However, for high-dimensional datasets typically considered in CI such as images, guaranteeing reconstruction in ambient dimensions can lead to unintended privacy guarantee. In our work, we consider pre-processing the samples by projecting them into an embedding space, where samples that are semantically closer and farther have norm smaller and higher respectively. We evaluate the privacy-utility trade-off our experiments for both ambient space and embedding space.
4

---

4 Privacy Mechanism
Our goal is design framework that can provide a formal privacy guarantee for encodings informally privatized in CI. However, CI algorithms use non-linear neural networks trained on non-convex objectives making it difficult to perform any worst-case analysis. Therefore, we take posthoc approach where we reason about privacy after the model is trained. Specifically, we apply the PTR mechanism by [T]. Applying PTR directly to our query (ARL) is not computationally feasible because PTR requires estimating local sensitivity at multiple points whereas evaluating the local sensitivity of neural network query is not even feasible at single point. Therefore, we design tractable variant of PTR that utilizes the local Lipschitz constant estimator to compute privacy related parameters. We refer the reader to supplementary for background on the Lipschitz, constant estimation and PTR.
CI algorithms consist of three computational blocks in the training stage: 1) obfuscator (f(-)) that generates an (informally private) representation (ž) of data, 2) proxy adversary that reconstructs the data from the representation produced by the obfuscator, and 3) classifier that performs the given task using the obfuscated representation. The classifier and proxy adversary are trained to minimize the task loss and reconstruction loss, respectively. The obfuscator trained to minimize the task loss but maximize the reconstruction loss. This setup results in a min-max optimization where the tra between task performance and reconstruction is controlled by a hyper- syper-parameter a. Note do not require proxy adversary but still learn an obfuscator that a few CI techniques [2 44 61
model using other regularizers.
At a high level, our framework applies the mechanism M such that the final released data 2 = M(x) has privacy guarantee discussed in Eq Like PTR, we start with a proposal (A),s) on the upper bound of the local sensitivity of x. To test the correctness of ALs. we compute the size of the biggest possible neighborhood such that the local Lipschitz constant of the obfuscator network in that neighborhood is smaller than the proposed bound. Next, we privately verify the correctness of the proposed bound. We do not release the data (denoted by L) if the proposed bound is invalid. Otherwise, we perturb the data using the Laplace mechanism. Next, we discuss the framework and privacy guarantees in more detail.
Global Sensitivity and Lipschitz constant of a query f X + y' are related in the dxxprivacc framework. Global sensitivity of query f(-) is the smallest value of A (if it exists) such that Vx, E X. (x), S Axx(xx x')). While global sensitivity is a measure over all possible pairs of data in the data domain X, local sensitivity (AL.)) is defined with respect to a given dataset such that Vx E X, (x)). fxx)) S ALS (x)xxxxx
We integrate the notion of similarity in a neighborhood (motivated in 2ec by defining the local sensitivity of neighborhood N(x, R) around x of radius R where N(x, R) = fx (x|dx(xx, x') < R. Vx' E X).. Therefore, the local sensitivity of query on x in the R-neighborhood is defined Vx E N N((x, R) such that
dy(f(x), f(x)) S A L.S (x, Rx,x(xxx')
(3)
We note that if dx is hamming distance and R is then this formulation is exactly same local sensitivity in 12]. The equation above can be re- re-written as:
dx(f(x),f(x')) xx(xxx))
ALS(X,R)
sup x'EV(x.R)
(4)
This formulation of local sensitivity is similar to the definition of the local Lipschitz constant. The local Lipschitz constant L of f for a given open neighborhood / C X' is defined as follows:
II((x) f(x")lla |I 1x'-x"1X x"1
Ca.9(f. = sup x' X'X"EN
(x'xx")
(5)
We note that while the local sensitivity of x is described around the neighborhood of x, the Lipschitz constant is defined for every possible pair of points in a given neighhorhood. Therefore, in Lemma we show that the local Lipschitz in the neighborhood of x is an upper bound on the local sensitivity.
Lemma 4.1. For a given ff and for dy + la and dx + La. A S (x). Proof in Supplementary.
Since local sensitivity upper bounded by the Lipschitz constant, evaluating the Lipschitz constant suffices an alternative to evaluating local sensitivity.
5

---

Lower bound on testing the validity of Ls: The PTR algorithm [T] suggests a proposal on the upper bound (A) of local sensitivity and then finds the distance between the given dataset (x) and the closest dataset for which the proposed upper bound is not valid. Let 7(-) be a distance query and A (x) be the local sensitivity defined as per the DP framework with respect to x such that
7 (xx
min {d (x, x') s.t. ALS(X') Ass).
(6)
x' x'EX'
For our privacy definition, the query (x, R) can be formulated as follows:
7xx, R) min {dx (x) 8.l. Ars(x',) > A.s) x'EX
We note that keeping dx des and R 1, makes the y query exactly same as defined in the c Generally, computing 7(-) is intractable due to local sensitivity estimation required for every x' X' (which depends upon a non-linear neural network in our case). We emphasize that this step is intractable at two levels, first, we require estimating the local sensitivity of neural network query. Second, we require this local sensitivity over all samples in the data domain. Therefore, make it tractable by computing lower bound over (xx, R) by designing a function <(-) s.t. 6(x, R) S (xx R). Intuitively, o(.) finds the largest possible neighborhood around x such that the local Lipschitz constant of the neighborhood is smaller than the proposed local sensitivity. Because the subset of points around x whose neighhorhood does not violate 4% is half of the size of the original neighborhood in the worst case, we return half of the size of neighborhood the output. We describe the algorithm procedurally in the supplementary material. More formally,
1 arg max s Lss R22R
Φ(x, R) 2
If there is no solution to the equation above, then we return O.
Lemma 4.2. o(x, S (x,, R). Proof in Supplementary.
The next step in the PTR algorithm requires testing if 7xx) S Privately testing the lower bound:
(e)) If the condition is true, then no-answer (.) is released instead of data. Since the 7y query depends upon x. PTR privatizes it by applying laplace mechanism, i.e. f(x) = query has sensitivity of since the y could differ at most by I for any two neighboring databases. In our framework, we compute Φxx, R) to lower bound the value of 7(x, R). Therefore, we need to privatize the á query. We prove that for distance metrics in dx-privacy, the global sensitivity of the ((x) query is 1.
The
Lemma 4.3. The query d(-) has global sensitivity of 1, i.e. Vx, E X, dataaa R), o(x (xx S dx(x, x'). Proof in Supplementary.
After computing Rxx,R), add noise sampled from laplace distribution, i.c. 0(x, R) = o R) Lap(R/e). Next, we check if $(x, R) I In(+)) R/e, then we release 1, otherwise we release 2 [()())) + Lap(A).s/e)) Next, we prove that the mechanism Mi described above satisfies reconstraction-privvey
Theorem 4.4. Mechanism Mi satisfies uniform (2c, reccosstuttnn privacy Eq. Vx, x X, &. dx(xxx') < R
2 i.e.
5)+ 5
P(M(X) S) 5 Se e
(8)
Proof Sketch: Our proof is similar to the proof for the PTR framework 12] except the peculiarity introduced due to our metric space formulation. First, we show that not releasing the answer (L) satisfies the privacy definition. Next, we divide the proof into two parts, when the proposed bound is incorrect (i.e. (Ls(x, R) > Aiss) and when it is correct. Let R be the output of query ø.
P(O(x, R) = R2]
exp( [d(x.R) R .e))
R
Plo(x', R) exp
- 10(x' RR E))
R
< <exp(lo(x' R) (6xx S S exp(dx (x,x) { eep((e
R
R

---

MNIST
FMNIST
30, 0.781)
UTKFace
0.0.002)
35, 0.732)
Informal
Informal
Informal
Encoder
0.93
0.428
0.673
0.883
0.921
0.779
0.228
0.355
0.605
0.722
0.724
0.617
0.673
0.717
0.721
ARL
0.917
0.329
0.532
0,792
0.882
0.747
0.214
0.319
0.557
0.685
0.71
0.605
0.649
0.691
0.707
0.926
0.443
0.684
0.881
0.917
0.781
0.158
0.225
0.442
0.608
0.73
0.623
0.673
0.718
0.724
N
0.923
0.279
0.496
0.816
0.902
0.559
0.136
0.177
00310
0.462
0.725
0.614
0.667
0,708
0.715
ARL-C
0.896
0.424
0.648
0.839
0.883
0.761
0.196
0.314
0.537
0.682
0.709
0.632
0.684
0.70
0.705
ARL-N
0.88
0.118
0.139
0.21
0.325
0.717
0.294
0.467
0.665
0.705
0.71
0.628
0.674
0,701
0.708
C-N
0,929
0,353
0.574
0.844
0,913
0.774
0.161
0.224
0.441
0.599
0.727
0.616
0.671
0.712
0.722
ARL-C-N
0.921
0.514
0.751
0.891
0.912
0.706
0.371
0.554
0.678
0.695
0.712
0.690
0.700
0.700
Table 1: Performance comparison for different baselines: Our posthoe framework enables com- parison between different obfuscation techniques by fixing the privacy budget (c). First four rows different approaches protect against data reconstruction and the remaining rows below are combinations of different approaches. The top row refers to the accuracy corresponding to different datasets under two extremes of epsilons. ARL refers widely used adversarial representation learn- ing approach for regularizing representation based on a proxy attacker [35] 38 65 [6). Contrastive refers to contrastive learning based informally privatizing mechanism introduced
44
Therefore, using the post-processing property- P[M(x) 11 S M(x = 1]. Here, the first inequality is due to triangle inequality, the second one is due to Lemma 4.3 and the third inequality Therefore, the
follows from dx(xx, x') S R. Note that when (x,((x, R) A Ls. o ((x, R) probability for the test to release the answer in this case is
P[M(X) * 1 = Pio(x, R) - Lap( R
1
R 1 = P[Lap( { > log(z) 1 R
log
L.s for Based on the CDF of Laplace distribution, P[M(x) + -1= $.. Therefore, if A R) > Ai.s any S [ TRd U L in the output space of .M
P(M(x) E (M((()) E E (-)) P[ ESN (R*)]
S <EPIM(x') E (LL F(M * S EPP(( E S] +
If (x, R) < Ai then the mechanism is composition of two (e, 6, R, R)-reconstruction private algo- rithm where the first algorithm (ø(x, R)) is 6/2 ()22,R)-reche reconsttttiiii private and the second algorithm is (e, O, Re-reoonstrrction private. Using composition, the algorithm is (2e, 8/2, R) R)-reconstruucton private. We describe M1 step by step in the algorithm in supplementary. To summarize, we designed the posthoc privacy framework that extends the PTR framework by making it tractable to get (c, ó, R)- reconstruction privacy. The exact local Lipschitz constant of the neural network based obfuscator is estimated using mixed-integer programming based optimization developed by (25).
Our key idea is to add extra computation the client side to turn informally private representations to their formal counterpart. This extra computational cost is due to the estimation of the local Lipschitz constant of the obfuscator network. However, the following two factors of our framework make it practically feasible-
Computational feasibility:
1. We compute the local Lipschitz constant (i.c. in a small neighborhood around a given point): Our extension of the propose-test-relass framework only requires us to operate in a small local neighborhood instead of estimating the global Lipschitz constant which would be much more computationally expensive.
2. Low number of parameters for obfuscator: Instead of estimating the Lipschitz constant of the whole prediction model, we only require estimation of the obfuscator a neural network that has significantly lower number of parameters in comparison to the prediction model.
We experimentally validate both of the above benefits in Sec 5
The fact that the local Lipschitz constant is being computed over the same obfuscator allows room for optimizing performance by caching. Our goal is to demonstrate the feasibility of bridging formal privacy guarantees and CI mechanisms, hence, we did not explore such performance speedups.
7

---

12 layer
layer
10 layer
3.5
layer
layer
3.0
layer
Runtime
Runtime
1.5
1.0
64
128
256
512
1024
2048
0.062
0.125
0.5
2
Input Dimensions
Radius
Figure 2: Runtime evaluation of local lipschitz computation for different (a) neighborhood radius, (b) input dimensions, and (c) number of layers. While the runtime increases exponentially with dimensions, it plateaus with increase in neighborhood radius. Since the input dimensions are same as embedding dimensions it makes the algorithm favorable our analysis.
Experiments
We evaluate different aspects of our proposed framework i) E1: comparison between different adversarial appraches, ii) E2: comparison with local differential privacy (LDP), ii) E3: computational tractability of our proposed framework, and iv) E4: investigating role of ARL in achieving privacy. We use MNIST All of them contain samples with high ambient dimensions (MNIST-784, FMNIST-784 and UTKFaae- 4096). We use a deep CNN based 3-VAE [2) for the pre-processing. We use Lip.Mip 25 for computing Lipschitz constant over foo baselines include a simple Encoder that projects the data to smaller dimensions using a neural network. This encoder type approach has been used in the literature Split Learning
Experimental Setup:
2MNIST(64 and UTKFaae 67 dataset for all experiments.
in the input space and é, in the output space. Our
[19] We include widely used ARL techniques [65] 56. 38 35 66) and adversarial contrastive learning g 44 which we denote as We use noisy regularization (denoted by N) improve classifier performance. We refer the reader to supplementary for detailed experimental setup, codebase, and
E1: Privacy-Utility Trade-off: Since framework enables comparison between different obfusca- tion techniques under same privacy budget, we evaluate test set accuracy as utility in Table [ Our results indicate that ARL complemented with contrastive and noise regularization helps in attaining overall best performance among all possible combinations.
E2: Comparison between ARL and LDP: While e-LDP definition provides a different privacy guarantee than our proposed privacy definition, for reference we compare the performance between LDP and CI and report results in supplementary. We note that for low values of LDP techniques do not yield any practical utility. This corroborates with the impossibility result of instance encoding [ and our discussion in See about the inapplicability of traditional DP in the context of CI.
E3: Computational feasibility: We report end-to-end runtime evaluation on CPU-based client and achieve 2 sec/image (MNIST) and 3.5 sec/image (UTKFace). While plenty of room exists for optimizing this runtime, we believe current numbers serve as reasonable starting point for providing formal privacy in ARL. As discussed in Sec 4 we compare the computation time of the obfuscator across three factors relevant our setup i) Dimensionality of the input, ii) Size of the neighborhood, and iii) Number of layers in the Obfuscator. We report the results in Fig. 2
E4: What role does ARL play in achieving privacy? We investigate the contribution adversarial training in improving the privacy-utility trade-off. We train obfuscator models with different values of a (weighing factor) for adversarial training. Our results in Fig indicate that higher weighing of adversarial regularization reduces the local Lipschitz constant, hence reducing the local sensitivity of the neural network. Furthermore, for high values of a, the change in the local Lipschitz constant reduces significantly for different sizes (R) of the neighborhood. These two observations can potentially explain that ARL improves reconstruction privacy by reducing the sensitivity of obfuscator. However, as we observe in Table [ the classifier can reduce its utility if ARL is not complemented with noisy and contrastive regularization. We believe this finding could be of independent interest the adversarial defense community.

---

Local lipachitz constant
15
0.59
(0,0.5, 0.99,,
0.3.0.4.3,......
Figure 3: Local sensitivity comparison for different values of a: The five bars for each a represent different neighborhood radii Increase in the value of a decreases the local Lipschitz constant (upper bound on local sensitivity) indicating lesser amount of noise to be added for the same level of privacy,
6 Discussion
How to select privacy parameter R? One of the key difference between (e, 6, R) neighborhood privacy and (e, 8D-DP is the additional parameter R. The choice of R depends upon the neighborhood in which a user wishes to get an e level of indistinguishabiiit. We discussed the equivalence of R and l in group Differential Privacy in Sec 3.2 To understand the role of R. we perform reconstruction attacks on privatized encoding obtained from our framework by training an ML model to reconstruct original images. We compare reconstruction results for different values of e and R on four distinct metrics for images and report in Supplementary. To assess the level of indistinguishability. we project the original images into embedding space and sample points from the boundary of neighborhoods of different R. We observe that as the boundary of the neighborhood increases, the images become perceptually different from the original image. For extremely large radii, the images change significantly enough that their corresponding label may change too. Such visualizations can be used to semantically understand different values of How to propose Ai.s Our framework requires a proposal on the upper bound of local sensitivity in a private manner. One possible way to obtain AL. is by using the Lipschitz constant of training data samples used in training the obfuscator. We choose Ais by computing the mean (/)) and standard deviation (a)) of local sensitivity on the training dataset (assumed be known under our threat model), then we keep AL. = + a where n allows trade-off between the likelihood of releasing the samples under PTR and adding extra noise to data. We used empirically, the value of local sensitivity appears to be following a gaussian, using confidence interval serves as good proxy. Fig[] that for higher values of a, the variability the local Lipschitz constant decreases indicating the validity of the bound would hold for large number of samples. Limitations: i) Since we utilize the PTR framework, outlier samples may not get released due to high sensitivity, this is expected since these outlier samples are likely to be misclassified anyway. ii) Lipschitz constant computation is limited to ReLU based DNNs, therefore more sophisticated obfuscator architectures are currently not compatible with proposed framework and we leave it as part of the future work. iii) Choosing the privacy parameter (R) could be challenging for certain datasets and might vary based on user preferences. We believe the choice of such parameter would depend upon the context in which CI is being applied.
in our experiments. Since
7 Related Work
Collaborative Inference techniques aim to learn a task-oriented privacy preserving encoding of data. Majority of the works in this area either protect against sensitive attribute leakage 20 [0] [5] 36) or input reconstruction [52] 56 39
35 38 These techniques usually evaluate their privacy using empirical attacks since the mechanism is learned using gradient based min-max optimization making it infeasible for the worst-case privacy analysis. The problem is exacerbated in the context of input reconstruction because of the lack of formal definition for reconstruction privacy. The goal of our work is to create a framework that make the existing techniques amenable to formal privacy analysis.

---

While theoretical analyses 668 69 51 of ARL objectives have identified fundamental trade-off's between utility and attribute leakage, they are difficult to formalize as a worst-case privacy guarantee especially for deep neural networks.
Privacy definitions that extend the DP definition incorporate some of its restrictions 29 include dx-Privacy [8]. and Pufferfish [30]. Our privacy definition is specific instantiation of the dx- Privacy 8 framework that extends DP general metric spaces. Our instantiation is focused on reconstruction privacy for individual samples instead of membership inference attacks [3] Existing works in DP for reconstruction attacks [6 58 focus on protecting training data from an attacker that has access to model weights (whitebox attacker) or output of model queries (blackbox attacker). In contrast, our work only focuses on the privacy of the data used during the prediction stage and not training data.
Lipschitz constant estimation for neural networks has been used to guarantee network's stability perturbations. Existing works either provide an upper bound 6$] 33 14, exact Lipschitz constant [25]
224 or Lipschitz constant regularization [53] [23] during the training stage. Some existing works have explored the relationship between adversarial robustness and DP model training [46, 47 [59] We utilize similar ideas of perturbation stability but for privacy. Shavit and Gjura [54] use Lipschitz
neural networks [16] to learn private mechanism design for summary statistics such as median, however their mechanism design lack privacy guarantee.
Posthoc approach to privacy applies privacy preserving mechanism a data dependent manner. Smooth sensitivity [4]] and PTR [11] reduce the noise magnitude because the local sensitivity is only equal to global sensitivity in the worst case and not average case. Privacy odometer [49], Ex-post privacy loss 37 and Rényi privacy filter [15 track privacy loss the query is applied over data. Our works builds upon the PTR framework in order to give high privacy for less sensitive data. However, as we show in Sec 4 our framework reformulates the PTR algorithm make it tractable under our
setup.
8 Conclusion
In this work we take first step towards bridging empirical techniques in ARL and formal privacy mechanisms. The posthoc nature of our framework allows reasoning about privacy without any modification to the obfuscation algorithm, hence, making it easy to integrate for benchmarking existing and future techniques. We introduced a privacy definition that formalizes ARL and designed corresponding privacy mechanism. An exciting future direction for extending our framework is to integrate NNs for designing more effective privacy mechanisms for other sophisticated queries exciting area in DP and our improvement to PTR can
beyond CI. Data adaptive mechanisms be potentially applied for other queries where PTR might be intractable currently.
9 Acknowledgements and Disclosure of funding
We thank Mohammad Mohammadi Amiri for his valuable feedback on the early draft. This work is supported by NSF award number 1729931.
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Miguel E Andrés. Nicolás E Bordenabe, Konstantinos Chatzikokolakis, Catuscia Palamidessi. Geo- indistinguishabiitt:: Differential privacy for location-based systems. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 901-914, 2013.
[3] Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1138 1156. IEEE, 2022.
[4] Yuksel Ozan Basciftci, Ye Wang, and Prakash Ishwar. On privacy- utility tradeoff's for constrained data release mechanisms. In 2016 Information Theory and Applications Workshop (ITA), pages 1-6. IEEE, 2016.
10

---

[5] Martin Bertran, Natalia Martinez, Afroditi Papadaki. Qiang Qiu, Miguel Rodrigues, Galen Reeves, and Guillermo Sapiro. Adversarially learned representations for information obfuscation and inference. In International Conference on Machine Learning, pages 623. PMLR, 2019.
[6] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protection against reconstruction and applications in private federated learning. arXiv preprint arXiv: 1812009444 2018.
[7] Nicholas Carlini, Samuel Deng. Sanjam Garg, Somesh Jha, Saeed Mahloujifar Mohammad Mahmoody, Shuang Song, Abhradeep Thakurta, and Florian Tramer. Is private learning possible with instance encoding? arXiv preprint arXiv:20I 1.2001110000 150315, 2020.
[8] Konstantinos Chatzikokolakis, Miguel E Andrés. Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metries. In International Symposium Privacy Enhancing Technologies Symposiun, pages 82-102. Springer, 2013.
[9] Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geambasu, Matthew Jagielski, Yangsibo Huang, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, et al. Challenges towards the next frontier in privacy. arXiv preprint arXiv:2304.0692,, 2023.
[10] Jian Du, Song Li, Moran Feng, and Siheng Chen. Dynamic differential-privacyy preserving sgd, arXiv preprint arxi: 1,00173, 2021.
[11] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium Theory of computing, pages 2009.
[12] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):21 1-407, 2014.
[13] Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman. Exposed! survey of attacks on private data, Annual Review of Statistics and Its Application, 4:61-84, 2017.
[14] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[15] Vitaly Feldman and Tijana Zrnie Individual privacy accounting via a renyi filter. Advances in Neural Information Processing Systems, 34, 2021.
[16] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. arxiv e-prints, page. arXiv preprint arXiv:1804.00 8088004000....00 2018.
[17] Chuan Guo, Brian Karrer. Kamalika Chaudhuri, and Laurens van der Maaten. Bounding training data reconstruction in private (deep) learning. In International Conference on Machine Learning, pages 8056-8071. PMLR, 2022.
[18] Hao Guo, Brian Dolhansky, Eric Hsin, Phong Dinh, Cristian Canton Ferrer, and Song Wang. Deep poisoning: Towards robust image data sharing against visual disclosure. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 686-696, 2021.
[19] Otkrist Gupta and Ramesh Raskar. Distributed learning of deep neural network over multiple agents. Journal of Network and Computer Applications, 116:1-8, 2018.
[20] Jihun Hamm. Minimax filter: Leaminng to preserve privacy from inference attacks. The Journal of Machine Learning Research, 18(1):400444334 2017.
[21] Awni Hannun. Chuan Guo, and Laurens van der Maaten, Measuring data leakage in machine-learning models with fisher information. In Uncertainty Artificial Intelligence, pages 760-770. PMLR, 2021.
[22] Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerehner. beta-vae: Learning basic visual concepts with constrained variational framework. 2016.
[23] Yujia Huang, Huan Zhang, Yuanyuan Shi, J Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local lipschitz bounds. Advances in Neural Information Processing Systems, 34, 2021.
[24] Matt Jordan and Alex Dimakis. Provable lipschitz certification for generative models. In International Conference on Machine Learning, pages
PMLR, 2021.
11

---

[25] Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. Advances in Neural Information Processing Systems, 33:7344-7353, 2020.
[26] James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. In International conference on learning representations, 2018.
[27] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. (GAZELLE): low latency framework for secure neural network inference. 27th USENIX Security Symposium (USENIX Security 18), pages 1651-1669 2018.
[28] Shiva Prasad Kasiviswanathan, Homin K Lee. Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-824 2011.
[29] Daniel Kifer and Ashwin Machanavajjhala. No free lunch in data privacy. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 193-204, 2011.
[30] Daniel Kifer and Ashwin Machanavajihala Pufferfish: A framework for mathematical privacy definitions. ACM Transactions Database Systems (TODS). 39(1):136, 2014.
[31] Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. Crypten: Secure multi-party computation meets machine learning. Advances in Neural Information Processing Systems, 34, 2021.
[32] Fragkiskos Koufogiannis and George J Pappas. Location-dependee privacy. In 2016 IEFE 55th Conference on Decision and Control (CDC), pages 7586-7591. JEEE, 2016.
[33] Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. arXiv preprint 2xXiv2200400666 2020.
[34] Yann LeCun. The mnist datahase of handwritten digits. http://yaan.. lecun. com/exdh/nmistl, 1998.
[35] Ang Li, Jiayi Guo, Huanrui Yang, Flora D Salim, and Yiran Chen. Deepobfuscator: Obfuscating intermediate representations with privacy-preserving adversarial learning smartphones. In Proceedings of the International Conference ofternet-of Design and Implementation, pages 28 39, 2021.
[36] Yitong Li, Timothy Baldwin, and Trevor Cohn. Towards robust and privacy text representations. arXiv preprint / 06093, 2018
[37] Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z Wu. Accuracy first: Selecting differential privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems, 30, 2017.
[38] Sicong Liu, Junzhao Du, Anshumali Shrivastava, and Lin Zhong, Privacy adversarial network: represen- tation learning for mobile data privacy. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 314):1-18, 2019.
[39] Fatemehsadat Mireshghallah, Mohammadkazem Taram, Ali Jalali, Ahmed Taha Taha Elthakeh, Dean Tullsen, and Hadi Esmacilzadeh. Not all features are equal: Discovering essential features for preserving prediction privacy. Proceedings of the Web Conference 2021. pages 669-680 2021.
[40] Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng, and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In 29th USENIX Security Symposium (USENIX Security 20), pages 2505-2522, 2020.
[41] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75-84, 2007.
[42] Scong Joon Oh, Rodrigo Benenson, Mario Fritz, and Bernt Schiele. Faceless person recognition: Privacy implications in social media. European Conference on Computer Vision, pages 19 19-35. Springer, 2016.
[43] Olga Ohrimenko, Felix Schuster, Cédric Fournet, Aastha Mehta, Schastian Nowozin, Kapil Vaswani, and Manuel Costa. Oblivious (Multi-Party) machine learning on trusted processors. In 25th USENIX Security Symposium (USENIX Security 16), pages 619-636, 2016.
[44] Seyed Ali Osia, Ali Shahin Shamsabadi, Sina Sajadmanesh, Ali Taheri, Kleomenis Katevas, Hamid Rabiee, Nicholas D Lane, and Hamed Haddadi. A hybrid deep learning architecture for mobile analytics. IEEE Internet of Things Jourmal, 755):5005 4518, 2020.
12

---

[45] Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Supi-supee knowledge transfer for deep learning from private training data. arXiv preprint urXiv:1610.05755, 2016.
[46] Hai Phan, My T Thai, Han Hu, Ruoming Jin, Tong Sun, and Dejing Dou. Scalable differential privacy with certified robustness adversarial learning. In International Conference on Machine Learning, pages 7683-7694, PMLR, 2020.
[47] Rafael Pinot, Florian Yger, Cédric Gouy-Pailler, and Jamal Atif. A unified view on differential privacy and robustness to adversarial examples. arXiv preprint arXiv:1906.07900 2019.
[48] Sofya Raskhodnikova and Adam Smith. Efficient lipschitz extensions for nighdimensiioal graph statistics and node private degree distributions. arXiv preprint 1rXfv:150..07122 2015.
[49] Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: Pay-as- you-go composition. Advances in Neural Information Processing Systems, 29, 2016.
[50] Proteek Chandan Roy and Vishnu Naresh Boddeti. Mitigating information leakage in image representations:
A maximum entropy approach. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2586-2594, 2019.
[51] Bashir Sadeghi and Vishnu Boddeti. On the fundamental trade-off's in learning invariant representations. arXiv preprint MXii:2/09.033880 2021.
[52] Mohammad Samragh, Hossein Hosseini, Aleksei Triastcyn, Kambiz Azarian, Joseph Soriaga, and Farinaz Koushanfar. Unsupervised information obfuscation for split inference of neural networks. arXiv preprint arXiv:2104.11413. 2021.
[53] Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: Analysis and efficient estimation. In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, page 3839-3848, Red Hook, NY, USA, 2018. Curran Associates Inc.
[54] Yonadav Shavit and Boriana Gjura. Exploring the of lipschitz neural networks for automating the design differentially private mechanisms. 2019.
[55] Zhouxing Shi, Yihan Wang, Huan Zhang, Zico Kolter, and Cho-Jui Hsieh. Efficiently computing local lipschitz constants of neural networks via bound propagation. Advances in Neural Information Processing Systems, 35:2350-2364, 2022.
[56] Abhishek Singh, Ayush Chopra, Ethan Garza, Emily Zhang. Praneeth Vepakomma, Vivek Sharma, and Ramesh Raskar. Disco: Dynamic and invariant sensitive channel obfuscation for deep neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12125- 12135, 2021.
[57] Brij Mohan Lal Srivastava, Aurélien Bellet, Mare Tommasi, and Emmanuel Vincent. Privacy-preserving adversarial representation learning in asr: Reality or illusion? arXiv preprint 191iv:191 1.04913, 2019.
[58] Pierre Stock, Igor Shilov, Ilya Mironov, and Alexandre Sablayrolles. Defending against reconstruction attacks with r) enyi differential privacy. arXiv preprint arXiv:2202.07623, 2022.
[59] Nurislam Tursynbek, Aleksandr Petiushko, and Ivan Oseledets. Robustness threats of differential privacy. arXiv preprint 20Xiv:2012.07826 2020.
[60] Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347-450. Springer, 2017.
[61] Praneeth Vepakomma. Abhishek Singh, Emily Zhang. Otkrist Gupta, and Ramesh Raskar. Sopeek-infers Preventing face reconstruction attacks in distributed inference after on-premise training. In 2021 16th IEEE International Conference on Automatic Face and Gesture Recognition (FG 2021), pages 1-8. IEEE, 2021.
[62] Ye Wang, Yuksel Ozan Basciftci, and Prakash Ishwar. Privacy-utility tradeoff's under constrained data release mechanisms. arXiv preprint 1w.:::70000000000000 2017.
[63] Lily Weng, Huan Zhang, Hongge Chen. Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pages 5276-5285. PMLR, 2018.
[64] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
13

---

[65] Taihong Xiao, Yi-Hsuan Tsai, Kihyuk Sohn. Manmohan Chandraker. and Ming- -suan Yang. Adversarial learning of privacy-press preserving and lask-oriented representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1-44411144, 2020.
[66] Mengda Yang. Ziang Li. Juan Wang, Hongxin Hu, Ao Ren, Xiaoyang Xu, and Wenzhe Yi. Measuring data reconstruction defenses collaborative inference systems. In Alice Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL https://opents
ew. net forum 2 U ryyuu
[67] Zhifei Zhang. Yang Song, and Hairong Qi. Age progressionneegrssionn by conditional adversarial autoen- coder. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2017.
[68] Han Zhao, Jianfeng Chi, Yuan Tian, and Geoffrey Gordon. Trade-off' and guarantees adversarial representation learning for information obfuscation. Advances in Neural Information Processing Systems, 33:9485 94966,99926222 2020.
[69] Han Zhao, Chen Dan. Bryon Aragam, Tommi S Jaakkola, Geoffrey J Gordon, and Pradeep Ravikumar, Fundamental limits and tradcoff's in invariant representation learning. arXiv preprint arXiv:2012 2020.
14


Reviews:
[{"review_id": "YA5yWFgkcm", "reviewer": "Reviewer_uj9h", "summary": "This paper is concerned with the development of privacy-preserving collaborative inference. A collaborative inference framework allows users to create a privacy-preserving encoding of their data, which in turn can be used in place of real private inputs when interacting with machine learning-based services. The promise of privacy-preserving collaborative inference is that an adversary observing an encoding should not be able to recover the original input or a sensitive attribute of the original input. The authors propose a new framework to formally evaluate the privacy guarantees of such an encoding against reconstruction attacks that seek to recover the original input.", "questions": "Please provide more discussion on the following elements\n\t- applicability to tabular data\n\t- the robustness of the framework to adversaries that have white-box access to the obfuscator\n\t- comparison of CI-based approaches to other secure inference techniques relying on secure multiparty computation and homomorphic encryption", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "\n- The paper made several technical improvements to render the proposed solution useful in practice\n- The proposed solution has been evaluated extensively ", "weaknesses": "\n- Lack of discussion on the following items:\n\t- applicability of the framework to tabular datasets\n\t- guarantees of the proposed approach if the adversary has white box access to the obfuscator\n- The paper focuses on collaborative inference as a solution for input privacy at inference time. The related work on secure inference could benefit from discussions on other approaches such as secure multi-party computation and homomorphic encryption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the feedback. We address the three main discussion points brought up by the reviewer below -\n\n**Application to tabular data** - Our framework is agnostic to the data modality. From the point of view of privacy, the input needs to be a vector so that it can be privatized by an obfuscator. From a utility point of view, the obfuscation model should have low sensitivity.\n\n**The robustness of the framework to adversaries with white-box access to the obfuscator** - Our threat model assumes the adversary has white-box access to the obfuscator as discussed in Sec 3.1 and hence the privacy guarantees hold equally well.\n\n**Comparison between CI and secure inference techniques** - Thanks for pointing this out. We will update our Related Work section with a more detailed discussion and references to secure inference techniques.\nSecure inference[1,2,3,4] provides a high level of privacy (that is every bit in the input data is almost completely indistinguishable to an attacker from a randomly generated bit). However, as the computation performed by the service provider gets more sophisticated, it comes at the expense of higher computation and communication costs.\n\nIn contrast, CI is computationally cheaper and does not incur any extra communication costs. However, CI offers less privacy as the input sample is only indistinguishable in a neighborhood around the input.\nCI is also more flexible because secure inference techniques need infrastructure implemented by the service provider, but obfuscation methods are user-controlled. Furthermore, shared embeddings in CI are in the plaintext space and hence amenable to additional analysis such as downstream training as performed in Split Learning and Vertical Federated Learning.\n\n**References** -\n1. Wagh, Sameer, Divya Gupta, and Nishanth Chandran. \"Securenn: Efficient and private neural network training.\" Cryptology ePrint Archive (2018).\n2. Lou, Qian, et al. \"Falcon: Fast spectral inference on encrypted data.\" Advances in Neural Information Processing Systems 33 (2020): 2364-2374.\n3. Reagen, B., Choi, W.S., Ko, Y., Lee, V.T., Lee, H.H.S., Wei, G.Y. and Brooks, D., 2021, February. Cheetah: Optimizing and accelerating homomorphic encryption for private inference. In 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA) (pp. 26-39). IEEE.\n4. Lee et al., 2022, June. Low-Complexity Deep Convolutional Neural Networks on Fully Homomorphic Encryption Using Multiplexed Parallel Convolutions. In International Conference on Machine Learning (pp. 12403-12422). PMLR."}, {"review_id": "RSRJyvyFrK", "reviewer": "Reviewer_MzZs", "summary": "This paper proposes a method for evaluating the privacy guarantees provided through adversarial representation learning. More precisely, the framework proposed is built on the Propose-Test-Release paradigm (PTR) as well as the d_x-privacy metric. The primary objective is to be able to characterize the privacy risks in terms of reconstruction against the adversarial representation at inference time.", "questions": "-It would be helpful to understand the limits of differential privacy if the authors could discuss in a bit more details the impossibility results of instance encoding (reference 7).\n\n-Please see also the weaknesses section. ", "limitations": "Ok.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and the authors have a done job at explaining the limits of previous works on assessing the security of adversarial representation learning. However, the definition of the Lipschitz constant should also be part of the main body of the paper rather than being in the supplementary material.\n\nThe move from differential privacy to d_x-privacy enables to make the estimation of the local sensitivity tractable, which circumvents some of the limits of the PTR framework. \n\nThe proposed approach is tested on three diverse datasets and the results obtained demonstrate that it is comparable in performance to other methods from the state-of-the-art.", "weaknesses": "There are several possible way to implement a LDP mechanism. I suggest to the authors to mention which one they have implemented (for instance is it randomized response) and also to try a different one to see if the results they obtained are dependent or not of the particular mechanisms evaluated.\n\nEven if the focus of the current approach is to prevent reconstruction attack, I suggest to also perform additional experiments to measure the success of membership inference attacks. This would help to fully characterize the privacy-utility trade-off of the proposed method. \n\nA few typos :\n-« hamming distance » -> « Hamming distance »\n-« laplace mechanism » -> « Laplace mechanism »\n-The following sentence should be completed : « as we show in Sec ?? »", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and address the concerns as follows -\n\n**LDP mechanisms and limits of differential privacy** - We note that our LDP experiment is only for the purpose of illustrating the gap in utility. The protection by LDP is so high that it is unreasonable to expect any utility (as we discuss below) in the context of Collaborative Inference (CI). Having said that, our LDP implementation is based on the Laplace mechanism with clipping. In order to bound the sensitivity of a sample we clip each dimension within a fixed range and add Laplace noise to the sample based on its sensitivity (clipping range and dimensions).\nA majority of the LDP mechanisms (such as randomized response, CountSketch, etc.) are designed for aggregation queries like count, mean, etc. However, in CI we only have a single sample over which post-processing (classifier) is applied and the answer is returned to the user.\n\nThis also leads to the impossibility of applying DP directly in this context as DP would require the obfuscated embedding from any two samples to be indistinguishable (up to $e^\\epsilon$) while the task of classification requires samples belonging to different classes to be distinguishable. A stronger version of this claim is given in instance encoding that says a dataset of such obfuscated embeddings can either have high utility or high privacy but not both. We address this impossibility by changing the metric space from hamming (as traditionally done in DP) to a general metric and using an l-norm ball around the input such that any two samples within that l-norm ball are indistinguishable. For example - Igamberdiev and Habernal apply LDP for Privatized Text Rewriting – a classification task, and hence, they had to use extremely large epsilons (around 200) to achieve a reasonable utility. We will make sure to include a more detailed discussion in the extra page of the camera-ready version.\n\n**Comparison with membership attacks** - We believe a membership attack is not possible because aggregate statistics are not shared. Specifically, a membership inference attack would require access to an aggregate statistic (such as mean or a ML model) and the attacker would have to guess whether a given sample was used to compute that statistic. In contrast, a low-dimension projection of a private input is shared. In that view, there isn’t any “model” to query for membership inference.\n\n**References** -\nTimour Igamberdiev and Ivan Habernal. 2023. DP-BART for Privatized Text Rewriting under Local Differential Privacy. In Findings of the Association for Computational Linguistics: ACL 2023, pages 13914–13934, Toronto, Canada. Association for Computational Linguistics."}, {"review_id": "oWKmXcrB0H", "reviewer": "Reviewer_ybRi", "summary": "A method is proposed to encode inputs to a server that performs inference, to limit the ability of the service provider to infer detailed information about the input. A formal privacy guarantee, inspired by differential privacy, quantifies the amount of leakage. This metric is related to the local Lipschitz constant, which relation is used in the test of a propose-test-release mechanism to ensure local privacy.", "questions": "What are some concrete applications where a user would reasonably be satisfied with the specific type of privacy afforded by this approach?", "limitations": "Limitations are discussed. No potential negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The concepts introduced are original as far as I know and the exposition is mostly clear. ", "weaknesses": "The primary weakness in my opinion is in the practical utility of the proposed method. If I understand correctly, the method does not provide local differential privacy (indeed the authors argue this is impossible for a system designed to return useful classification or functions of the input) but merely prevents the inference of detailed information. Specifically, it attempts to obfuscate any information that is not necessary for the task. It seems to me much of the time this would not guarantee \"privacy\" in the sense that most people would want. Suppose for example that we are working with linguistic input. Maybe it is a question answering service, or machine translation. Users of a purportedly private system would expect that the service would not have access to (not be able to examine or log) the specific question being answered, or the text being translated. Clearly that is incompatible with providing sufficient utility-- something like holomorphic encryption or trusted execution environments would be needed for that. So I think the paper would be stronger if it were motivated with some concrete applications where a user would reasonably be satisfied with the specific type of privacy afforded by this approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We agree that tasks which require granular information from data such as translation would not be possible with collaborative inference approaches. However, plenty of use cases exist where all the information is not necessarily required to produce an answer. These uses-cases typically produce a significantly smaller dimensional output for high dimensional input. Examples include -\n\n- Image, Graphs, or Text classification tasks - A significant amount of information can be thrown away while still being able to compute the answer.\n- Vector databases for language model - With the improved performance of language models, several use cases for vector databases have arisen such as document retrieval, product recommendation, etc. For example - Authors of [1] tried to apply privacy to classification tasks by using traditional local DP, and hence, they had to resort to extremely large epsilons (around 200) to achieve a reasonable utility. We believe such a technique could benefit from the privacy definition proposed in our work.\n\n**References** -\n1. Timour Igamberdiev and Ivan Habernal. 2023. DP-BART for Privatized Text Rewriting under Local Differential Privacy. In Findings of the Association for Computational Linguistics: ACL 2023, pages 13914–13934, Toronto, Canada. Association for Computational Linguistics."}, {"review_id": "hAOJF8YMU9", "reviewer": "Reviewer_UmFA", "summary": "The paper proposed to protect data privacy in collaborative inference settings.  Specifically, the paper presents a formal way to capture the obfuscation of an image using adversarial representation learning, a well-studied technique. The paper does so by using a metric-based differential privacy notion. Since the metric is difficult to compute, the paper proposes a way to estimate Lipschitz constant using an estimation technique from DP. ", "questions": "My big concern is that the threat model requires knowing the classifier (by the obfuscator/defender) which makes it unable to protect all attacks and impracticable in many cases. For instance, the data owner has a stringent requirement about his data privacy, e.g., not \n letting the defender knows the learning task.  In other words, when knowing the classifier, why would the data owner send his data for classification to the server in the first place?\n\n“most of these works analyze specific obfuscation techniques and lack formal privacy definitions” This claim seems inaccurate. \nFor instance,  Zhao et al. 2020a indeed showed formal privacy guaranteed information leakage. What are the key differences? How do you compare your theoretical results with theirs?\n\nTable 1 shows that ARL-C-N is even worse than Encoder in several cases. Why does this happen? How can you claim that ARL-C-N performs the best among all baselines? \n\nTwo recent works [a,b] propose advanced attacks against ``representation learning” based defense. I would like to see the performance of the proposed ARL-C-N .  \n\n[a] Song et al., Overlearning reveals sensitive attributes. In ICLR, 2020\n[b] Balunovic et al., Bayesian framework for gradient leakage. ICLR’22\n\nBalle et al. [c] also showed theoretical results on data reconstruction via DP technique. What are the key technical differences?  \n\n[c] Balle et al., “Reconstructing training data with informed adversaries,” in IEEE SP, 2022.\n\n", "limitations": "Yes. ", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ The studied problem is important \n\n+ The paper is easy to follow \n\n+ Formal privacy guarantees ", "weaknesses": "- Threat model is unrealistic\n- Lack of evaluation against advanced attacks\n- More clarifications are needed\n- Experimental result is not convincing\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We respectfully disagree with several points mentioned by the reviewer and have tried our best to address those by quoting them inline.\nFirst, we would like to clarify “collaborative inference” as studied in several existing papers[1-5] including ours.\nIn collaborative inference, an embedding from an intermediate layer is shared by a client to a server and several existing works have proposed (informally private) obfuscation techniques to prevent these embeddings from input reconstruction attacks. Our work presents a framework to give a formal privacy guarantee for these obfuscation techniques.\n\n**My big concern is that the threat model requires knowing the classifier (by the obfuscator/defender)**\n\nThe threat model does not require the defender to know the classifier. In fact, threat models (including ours) do not impose any restriction on defenders, they only focus on the capability of the adversary.\n\n**why would the data owner send his data for classification to the server in the first place?**\n\nThere isn’t any strict requirement for the data owner to know the classifier. It is the training of the obfuscator that requires access to the classifier. However, such training can be performed by the service provider or a third party. We would like to emphasize that our work only focuses on inference and not training.\n\nA typical use-case for collaborative inference is that a cloud-based service provider company has a model which they want their users to query with their private data. However, the user can not run it on their own device (either due to the model size or the proprietary nature of the model). Therefore, the cloud-based service provider gives the end user an obfuscator so that it can share its obfuscated data with the service provider.\n\n**How do you compare your theoretical results with Zhao et al.2020a?**\n\nZhao et al. 2020a study attribute obfuscation. In contrast, we study reconstruction attacks over the input data. We highlighted this important distinction in line 73 by stating -\n> A majority of the CI techniques protect either a sensitive attribute or reconstruction of the input. We only consider sensitive input in this work.\n\nIn contrast, quoting Zhao et al. on Page 3, Lines 3 and 4 -\n\n> To simplify the exposition, we mainly discuss the setting where $X \\subseteq R^d$, $Y = A = \\{0, 1\\}$, but the underlying theory and methodology could easily be extended to the categorical case as well.\n\nTherefore, they study binary (and categorical) sensitive attributes. Hence, Attribute Inference Advantage (their privacy definition) can not be extended to reconstruction privacy in the input space of data.\n\n**Table 1 shows that ARL-C-N is even worse than Encoder in several cases. Why does this happen? How can you claim that ARL-C-N performs the best among all baselines?**\n\nARL-C-N is generally better than other techniques (best performing for 8 out of 12 combinations of datasets and privacy budgets). However, we agree this statement should be made more precisely. The “Informal” column is just for reference and shouldn’t be considered formally private. Considering that, the encoder is only higher than ARL-C-N for $\\epsilon=10$ (except $\\epsilon=5$ in UTKFace). This is due to the high local sensitivity of the Encoder (bad for privacy-utility trade-off) that gets discounted when the epsilon value is high.\n\n**Two recent works [a,b] propose advanced attacks against ``representation learning” based defense. I would like to see the performance of the proposed ARL-C-N.**\n\nWe would like to clarify that ARL-C-N is not our proposed technique and is simply yet another defense mechanism. We have evaluated three popular classes of collaborative inference techniques – ARL[2,3,4], C[5], and N[6]. ARL-C-N is an ablation where all three regularizations are active. We have ablated all 2^3 combinations in the experiments and ARL-C-N is one of them. Song et al. attack focuses on inferring sensitive attributes while our attack is about reconstructing the input data from its embedding during inference. However, both attacks use supervised learning to train an attacker, and hence the training algorithm for the attacker is the same as the one we employed in Table 2 of the supplementary.\n\nWhile Balunovic et al. attack representation learning techniques, their attacks rely on access to gradients because they focus on Federated Learning. In contrast, gradients are not involved at all in our context because we focus on Collaborative Inference.\n\n**Balle et al. [c] also showed theoretical results on data reconstruction via the DP technique.**\n\nBalle et al. are also out of scope from our line of work. Their focus is on reconstructing training data by accessing the parameters of a trained model. Quoting the first line of their abstract -\n> Given access to a machine learning model, can an adversary reconstruct the model’s training data?\n\nIn contrast, we study the problem of reconstruction attacks over input data during the inference (not training) stage.\n\nReferences\n1. Yang, Mengda, et al. \"Measuring Data Reconstruction Defenses in Collaborative Inference Systems.\" Advances in Neural Information Processing Systems 35 (2022): 12855-12867.\n2. Singh, Abhishek, et al. \"Disco: Dynamic and invariant sensitive channel obfuscation for deep neural networks.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.\n3. Xiao, Taihong, et al. \"Adversarial learning of privacy-preserving and task-oriented representations.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 07. 2020.\n4. Osia, Seyed Ali, et al. \"A hybrid deep learning architecture for privacy-preserving mobile analytics.\" IEEE Internet of Things Journal 7.5 (2020): 4505-4518.\n5. Mireshghallah, Fatemehsadat, et al. \"Not all features are equal: Discovering essential features for preserving prediction privacy.\" Proceedings of the Web Conference 2021. 2021."}]

Author rebuttal:

Meta-review: Most reviewers agreed that the paper should be accepted, although there were some common points of confusion that the authors should clarify in the final version. In particular, they should emphasize that only the privacy of data provided during inference, and not the privacy of training data, is protected by their mechanism.
Decision: Accept (poster)