In this work we introduce a new protocol for vector aggregation in the context of the Shufle Model, a recent model within Diferential Privacy (DP). It sits between the Centralized Model, which prioritizes the level of accuracy over the secrecy of the data, and the Local Model, for which an improvement in trust is counteracted by a much higher noise requirement. The Shufle Model was developed to provide a good balance between these two models through the addition of a shufling step, which unbinds the users from their data whilst maintaining a moderate noise requirement. We provide a single message protocol for the summation of real vectors in the Shufle Model, using advanced composition results. Our contribution provides a mechanism to enable private aggregation and analysis across more sophisticated structures such as matrices and higher-dimensional tensors, both of which are reliant on the functionality of the vector case. Diferential privacy (DP), single-message shufle model, local randomizer, randomized response, mean squared error (MSE).
[2], a one-time data collection model where trices. It is important to use matrix reduction to eneach of users is permitted to submit a single message. sure that the constituent vectors are linearly indepen
definition of privacy that guarantees a measurable level of confidentiality for any data subject in the dataset to which it is applied. In this way, useful collective information can be learned about a population, whilst simultaneously protecting the personal information of each data subject.
In particular, DP guarantees that the impact on any particular individual as a result of analysis on a dataset is the same, whether or not the individual is included in the dataset. This guarantee is quantified by a parameter , which represents good privacy if it is small. However, ifnding an algorithm that achieves DP often requires a trade-of between privacy and accuracy, as a smaller sacrifices accuracy for better privacy, and vice versa. DP enables data analyses such as the statistical analysis of the salaries of a population. This allows useful collective information to be studied, as long as is adjusted appropriately to satisfy the definition of DP. (C. Maple)
links to Federated Learning and Secure Aggregation. CEUR htp:/ceur-ws.org ISN1613-073 © 2021 Copyright for this paper by its authors. Use permitted under Creative
Message Shufle Model in Federated Learning, where multiple users collaboratively solve a Machine Learning problem, the results of which simultaneously improves the model for the next round [3]. The updates generated by the users after each round are high-dimensional vectors, so this data type will prove useful in applications such as training a Deep Neural Network to predict the next word that a user types [4]. Additionally, aggregation is closely related to Secure Aggregation, which can be used to compute the outputs of Machine Learning problems such as the one above [5].
messages, extending an existing result from Balle et al. [2] by permitting the users to each submit a vector of real numbers instead of a scalar. The resulting estimator is unbiased and has normalized mean squared error (MSE) , ( 8/3 −5/3), where is the dimension of each vector.
dent. This problem can be extended further to higherdimensional tensors, which are useful for the representation of multi-dimensional data in Neural Networks.
a dataset focused on simple ways of suppressing or generalising the data. Examples include -anonymity [6], diversity [7] and -closeness [8]. However, such attempts have been shown to be insuficient, as proved by numer
users This harmful leakage of sensitive information can be to submit more than one message, using several indeeasily prevented through the use of DP, as this mathependent shuflers to securely compute the sum. In this matically guarantees that the chance of a linkage attack work, Balle et al. contributed a recursive construction on an individual in the dataset is almost identical to that based on the protocol from [2], as well as an alternative on an individual not in the dataset.
has focused on two opposing models. In the Centralized
tion directly to a trusted central data collector, who adds mechanism which implements a discretized distributed noise addition technique using the result from Ishai et
al. [18], which explored the related problems of private frequency estimation and selection in a similar context, random noise to the raw data to provide DP, before as- drawing comparisons between the errors achieved in the sembling and analyzing the aggregated results.
In the Local Model, DP is guaranteed when each user similar team of authors produced a follow-up paper [19] applies a local randomizer to add random noise to their data before it is submitted. The Local Model difers from describing a more eficient protocol for private summation in the Single-Message Shufle Model, using the ‘inthe Centralized Model in that the central entity does not visibility cloak’ technique to facilitate the addition of see the users’ raw data at any point, and therefore does zero-sum noise without coordination between the users. not have to be trusted. However, the level of noise required per user for the same privacy guarantee is much higher, which limits the usage of Local Diferential Privacy (LDP) to major companies such as Google [10], Apple [11] and Microsoft [ 12].
provide a good balance between the trust of the central entity and the level of noise required to guarantee DP.
intermediate models that reap the benefits of both.
In 2017, Bittau et al. [13] introduced the Encode, Shuflfe, Analyze (ESA) model, which provides a general framework for the addition of a shufling step tocol. After the data from each user is encoded, it is randomly permuted to unbind each user from their data before analysis takes place. In 2019, Cheu et al. [14] formalized the Shufle Model as a special case of the ESA model, which connects this additional shufling step to the Local Model. In the Shufle Model, the local randomizer applies a randomized mechanism on a per-element basis, potentially replacing a truthful value with another randomly selected domain element. The role of these independent reports is to create what we call a privacy blanket, which masks the outputs which are reported truthfully.
domains , , and apply them to input datasets ,⃗ ⃗ ′ to generate (vector-valued) messages ⃗ , ⃗′. We write [] = {1, … , } and ℕ for the set of natural numbers. 3.1. Models of Diferential Privacy
come of the mechanism applied to that dataset.
troduced after the users’ inputs are gathered by a (trusted) aggregator. Consider a dataset ⃗ ′ that difers from ⃗ only in the contribution of a single user, denoted ⃗≃ ⃗ ′.
mechanism ℳ ∶ → is (, ) -diferentially private if ∀ ⃗≃ ⃗ ′, ∀ ⊆ :
Pr[ℳ ()⃗ ∈ ] ≤ ⋅ Pr[ℳ (⃗ ′) ∈ ] + [ 9].
in a private pro- ⃗= ( ⃗ 1, … , ⃗ ) does not have much efect on the outment that the contribution ⃗ of a user to a dataset
As well as the result on the private summation of scalar- tor obtains the raw data from all users and introduces valued messages in the Single-Message Shufle Model that we will be using [2], Balle et al. have published two more recent works that solve related problems. The the necessary perturbations.
randomness on their input ⃗ ∈ by using a local ranifrst paper [ 15] improved the distributed -party summa- domizer ℛ ∶ → to obtain a perturbed result ℛ( ⃗). tion protocol from Ishai et al. [16] in the context of the
(1 + / log ) scalar-valued messages, instead of a logarithmic dependency of ( log + ) , to achieve statistical security 2− .
private if ∀,⃗ ⃗ ′, ∀ ⊆ : ′
Pr[ℛ(⃗) ∈ ] ≤ ⋅ Pr[ℛ(⃗) ∈ ] + [ 2], where ⃗′ ∈ is some other valid input vector that could hold. The Local Model guarantees that any observer will
Algorithm 1: Local Randomizer ℛ,, Public Parameters: ∈ [0, 1], domain size , and number of parties Input: ∈ [] Output: ∈ [] Sample ← Ber( ) if = 0 then let ← else sample ← Unif([]) return not have access to the raw data from any of the users.
3.2. Single-Message Shufle Model
Centralized and Local Models of DP [2]. Let a protocol in the Single-Message Shufle Model be of the form = (ℛ, ) , where ℛ ∶ → is the local randomizer, and ∶ → ℤ is the analyzer of . Overall, implements a mechanism ∶ → ℤ as follows. Each user independently applies the local randomizer to their 4.1. Basic Randomizer message ⃗ to obtain a message ⃗ = ℛ( ⃗). Subsequently, the messages ( ⃗1, … , ⃗ ) are randomly permuted by a First, we describe a basic local randomizer applied by each trusted shufler ∶ → . The random permutation user to an input ∈ []. The output of this protocol is a ( ⃗ 1, … , ⃗ )is submitted to an untrusted data collector, (private) histogram of shufled messages over the domain who applies the analyzer to obtain an output for the []. mechanism. In summary, the output of ( ⃗ 1, … , ⃗ )is The Local Randomizer ℛ,, , shown in Algorithm 1, given by: applies a generalized randomized response mechanism that returns the true message with probability 1 − ∘ ∘ ℛ ( )⃗ = ( (ℛ( ⃗ 1), … , ℛ(⃗))). and a uniformly random message with probability .
Note that the data collector observing the shufled mes- Single-Message Shufle Model for scalar-valued messages, sages ( ⃗ 1, … , ⃗ )obtains no information about which as well as in several other previous works in the Local user generated each of the messages. Therefore, the pri- Model [20, 21, 22]. In Section 4.3, we find an appropriate vacy of relies on the indistinguishability between the to optimize the proportion of random messages that are shufles ∘ ℛ ()⃗ and ∘ ℛ ( ⃗ ′)for datasets ⃗≃ ⃗ ′. submitted, and therefore guarantee DP. The analyzer can represent the shufled messages as a We now describe how the presence of these random histogram, which counts the number of occurrences of messages can form a ‘privacy blanket’ to protect against the possible outputs of . a diference attack on a particular user. Suppose we apply
3.3. Measuring Accuracy a subset of approximately of these users returned a uniformly random message, while the remaining users In Section 4 we use the mean squared error to compare returned their true message. Following Balle et al. [2], the overall output of a private summation protocol in the the analyzer can represent the messages sent by users in Single-Message Shufle Model with the original dataset. by a histogram 1 of uniformly random messages, and The MSE is used to measure the average squared difer- can form a histogram 2 of truthful messages from users ence in the comparison between a fixed input ( )⃗ to not in . As these subsets are mutually exclusive and the randomized protocol , and its output ( )⃗ . In this collectively exhaustive, the information represented by context, MSE( , )⃗ = E[( ( )⃗ − ( )⃗) 2], where the the analyzer is equivalent to the histogram = 1 ∪ 2. expectation is taken over the randomness of . Note Consider two neighbouring datasets, each consisting of messages from users, that difer only on the inwhen E[ ( )⃗] = ( )⃗ , MSE is equivalent to variance, put from the th user. To simplify the discussion and i.e.: subsequent proof, we temporarily omit the action of the MSE( , )⃗ = E[( ( )⃗ − E[ ( )⃗])2] = Var[ ( )⃗]. shufler. By the post-processing property of DP, this can be reintroduced later on without adversely afecting the privacy guarantees. To achieve DP we need to find an 4. Vector Sum in the Shufle Model appropriate such that when Algorithm 1 is applied, the change in is appropriately bounded. As the knowledge In this section we introduce our protocol for vector sum- of either the set or the messages from the first − 1 mation in the Shufle Model and tune its parameters to users does not afect DP, we can assume that the anaoptimize accuracy. lyzer knows both of these details. This lets the analyzer remove all of the truthful messages associated with the
Algorithm 2: Local Randomizer ℛ,,, Public Parameters: , , dimension , and number of parties Input: ⃗ = ( Output: ⃗ = ( (1), … ,
() ( 1), … , ) ∈ [0, 1] ( )) ∈ {0, 1, … , } return ⃗ = ( ( 1), … ,
( )) Sample ( 1, … , ) ←Unif([]) Let ̄ ▷ ̄ ▷ ( ): apply Algorithm 1 to each ̄ appropriately ‘hides’ . ifrst − 1 users from .
If the th user is in , this means their submission is independent of their input, so we trivially satisfy DP.
Otherwise, the (curious) analyzer knows that the th user has submitted their true message . The analyzer can remove all of the truthful messages associated with the ifrst −1 users from , and obtain 1∪{ }. The subsequent privacy analysis will argue that this does not reveal if is set so that 1, the histogram of random messages, 4.2. Private Summation of Vectors
dress the problem of computing the sum of real vectors, each of the form ⃗ = ( (1), … , () ) ∈ [0, 1], in the Single-Message Shufle Model. Specifically, we analyze the utility of a protocol ,,, = (ℛ,,, , ,, )for this purpose, by using the MSE from Section 3.3 as the accuracy measure. In the scalar case, each user applies the protocol to their entire input [2]. Moving to the vector case, we allow each user to independently sample a set of 1 ≤ ≤ coordinates from their vector to report. Our analysis allows us to optimize the parameter .
Hence, the first step of the Local Randomizer ℛ,,, , presented in Algorithm 2, is to uniformly sample coordinates ( 1, … , ) ∈ [] (without replacement) from each vector ⃗ . To compute a diferentially private approximation of ∑ ⃗ , we fix a quantization level . Then ℳ = ∘ ℛ ,,, is (, ) -DP for any , , ∈ ℕ , { ∈ ℕ | ∈ []} , < 6 and ∈ (0, 1]such that: 56 log(1/) log(2/) , see the users in (i.e., the subset of users that returned a uniformly random message), as well as the inputs from the first − 1 users.
We now introduce the vector view VViewℳ()⃗ as the collection of information that the analyzer is able to see after the mechanism
ℳ is applied to all vector-valued messages in the dataset ⃗ . VViewℳ()⃗ is defined as the tuple ( ⃗, ⃗ ∩, ⃗) , where ⃗ is the multiset containing the outputs { ⃗1, … , ⃗ } of the mechanism ℳ()⃗ , ⃗ ∩ is the vector containing the inputs ( ⃗1, … , ⃗−1 )from the ifrst − 1 users, and ⃗ contains binary vectors (⃗1, … , ⃗ ) which indicate for which coordinates each user reports truthful information. This vector view can be projected to overlapping scalar views by applying Algorithm 2 only to the th uniformly sampled coordinate ∈ [] from each user, where ∈ [] . The th scalar view Viewℳ of VViewℳ()⃗ is defined as the tuple ( ⃗( ), ⃗ ∩ are the analogous definitions of ⃗, ⃗ ∩ and ⃗, but containing only the information referring to the th uniformly sampled coordinate of each vector-valued message.
used in our setting to get a tight upper bound: ifes Theorem 4.2 (Dwork et al. [9]). For all ′, ′, ≥ 0 , the class of ( ′, ′)-diferentially private mechanisms satis(, ′ + ) -diferential privacy under -fold adaptive composition for: = √2 log(1/ ) ′ + ′( ′ − 1).
Corollary 4.3. Given target privacy parameters 0 < < 1 and > 0 , to ensure (,
′+ ) cumulative privacy loss over mechanisms, it sufices that each mechanism is ( ′, ′)-DP, where: ′ =
2√2 log(1/ ) 1–10 (2) suficient to derive ( 1) from:
Pr
V lary 4.3, which states that the use of overlapping ( ′, ′)
applies in our setting, since we have assumed that VViewℳ()⃗ satisfies the requirements of (, ) -DP, and that each of the overlapping scalar views is formed identically but for a diferent uniformly sampled coordinate of the vector-valued messages.
remains to show that for a uniformly sampled coordinate ∈ [], Viewℳ ( )()⃗ satisfies ( ′, ′)-DP.
Lemma 4.5. Condition (2) holds.
cover the additional case 1 ≤ < 6 . This will be suficient to complete the proof of our main Theorem 4.1.
First, we scale the setting of ′ by a multiple of 6 in Corollary 4.3 so that the advanced composition property holds for all 1 ≤ < 6 . We now insert ′ = into the proof of Theorem 4.1, resulting in a change of 12√2 log(1/) constant from 56 to 2016. 4.4. Accuracy Bounds for Shufled Vector
Sum
protocol, and then identify the value(s) of that minimize this upper bound.
First, note that encoding the coordinate used with expectation / . Therefore, we define the normalized MSE, or M̂SE, as the normalization of the MSE by a factor of (/) 2.
Theorem 4.6. For any , ∈ ℕ , { ∈ ℕ | ∈ []} , < 6 and ∈ (0, 1], there exists a parameter such that ,,, is (, ) -DP and
M̂SE( ,,, ) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎩ 2 8/3(14 log(1/) log(2/)) 2/3
(1− ) 2 5/3 4/3 there is an (, ) -DP -party unbiased protocol for estimat∑ ( ⃗ ) in the Single-Message Shufle Model with , { ∈ ℕ | ∈ []} , < 6 and ∈ (0, 1], ̂ (,,, ) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎩ (2) 1/2 4/3(14 log(1/) log(2/)) 1/3
(1− ) 5/6 2/3 , where
̂de notes the error between the estimated average vector and the true average vector.
tocol for the computation of the sum of real vectors in the Single-Message Shufle Model with normalized MSE , ( 8/3 −5/3), using advanced composition results from Dwork et al. [9]. Minimizing this bound as a function of leads us to choose = 1 , but any choice of that is small and not dependent on produces a bound of the same order. In our experimental study, we determine com- that the best choice of in practice is indeed = 1 . then Var[ ] ≤ ( − ) 2/4, and so the MSE To obtain the error between the estimated average per coordinate due to the fixed-point approximation of vector and the true average vector, we simply take the , , 2 where M̂SE denotes the squared error between the estimated average vector and the true average vector.
Proof. We consider the ∑=1 DeBias( ̂())of ,,, pared to the corresponding input ∑=1 the dataset ⃗ . We use the bounds on the variance of the randomized response mechanism from Theorem 4.6 to give us an upper bound for this comparison.
∑ =1 ( ) over MSE( ,,, ) =sup E[(∑ DeBias( ̂()) −∑ ∑ =1 =1
2 ( )) ] = sup E[(∑ ∑(DeBias( ( )/) − ( ))) ] = sup ∑ ∑ E[(DeBias( ( )/) − ( ))2 ] = sup ∑ ∑ Var[DeBias(
( )/) ] sup Var[ 1 ( 1)/] ≤
(1 − )2 ( 1 − 4 2 + ) 2 log(1/ ) log(2/ )
⃗ =1 =1 ⃗ =1 =1 (1 − )2 1 ( 1) 1 (1 − )2 4 2 +
( where = 28 when < 1 , and = 1008 when 1 ≤ < 6. In other words, is equal to half the constant term in the expression of stated in Theorem 4.1. The choice above and the bounds in the statement of the theorem minimizes the bracketed sum 4.5. Improved bounds for t=1 We observe that in the optimal case in which = 1 , we can tighten the bounds further, as we do not need to invoke the advanced composition results when each user samples only a single coordinate. This changes the value of by a factor of ( log(1/ )), which propagates through to the expression for the MSE. That is, we can more simply set ′ = and ′ = in the proof of Theorem 4.1. the condition ′ < 1 no longer holds.
≥ 1′42 log(2/ ) being chosen as before. However, when 1 ≤ < 6 , a tighter ≥ 8′02 log(2/ ) must be selected, as Using ′ < 6, we have: (1 −exp (− ′/2)) ≥(1 − exp (− )) ′ ≥ 2 3√15 N N
(a) Experimental error by number of coordinates retained (b) Experimental error by number of buckets used
Note that the above expression for in the case < 1 //www.kaggle.com/shayanfazeli/heartbeat. We analyse coincides with the result obtained by Balle et al. in the the efect of changing one key parameter at a time, whilst scalar case [2]. Putting this expression for in the proof the others remain the same. Our default settings are of Theorem 4.6, with the choice vector dimension = 100 , rounding parameter = 3 , = ⎨⎩⎧mmiinn{{((12680 lolog2g(22(2//))))11//33, ,((5 14712 )1)/13/}3, }, wwhheenn 1<≤1 < 6, saanadnumjdmupsblte=eerd=0ot.of51ub,.seaesnTrtdshdedisi=freparlean5ny0gt0eit0ash0leopfd,rienavplualemcnpybdapreeaarnrmcaoimefetscee,otrweosrrhshdiali snvt=aestieb0ms.e9eut5noltaneously ensuring that the parameter of the randomcauses the upper bound on the normalized MSE to reduce ized response mechanism is always within its permitted to: range of [0, 1 ]. The Python code is available at https: //github.com/mary-python/dft/blob/master/shuffle.
M̂SE = ⎪⎪⎩⎨⎧⎪⎪mmaaxx{{ww298hh18/(/(ee1313nn(−−281))/03<l22o≤log155g(//2233<//344)(//6)233/.2)/3 ,, ((11−−2))(1229825/5//3833)/((34181)/3)2/23/3},}, w(aHashe)Wpaesrrhneteobdfirwe=isactstt1ectC,dohacnabtotfireymmgthtophertaheirztaeoartdettaistotluhoneletaxDscnpahoyetforaoiiSscmteeehtceetoinrisfotsasnmilg4Man̂.l5il=Sfic.vEaIna1nfltoduliyreesetsoodhmfp,eatF.iElimlgCe.raG1l,
By updating Corollary 4.7 in the same way, we can M̂SE is lowest when = 3 , which is suficiently close to conclude that for the optimal choice = 1 , the normal- the choice of selected in the proof of Theorem 4.6, with ized standard deviation of our unbiased protocol can be all other default parameter values substituted in. Observe further tightened to: that the absolute value of the observed MSE is below 0.3 in this case, meaning that the vector is reconstructed to a ⎧max{981/6 4/3 log1/3(2/) , 181/2 4/3 high degree of accuracy, suficient for many applications. ̂ ⎪⎪⎪⎨⎪⎩=max{ww21hh/2ee(1nn(4−/131−)( <2)≤051/l5o6/<g62(/2236//.3)) 1/3(1,−( 1)−2 )15//269(54/16/)(311/143/)3}1,/3 }, wTtsouhirtNethphoerierxisesqtim,sunuawgpt4leiey.o6r,nv.ltiehnaFreeiimgfaMy.ru2StldthEi(epeapi)lneebincosordufepenalnods8cet/stes3e.o,adfesMxwae8ic/agtt3hnolyweaasanhbsduieldpese,t−asFc5fitiri/cgce3oud.rf.r2drvUio(nembng)ifts a curve dependent on −7/6, suficiently close to the required result. We see the benefit of increasing : as 5. Experimental Evaluation increases by a factor of 10 across the plot, the error decreases by more than two orders of magnitude. In Fig. 3, we verify the dependency −4/3 in the two ranges < 1 and 1 ≤ < 6 . The behavior for < 1 is quite smooth,
(a) Experimental error by vector dimension (b) Experimental error by number of vectors used
sums to provide a protocol ,,, in the Single-Message
messages ( ⃗1, … , ⃗ ) ∈ ([0, 1]) . It is not surprising that the normalized MSE of the resulting estimator has a dependence on −5/3, as this was the case for scalars, but the but becomes more variable for larger values. addition of a new dimension introduces a new depen
In conclusion, these experiments confirm that picking dency for the bound, as well as the possibility of sampling = 1 and = 3 serves to minimize the error. The lines coordinates from each -dimensional vector. For this of best fit confirm the dependencies on the other param- extension, we formally defined the vector view as the eters from Section 4 for , and , by implementing and knowledge of the analyzer upon receiving the randomapplying Algorithms 2 and 3 to an ECG Heartbeat Catego- ized vectors, and expressed it as a union of overlapping rization Dataset in Python. The experiments demonstrate scalar views. Through the use of advanced composition that the MSE observed in practice is suficiently small to results from Dwork et al. [9], we showed that the estimaallow efective reconstruction of average vectors for a tor now has normalized MSE , ( 8/3 −5/3)which can suitably large cohort of users. be further improved to , ( 8/3 −5/3)by setting = 1 .
6. Conclusion tween the summation of the scalar case discussed by
structures such as matrices and higher-dimensional tensors, both of which are reliant on the functionality of the vector case. As mentioned in Section 2, there is potential for further exploration in the Multi-Message Shufle
paper of Balle et al. [17].
.
We observe that the counts ( ) and ( ) follow the binomial distributions N ∼ Bin(, )+ 1 and N ∼ Bin(, respectively, where denotes the number of times that the coordinate is sampled. In expectation, = ( − 1)/ , and below we will show that it is close to its expectation: ) Pr
V = Pr[ ≥ ′].
N N
N N [ of two events, ≥ ′/2 and ≤ − ′/2. Applying a ⋅ and split this into the union Pr[ ≥ ′] ≤ exp(−
( ′/2 − 1 − + exp(− (1 − − ′/2)2) .
We will choose ≥ 1′42 log(2/ ) so that we have: exp ( ′/2) − 1 −
≥ 1 ′ 2 + ′2 8 −
′2 14 log(2/ ) ≥ ′ 2 .
Using ′ < 1, we have: (1 −exp (− ′/2)) ≥ (1 −exp (−1/2))′ ≥
N N
exp(−E()/3), using E() = ( − 1)/ : Pr[ ≥ 2 E()] ≤exp ( − / ) ≤ exp ( − ) < /3, 2 3 3