FED-χ: SECURE FEDERATED CORRELATION TEST
Year: 2021

Abstract:
In this paper, we propose the first secure federated χ-test protocol, FED-χ. We recast χ-test as a second frequency moment estimation problem and use stable projection to encode the local information in a short vector. As such encodings can be aggregated with summation, secure aggregation can be applied to conceal the individual updates. We formally establish the security guarantee of FED-χ by demonstrating that the joint distribution is hidden in a subspace containing exponentially possible distributions. Our evaluation results show that FED-χ achieves good accuracy with small client-side computation overhead. FED-χ performs comparably to the centralized χ-test in several real-world case studies. The code for evaluation is in the supplementary material.

heading: 1 INTRODUCTION
text: Correlation test, as the name implies, is the process of examining the correlation between two random variables using observational data. It is a fundamental building block in a wide variety of real-world applications, including feature selection (Zheng et al., 2004), cryptanalysis (Nyberg, 2001), causal graph discovery (Spirtes et al., 2000), empirical finance (Ledoit & Wolf, 2008; Kim & Ji, 2015), medical studies (Kassirer, 1983) and genomics (Wilson et al., 1999; Dudoit et al., 2003). Because the observational data used in correlation tests may contain sensitive information such as genomic information, centralizing the data collection is risky. To address, we resort to a federated setting in which each client maintains its own data and communicates with a centralized server to calculate a function. Note that the communication should contain as little information as feasible. Otherwise, the server may be able to infer sensitive information from the communication transcript.
In the present work, we study a representative correlation test, namely χ2-test, under the federated setting. There are two straightforward methods for conducting χ2-test in such a context. First, clients can upload their raw data to the centralized server and delegate the test to it. While this method is effective in terms of communication, it entirely exposes the clients’ private information. Second, clients may run secure multiparty computation (MPC) under the server’s coordination. Thus, clients can jointly run χ2-test without disclosing their data to the server. However, general-purpose MPC imposes significant computation and communication overhead, which is typically intolerable in a federated setting with computationally limited clients, e.g., mobile devices.
To address the dilemma, we present a federated protocol optimized for χ2-test that is computationally and communicationally efficient and discloses limited information to the server. We begin by recasting χ2-test as a second frequency moment estimation problem. To approximate the second frequency moment in a federated setting, each client encodes its raw data into a low-dimensional vector via stable random projection (Indyk, 2006; Vempala, 2005; Li, 2008). Such encodings can be aggregated with only summation, allowing clients to leverage secure aggregation (Bonawitz et al., 2017; Bell et al., 2020) to aggregate the encodings and the server to decode them to approximate the second frequency moment. Because secure aggregation conceals each client’s individual update within the aggregated global update, the server learns only limited information about the clients’ data.
Our evaluation on four synthetic datasets and 16 real-world datasets shows that FED-χ2 can replace centralized χ2-test with good accuracy and low computation overhead. Additionally, we analyze FED-χ2 in three real-world use cases: feature selection, cryptanalysis, and online false discovery rate control. The results show that FED-χ2 can achieve comparable performance with centralized χ2-test and can withstand up to 20% of clients dropping out with minor influence on the accuracy. In summary, we make the following contributions:
We propose FED-χ2, the first secure federated χ2-test protocol. FED-χ2 is computation- and communication-efficient and leaks much less information than trivially deploying secure aggregation.
FED-χ2 decomposes χ2-test into frequency moments estimation that can easily be encoded/decoded using stable projection and secure aggregation techniques. We give formal security proof and utility analysis of FED-χ2.
We evaluate FED-χ2 in real-world use cases, and the findings suggest that FED-χ2 can substitute centralized χ2-test with comparable accuracy, and FED-χ2 can tolerate up to 20% of clients dropout with minor accuracy drop.

heading: 2 RELATED WORK
text: Bonawitz et al. (2017) proposed the well-celebrated secure aggregation protocol as a low-cost way to calculate linear functions in a federated setting. It has seen many variants and improvements since then. For instance, Truex et al. (2019) and Xu et al. (2019) employed advanced crypto tools for secure aggregation, such as threshold homomorphic encryption and functional encryption. So et al. (2021) proposed TURBOAGG, which combines secure sharing with erasure codes for better dropout tolerance. To improve communication efficiency, Bell et al. (2020) and Choi et al. (2020) replaced the complete graph in secure aggregation with either a sparse random graph or a low-degree graph.
Secure aggregation is deployed in a variety of applications. Agarwal et al. (2018) added binomial noise to local gradients, resulting in both differential privacy and communication efficiency. Wang et al. (2020) replaced the binomial noise with discrete Gaussian noise, which is shown to exhibit better composability. Kairouz et al. (2021) proved that the sum of discrete Gaussian is close to discrete Gaussian, thus discarding the common random seed assumption from Wang et al. (2020). The above three works all incorporate secure aggregation in their protocols to lower the noise scale required for differential privacy. Chen et al. (2020) added an extra public parameter to each client to force them to train in the same way, allowing for the detection of malicious clients during aggregation. Nevertheless, designing secure federated correlation tests, despite its importance in real-world scenarios, is not explored by existing research in this field.
On the other end of the spectrum, Wang et al. (2021) proved that stable projection is differentially private if the projection matrix is secret. In our protocol, the projection matrix is public information; hence FED-χ2 does not consider the differential privacy guarantee.

heading: 3 FEDERATED CORRELATION TEST WITH MINIMAL LEAKAGE
text: In this section, we elaborate on the design of FED-χ2, a secure federated protocol for χ2-test. Sec. 3.1 first formalizes the problem, establishes the notation system, and introduces the threat model. In Sec. 3.2, we recast χ2-test as a second frequency moment estimation problem in the federated setting, and consequently, we are able to leverage stable projection to encode each client’s local information (Sec. 3.3), and then aggregate them using secure aggregation (Sec. 3.4). Sec. 3.5, 3.6, and 3.7 present security proof, utility analysis, communication analysis, and computation analysis of FED-χ2.

heading: 3.1 PROBLEM SETUP
text: We now formulate the problem of the federated correlation test and establish the notation system. We use [n] to denote {1, · · · , n}. We denote vectors with bold lower-case letters (e.g., a,b, c) and matrices with bold upper-case letters (e.g., A,B,C).
We consider a population of n clients C = {ci}i∈[n]. Each client has one share of local data composed of the triplets Di = {(x, y, v(i)xy )}, x ∈ X , y ∈ Y, v(i)xy ∈ {−M, · · · ,M}, where x and y are categories of the contingency table, v(i)xy is the observed counting of the categories x and y in the local contingency table of the ith client, |X | = mx and |Y| = my are finite domains, and M is the maximum value |v(i)xy | can be. The global dataset is defined as D = {(x, y, vxy) : vxy =∑ i∈[n] v (i) xy}. We focus on federated χ2-test and the data in contingency table is discrete. For the
ease of presentation, we define the marginal statistics vx = ∑ y∈[|Y|] vxy, vy = ∑ x∈[|X |] vxy, and
v = ∑ x∈[|X |],y∈[|Y|] vxy . Besides, we define v̄xy = vx×vy v , denoting the expectation of vxy if x and
y are uncorrelated. We define m = mxmy and use an indexing function I : [mx]× [my]→ [m] to obtain a uniform indexing given the indexing of each variable. A centralized server S calculates the statistics for χ2-test sχ2(D) = ∑ x∈[|X |],y∈[|Y|] (vxy−v̄xy)2 v̄xy
on the global dataset to decide whether X and Y are correlated without collecting the raw data from clients. Overall, using MPC to conduct secure correlation tests in a federated scenario is highly expensive and impractical (Boyle et al., 2015; Damgård et al., 2012). Hence, in the present work, we trade off accuracy for efficiency, as long as the estimation error is small with a high probability. Formally, if FED-χ2 outputs ŝχ2 , whose corresponding standard centralized χ2-test output is sχ2 , the following accuracy requirement should be satisfied with small and δ.
P[(1− )sχ2 ≤ ŝχ2 ≤ (1 + )sχ2 ] ≥ 1− δ
Threat Model. We assume that the centralized server S is honest but curious. It honestly follows the protocol due to regulatory or reputational pressure but is curious to discover extra private information from clients’ legitimate updates for profit or surveillance purposes. As a result, client updates should contain as little sensitive information as feasible. We want to emphasize that, while the server may explore the privacy of clients, the server will honestly follow the protocol due to regulation or reputational pressure. The server won’t provide adversarial vectors to the clients.
On the other hand, we assume honest clients. Specifically, we do not consider client-side adversarial attacks (e.g., data poisoning attacks (Bagdasaryan et al., 2020; Bhagoji et al., 2019)). However, we allow a small portion of clients to drop out during the execution. Also, as we mentioned in Sec. 2, we do not consider the differential privacy guarantee; see further clarification in Appendix A.

heading: 3.2 FROM CORRELATION TEST TO FREQUENCY MOMENTS ESTIMATION
text: We first recast correlation test to a second frequency moments estimation problem as defined below. Given a set of key-value pairs S = {ki, vi}i∈[n], we re-organize it into a histogramH = {kj , vj =∑ ki=kj ,i∈[n] vi}, and estimate the αth frequency moments as Fα = ∑ j v α j . χ
2-test can thus be recast to a 2nd frequency moments estimation problem as follows:
sχ2(D) = ∑ x,y (vxy − v̄xy)2 v̄xy = ∑ x,y ( vxy − v̄xy√ v̄xy )2
In federated setting, each client ci holds a local dataset Di = {(x, y, v(i)xy )} and computes a vector ui, where ui[I(x, y)] = v(i)xy−v̄xy/n√ v̄xy
and ui has m elements. Thus, the challenge in federated χ2-test becomes calculating the following equation:
sχ2(D) = ∑ x,y ( vxy − v̄xy√ v̄xy )2 = || ∑ i∈[n] ui||22

heading: 3.3 ENCODING BY STABLE PROJECTION & DECODING BY GEOMETRIC MEAN ESTIMATOR
text: To address the aforementioned challenges and to easily integrate the algorithm into secure aggregation protocols, we use stable random projection (Indyk, 2006; Vempala, 2005) and geometric mean estimator (Li, 2008) to approximate the data’s second frequency moment efficiently. We begin by discussing stable distributions, followed by the encoding and decoding techniques. Definition 1 (α-stable distribution). A random variable X follows an α-stable distributionQα,β,F if its characteristic function is as follows.
φX(t) = exp(−F |t|p(1− √ −1β sgn(t) tan(πα
2 )))
, where F is the scale to the αth power and β is the skewness. α-stable distribution is named due to its property called α-stability. Briefly, the sum of independent α-stable variables still follows an α-stable distribution with a different scale. Definition 2 (α-stability). If random variables X ∼ Qα,β,1, Y ∼ Qα,β,1 and X and Y are independent, then C1X + C2Y ∼ Qα,β,Cα1 +Cα2 . We borrow the genius idea from Indyk’s well-celebrated paper (Indyk, 2006) to encode the frequency moments in the scale parameter of a stable distribution defined in Definition 1. To encode the local datasetDi = {(x, y, v(i)xy )}, each client ci, i ∈ [n], is given by the server an `×m projection matrix P whose values are drawn independently from an α-stable distribution Qα,β,1, where ` is the encoding
Algorithm 1: The encoding and decoding scheme for federated frequency moments estimation. Note that the encoding and decoding themselves do not provide any security guarantee.
1 Function ENCODE(P, ui): 2 return P× ui 3 Function GEOMETRICMEANESTIMATOR(e): 4 d̂(2),gm ← ∏` k=1 |ek| 2/`
( 2 π Γ( 2 ` )Γ(1− 1 ` ) sin(π `
))` // ` is the encoding size.
5 return d̂(2),gm 6 Function DECODE(e): 7 return GEOMETRICMEANESTIMATOR(e)
size and m = mxmy. The client re-organizes the data into a vector ui, where ui[I(x, y)] = v(i)xy . Then, the client projects ui to ei = P× ui as the encoding (line 2 in Alg. 1). To decode, the server first sums the encodings up e = ∑ i∈[n] ei and estimates the scale of the variables in the aggregated encoding with an unbiased geometric mean estimator (Li, 2008) in line 4 of Alg. 1. According to the α-stability defined in Definition 2, every element ek in e, k ∈ [`], follows this stable distribution: ek ∼ Q2,0,||∑i∈[n] ui||22 . Thus, the l2 norm can be estimated by calculating the scale of the distribution Q2,0,||∑i∈[n] ui||22 with e containing ` elements. During the above processes, ui and ∑ i∈[n] ui are not leaked and the aggregation among clients is calculated with only summation. Thus, secure aggregation protocols can be naturally applied with quantization, as will be discussed in Sec. 3.4 and 3.5. Furthermore, ` = c 2 log(1/δ) suffices to guarantee that the second frequency moment can be approximated with a 1± factor and a probability no less than 1− δ. We will further analyze the utility of FED-χ2 in Sec. 3.6.

heading: 3.4 SECURE FEDERATED CORRELATION TEST
text: The complete protocol for FED-χ2 is presented in Alg. 2. Firstly, the marginal statistics vx, vy and v are calculated with secure aggregation and broadcasted to all clients (lines 1–6 in Alg. 2). This step can be omitted if the marginal statistics are already known. Then, on the server side, a projection matrix P is sampled from an α-stable distribution Q`×m2,0,1. The projection matrix is broadcasted to all clients (lines 8–10 in Alg. 2). For each client ci, the local data is re-organized into ui and projected to ei as encoding (lines 11–14 in Alg. 2). Then, the encoding results will be quantized and aggregated with secure aggregation (line 15 in Alg. 2). As we have already known the marginal statistics in the first round, the quantization bound can be set accordingly. Additionally, we can use high precision for quantization, such as 64 bits, since the size of the contingency table is normally moderate rather than enormous. Thus, the precision of the quantized float number is comparable to or even better than that of float64, and hence we disregard the effect of quantization on accuracy. Finally, the server gets the χ2-test result using the decoding algorithm described in Alg. 1 (line 17 in Alg. 2).
Dropouts in the first round have no effect on the test’s accuracy because they can be recovered inside secure aggregation (Bonawitz et al., 2017; Bell et al., 2020). On the other hand, dropouts in the second round will affect the accuracy of the test. Still, because the χ2 value is typically far from the decision threshold, FED-χ2 is intrinsically robust to a small portion of clients dropping out (see Section 4 for empirical assessment).

heading: 3.5 SECURITY ANALYSIS
text: As discussed in Sec. 2, the secure aggregation protocol is well studied, and many well-celebrated secure aggregation protocols have been proposed (Bonawitz et al., 2017; Truex et al., 2019; Xu et al., 2019; So et al., 2021; Bell et al., 2020; Choi et al., 2020). In this paper, we choose the state-of-the-art secure aggregation protocol by Bell et al. (Bell et al., 2020), which replaces the complete graph with a sparse random graph to enhance communication efficiency. We clarify that FED-χ2 can incorporate other popular secure aggregation protocols. We now prove the security enforced by Alg. 2 via a standard simulation proof process (Lindell, 2017) on the basis of Theorem 1.
Theorem 1 (Security). Let Π be an instantiation of Alg. 2 with the secure aggregation protocol in Alg. 4 of Appendix H with cryprographic security parameter λ. There exists a PPT simulator SIM such that for all clients C, the number of clients n, all the marginal distributions {vx}, {vy}, and all
the encodings {ei}, the output of SIM is indistinguishable from the view of the real server ΠC in that execution, i.e., ΠC ≈λ SIM( ∑ ei, n).
Intuitively, Theorem 1 illustrates that no more information about the clients except the averaged updates is revealed to the centralized server. Thus, each client’s update is hidden by the rest clients in secure aggregation. We now present the formal proof for Theorem 1. Proof for Theorem 1. To prove Theorem 1, we need the following lemma.
Lemma 1 (Security of secure aggregation protocol). Let SECUREAGG be the secure aggregation protocol in Alg. 4 of Appendix H instantiated with cryprographic security parameter λ. There exists a probabilistic polynomial-time (PPT) simulator SIMSA such that for all clients C, the number of clients n, and all inputs X = {ei}i∈[n], the output of SIMSA is perfectly indistinguishable from the view of the real server, i.e., SECUREAGGC ≈λ SIMSA( ∑ i∈[n] ei, n).
Lemma 1 is derived from the security analysis of our employed secure aggregation protocol (Theorem 3.6 in Bell et al. (2020)), which establishes that the secure aggregation protocol securely conceals the individual information in the aggregated result. With this lemma, we are able to prove the theorem for federated χ2-test by presenting a sequence of hybrids that begin with real protocol execution and end with simulated protocol execution. We demonstrate that every two consecutive hybrids are indistinguishable, illustrating that the hybrids are indistinguishable according to transitivity.
HYB1 This is the view of the server in the real protocol execution, REALC . HYB2 In this hybrid, we replace the view during the execution of each SECUREAGG({v(i)x }i∈[n])
in line 3 of Alg. 2 with the output of SIMSA(vx, n) one by one. According to Lemma 1, each replacement does not change the indistinguishability. Hence, HYB2 is indistinguishable from HYB1.
HYB3 Similar to HYB2, we replace the view during the execution of each SECUREAGG({v(i)y }i∈[n]) in line 4 of Alg. 2 with the output of SIMSA(vy, n) one by one. According to Lemma 1, HYB3 is indistinguishable from HYB2. HYB4 In this hybrid, we replace the view during the execution of SECUREAGG({ei}i∈[n]) in line 15 of Alg. 2 with the SIMSA( ∑ ei, n). This hybrid is the output of SIM. According
to Lemma 1, HYB4 is indistinguishable from HYB3.
Remark: what does Alg. 2 leak? By Theorem 1, we show that individual updates of clients are perfectly hidden in the aggregated results and FED-χ2 leaks no more than a linear equation system: P× v = eT J1,my × V T = vTx
J1,mx × V = v T y
Algorithm 2: FED-χ2: secure federated χ2-test. SECUREAGG is a remote procedure that receives inputs from the clients and returns the summation to the server. INITSECUREAGG is the corresponding setup protocol deciding the communication graph and other hyper-parameters.
1 Round 1: Reveal the marginal statistics 2 INITSECUREAGG(n) // n is the client number. 3 for x ∈ [mx] do vx = SECUREAGG({v(i)x }i∈[n]) 4 for y ∈ [my] do vy = SECUREAGG({v(i)y }i∈[n]) 5 Server 6 Calculate v = ∑ x vx and broadcast v, {vx} and {vy} to all the clients. 7 Round 2: Approximate the statistics 8 Server 9 Sample the projection matrix P fromQ`×m2,0,1
10 Broadcast the projection matrices to the clients 11 Client ci, i ∈ [n] 12 Calculate v̄xy = vxvy v 13 Prepare ui s.t. ui[I(x, y)] = v (i) xy−v̄xy/n√
v̄xy
14 Calculate ei = ENCODE(P, ui) 15 e = SECUREAGG(QUANTIZE({ei}i∈[n])) 16 Server 17 ŝχ2 = DECODE(e)
, where J1,mx and J1,my are 1 ×mx and 1 ×my unit matrices, V is an mx ×my matrix whose elements are {vxy}, and v is a vector flattened by V. To understand this, information leaked by FEDχ2 includes the estimation e and marginal statistics vx and vy . The following theorem establishes an important fact: the above equation system has an exponentially large solution space, which effectively conceals the real joint distribution. We thus believe that Alg. 2 practically ensures privacy due to the solution space’s vastness. Theorem 2. Given a projection matrix P ∈ Z`×mq , {vx}, {vy} and e, there are at least qm−`−mx−my feasible choices of {vxy}. Proof sketch for Theorem 2. As demonstrated above, the given information forms a linear equation with mx + my + ` equations. Given m > mx + my + `, the rank of the coefficient matrix is no more than mx +my + `. Solving the equations with Smith normal form, we know that the solution space is at least (m−mx −my − `)-dimensional. With the following lemma, we manage to prove Theorem 2.
Lemma 2. There are qr×c vectors in the subspace of Zr×cq .

heading: 3.6 UTILITY ANALYSIS
text: In this section, we conduct the utility analysis in terms of multiplicative error. We show that the output of FED-χ2, ŝχ2 , is a fairly accurate approximation (parameterized by ) to the correlation test output sχ2 in the standard centralized setting with high probability parameterized by δ. Theorem 3 (Utility). Let Π be an instantiation of Alg. 2 with secure aggregation protocol in Alg. 4 of Appendix H. Π is parameterized with ` = c 2 log(1/δ) for some constant c. After executing ΠC on all clients C, the server yields ŝχ2 , whose distance to the accurate correlation test output sχ2 is bounded with high probability as follows:
P[ŝχ2 < (1− )sχ2 ∨ ŝχ2 > (1 + )sχ2 ] ≤ δ
Proof sketch for Theorem 3. First, we introduce the following lemma from Li (2008).
Lemma 3 (Tail bounds of geometric mean estimator (Li, 2008)). The right tail bound of geometric mean estimator is:
P(ŝχ2 − sχ2 > sχ2) ≤ exp(−` 2
GR )
where 2 GR = C1 log(1 + ) − C1γe(α − 1) − log( 2πΓ(αC1)Γ(1 − C1) sin(παC12 )), α = 2 in our
setting, C1 = 2π tan −1( log(1+ )(2+α2)π/6 ), and γe = 0.577215665... is the Euler’s constant.
The left tail bound of the geometric mean estimator is:
P(ŝχ2 − sχ2 < − sχ2) ≤ exp(−` 2
GL )
where ` > `0, 2 GL = −C2 log(1 − ) − log(− 2πΓ(−αC2)Γ(1 + C2) sin(παC22 )) −
`0C2 log( 2 πΓ( α `0 )Γ(1− 1`0 ) sin( π 2 α `0 )), and C2 = 12π2 (2+α2) . With Lemma 3, Taking c ≥ max(GR, GL) and δ = exp(− ` 2
c ), we are able to prove P[ŝχ2 < (1− )sχ2 ∨ ŝχ2 > (1 + )sχ2 ] ≤ δ, and the above bound holds when ` = c 2 log(1/δ).

heading: 3.7 COMMUNICATION & COMPUTATION ANALYSIS
text: In this section, we present the communication and computation cost of Alg. 2. Theorem 4 (Communication Cost). Let Π be an instantiation of Alg. 2 with secure aggregation protocol in Alg. 4 of Appendix H, then (1) the client-side communication cost is O(log n + mx + my + `); (2) the server-side communication cost is O(n log n+ nmx + nmy + n`). Theorem 5 (Computation Cost). Let Π be an instantiation of Alg. 2 with secure aggregation protocol in Alg. 4 of Appendix H, then (1) the client-side computation cost isO(log2 n+(`+mx+my) log n+ m`); (2) the server-side computation cost is O(n log2 n+ n(`+mx +my) log n+ `). Note that compared with the original computation cost presented in (Bell et al., 2020), the client-side overhead has an extra O(m`) term. This term is incurred by the encoding overhead. We also give an empirical evaluation on the client-side computation overhead in Sec. 4.1. Please refer to Appendix I for the detailed proof of Theorem 4 and Theorem 5.

heading: 4 EVALUATION
text: Experiment Setup. To assess FED-χ2’s accuracy, we simulate it on four synthetic datasets and 16 real-world datasets. We compare the multiplicative errors of FED-χ2 with that of the standard centralized χ2-test. The four synthetic datasets are independent, linearly correlated, quadratically correlated, and logistically correlated. As the real-world datasets, we report the details in Appendix J.
Additionally, we evaluate FED-χ2’s utility in three real-world application scenarios: 1) feature selection, 2) cryptanalysis, and 3) online false discovery rate (FDR) control. For feature selection, we report the model accuracy trained on the selected features. For cryptanalysis, we report the success rate of cracking ciphertexts. For Online FDR control, we report the average false discovery rate. We compare the performance of FED-χ2 with that of the centralized χ2-test in each of the three experiments. Unless otherwise specified, experiments are launched on an Ubuntu 18.04 LTS server equipped with 32 AMD Opteron(TM) Processor 6212 and 512GB RAM.

heading: 4.1 EVALUATION RESULTS
text: Accuracy. We begin by evaluating the accuracy of FED-χ2, as illustrated in Fig. 1. Each point represents the mean of 100 independent runs with 100 clients, while the error bars indicate the standard deviation. We choose mx = my = 20 in this experiment. Note that the accuracy drop is independent of the number of clients.
From Fig. 1, we observe that the larger the encoding size `, the smaller the multiplicative error. When ` = 50, the multiplicative error ≈ 0.2. This conforms with Theorem 3, in which the multiplicative error = √ c ` log(1/δ) decreases as ` increases.
We also evaluate the power (Cohen, 2013) of FED-χ2. We set the p-value threshold as 0.05, which determines whether or not to reject the null hypothesis. From The dashed lines in Fig. 1, we can tell that the power of FED-χ2 is high. This conforms with our observation on the multiplicative errors. Specifically, since the χ2 values are typically far from the decision threshold, a multiplicative error of 0.2 rarely flips the final decision.
We also present the results when 5% of clients drop out in the second round of FED-χ2 in Fig. 1. The results show that FED-χ2 is robust to a small portion of dropouts. In Appendix G, we present the results in terms of 10%, 15%, and 20% dropout rates.
Client-side Computation Overhead. To assess extra computation overhead incurred by FED-χ2 on the client side, we measure the execution time of the encoding scheme on an Android 10 mobile device equipped with a Snapdragon865 CPU and 12GB RAM. We use PyDroid (Sandeep Nandal, 2020) to run the client-side computation of FED-χ2 on the Android device.
The results are shown in Fig. 2. Each point represents the average of 100 separate runs, with accompanying error bars. The overhead is generally negligible. For example, for a 500×500 contingency table, the encoding takes less than 30ms. The overhead grows linearly in relation to mx (my) and consequently quadratically in Fig. 2, where mx equals my .
4.2 DOWNSTREAM USE CASE STUDY
Feature Selection. Our first case study explores secure federated feature selection using FED-χ2. The setting is that each client holds data with a large feature space and wants to collaborate with other clients to rule out unimportant features and retain features with topk highest χ2 scores. We use Reuters-21578 (Hayes & Weinstein, 1990), a standard text categorization dataset (Yang, 1999; Yang & Pedersen, 1997; Zhang & Yang, 2003), and pick the top-20 most frequent categories using 17,262 training and 4,316 test documents. These documents are distributed randomly to 100 clients, each of whom receives the same number of training documents. After removing all numbers and stop-words, we obtain 167,135 indexing terms. After performing feature selection using FED-χ2, we select the top 40,000 terms with the highest χ2 scores. When compared
with the centralized χ2-test, 38,012 (95.03%) of the selected terms are identical, indicating that FED-χ2 produces highly consistent results with the standard χ2-test.
We then train logistic regression models using the terms selected by FED-χ2 and the centralized χ2-test, respectively. All hyper-parameters are the same. The details of these models are reported in Appendix K. The results in Fig. 3 further demonstrate that FED-χ2 exhibits comparable performance with the centralized χ2-test. When 10% and 20% of clients dropout in the second round of FED-χ2, the accuracy of the trained model using the features selected by FED-χ2 does not drop much. We also examine performance without feature selection, and as expected, model accuracy is significantly greater after feature selection. Note that the model without feature selection has 2,542,700 more parameters than the model with feature selection. Hence, feature selection effectively improves model accuracy while reducing model size and computational cost.
Cryptanalysis. In the second case study, we explore federated cryptanalysis with FED-χ2. We break Caesar cipher (Luciano & Prichett, 1987), a classic substitution cipher, with FED-χ2. In a Caesar cipher, each letter in the plaintext is replaced by another letter with some fixed number of positions down the alphabet. For instance, each English letter can be right-shifted by three, converting
the plaintext “good” to the ciphertext “jrrg”. There are 26 possible shifts when given 26 English letters. The plaintext can be cracked in a shortcut by performing a correlation test on the ciphertext in relation to normal English text.
In our setting, each client is assumed to possess a segment of the Caesar ciphertext. To collaboratively crack the ciphertext, these clients run 26 χ2-tests to determine the correlation level between each ciphertext letter and the letters in normal English text. The χ2-test yielding the highest correlation level elucidates how English letters are encrypted into Caesar ciphertexts.
We take Shakespeare’s lines as the plaintext and encrypt it into a Caesar ciphertext with a length of 1000 characters. We initiate the cracking process on ten non-overlapping ciphertexts to compute the average success rate (see Fig. 4). In general, the larger the encoding size, the more precise the χ2-statistics is, and consequently the higher the success rate. Again, according to Theorem 3, the
multiplicative error decreases as the encoding size increases. In Fig. 4, we also report the success rate when 10% and 20% of clients dropout in Round two of FED-χ2, respectively. Even if 20% of clients dropout, the success rate can still be 100% as long as the encoding size ` is larger than 20.
Online False Discovery Rate Control. In the third case study, we explore federated online false discovery rate (FDR) control (Foster & Stine, 2008) with FED-χ2. In an online FDR control problem, a data analyst receives a stream of hypotheses on the database, or equivalently, a stream of p-values: p1, p2, · · · . At each time t, the data analyst should pick a threshold αt to reject the hypothesis when pt < αt. The error metric is the false discovery rate, and the objective of online FDR control is to ensure that for any time t, the FDR up to time t is smaller than a pre-determined quantity.
We use the SAFFRON procedure (Ramdas et al., 2018), the state-ofthe-art online FDR control, for multiple hypothesis testing. The χ2 results and corresponding p-values are calculated by FED-χ2. We
present the detailed algorithm of SAFFRON and the hyper-parameters used in our evaluation in Appendix L. The size of the randomly synthesized contingency table is 20× 20. Each time, there are 100 independent hypotheses, with a probability of 0.5 that each hypothesis is either independent or correlated. The time sequence length is 100, and the number of clients is 10. The data are synthesized from a multivariate Gaussian distribution. For the correlated data, the covariance matrix is randomly sampled from a uniform distribution. For the independent data, the covariance matrix is diagonal, and its entries are randomly sampled from a uniform distribution.
At time t, we use FED-χ2 to calculate the p-values pt of all the hypotheses, and then use the SAFFRON procedure to estimate the reject threshold αt using pt. The relationship between the average FDR and encoding size ` is shown in Fig. 5. We observe that the variance of independent runs is very small, so we omit the error bars. The results indicate that by increasing the encoding size `, FED-χ2 can achieve a low FDR of less than 5.0%. We also observe that dropouts improve the performance of FED-χ2 in this case study. The reason for this is because dropouts reduce the estimated χ2 value, which increases the probability of accepting the null hypothesis in FED-χ2. As a larger portion of queries follows the null hypothesis in online FDR control, the accuracy also increases. The results further demonstrate that FED-χ2 can be employed in practice to facilitate online FDR control using a secure federated correlation test.

heading: 5 CONCLUSION
text: This paper takes an important step towards designing non-linear secure aggregation protocols in the federated setting. Specifically, we propose a universal secure protocol to evaluate frequency moments in the federated setting. We focus on an important application of the protocol: χ2-test. We give formal security proof and utility analysis on our proposed secure federated learning χ2-test protocol FED-χ2 and validate them with empirical evaluations and case studies.

heading: A CLARIFICATION ON PRIVACY
text: As indicated in Sec. 2, the projection matrix is public information, and hence FED-χ2 does not take the differential privacy guarantee into account. We would want to provide more information in order to eliminate any potential misunderstandings.
To begin, we would want to emphasize that “privacy” in our paper refers to MPC-style privacy, not DP-style privacy. In general, MPC-style privacy is orthogonal to DP-style privacy: in MPC, privacy is obtained against a semi-honest server in such a way that the server cannot witness individual client’s updates but only an aggregate of them, e.g. SecAgg (Bonawitz et al., 2017). In DP, privacy is accomplished by including random noise in each client’s update, such that the distribution of the output result does not reveal the clients’ private information and the server cannot infer the clients’ identification from the output result.
Second, we would like to emphasize that our work proposes a novel secure aggregation scheme particularly for the χ2-test. Existing standard secure aggregation schemes are inapplicable to the χ2-test, which will reveal much more information than FED-χ2, as we have clarified in Sec. 1. Again, this work requires guaranteeing MPC-style privacy, not DP.
Third, to quantify MPC-style privacy, we prove in Theorem 2 that the clients’ updates in FED-χ2 are hidden inside a space with exponential size. This is weaker than hiding users’ updates in the whole space, but still gives meaningful privacy guarantees (consider attempting to guess the output of an exponential-sided dice, which is practically infeasible).
Finally, while DP is orthogonal to this research, we would want to emphasize that our protocol can achieve DP by introducing calibrated discrete Gaussian noise to the users’ local updates.
B COMPARISON WITH POOLING χ2-TEST
We also compare the performance of FED-χ2 with pooling χ2-test. That is, the clients compute the χ2-test with their local observations and then they aggregate their test results by pooling. The result of the pooling χ2-test is determined by the majority of the clients’ local results. Fig. 6 shows the result of pooling χ2-test on the real-world datasets. The details of the datasets are presented in Appendix J. We observe that pooling χ2-test cannot give meaningful results and it tends to give judgement that the data is independent since that the numbers of the local observations are not sufficient to make correct judgement. The results further demonstrate the effectiveness and the necessity of FED-χ2.
C PERFORMANCE OF FED-χ2 WHEN ORIGINAL χ2-TEST ACHIEVES LOW POWER
We have computed the multiplicative error and accuracy of FED-χ2 with the original centralized χ2-test as the baseline. To further demonstrate the effectiveness of FED-χ2, we also set up the experiment to evaluate the performance of FED-χ2 on the synthesized dataset when the accuracy of the original centralized χ2-test is lower. More specifically, we synthesize the random independent, linearly correlated, quadratically correlated, and logistically correlated datasets with the same hyperparameters for 20 times. We then compute the accuracy of the original centralized χ2-test over these 20 datasets. We report the results in Fig. 7. The results show that FED-χ2 can still achieve good performance on the datasets when the original centralized χ2-test’s accuracy is lower. Consistent with our results in Sec. 4.1, the multiplicative error becomes lower with the increase of the encoding size l. Thus, we conclude that FED-χ2’s performance is comparable to that of the original centralized χ2-test with an appropriate encoding size l and this is not dependent on the datasets.

heading: D FURTHER RESULTS FOR ONLINE FDR CONTROL
text: In this section, we provide further results for online FDR control. As we have shown in Fig. 5, FED-χ2 achieves good performance (FDR lower than 5%) when the encoding size l is larger than 200. In Fig. 8, we provide the FDR result of the original χ2-test as well as the true discovery rate (TDR, i.e., #correct reject / #should reject). In addition, we provide statistics for each encoding size l that was evaluated in Table 1. These results demonstrate that FED-χ2 performs well and is comparable to the centralized χ2-test when the encoding size l is increased. More importantly, as we have shown in Sec. 4.1 and Appendix C, FED-χ2 gives results close to original centralized χ2-test and this is independent from the data.
To further demonstrate that the close performance of FED-χ2 and the original centralized χ2-test is independent of the data, we use a similar approach as described in Appendix C to generate the data that the original centralized χ2-test struggles to distinguish its correlation (i.e., resulting in a higher FDR). To achieve this, we change the covariance matrix of the Gaussian distribution when generating the independent and dependent data. The detailed results are shown in Table 2 and in Fig. 9. The original centralized χ2-test achieves an FDR of 7.03% and a TDR of 89.73%. The results indicate that when the encoding size l is increased, the performance of FED-χ2 gets closer to the original centralized χ2-test. When l = 300, FED-χ2 performs similarly to the original centralized χ2-test. The results in Fig. 9 and Table 2 are consistent with those in Appendix C, indicating
that the performance of FED-χ2 is comparable to that of the original centralized χ2-test when the encoding size l is set appropriately, and that this is independent of the data.
E INCORPORATE GAUSSIAN MECHANISM IN FED-χ2
As we have mentioned in Appendix A, FED-χ2 can achieve differential privacy easily by incorporating well-studied differentially private mechanisms. To further demonstrate this point, we utilize Gaussian Mechanism to provide ( , δ)-DP guarantee. We clipped the local clients’ data such that the encoding
function’s sensitivity, which is the L2-norm of the clients’ local data is bounded by ∆f . Before encoding their local data, each client add Gaussian noise N d(0, σ2) to their local data vector µi. We can calculate σ2 = 2 ln(1.25/δ)(∆f) 2
n( /l)2 . After encoding and decoding with the computed vector, FED-χ 2
provides ( , δ)−DP guarantee. We evaluate the performance of differentially private FED-χ2 on the first four real-world datasets adopted in this research as shown in Fig. 10. We choose encoding size l = 10 and δ = 0.01. The results show that the performance our algorithm becomes better with the increase of privacy budget . However, when the privacy budget is small, the protocol tends to give the judgement that the data is independent because that the independent noise is too large and it dominates the test. When the privacy budget is large enough (i.e., = 100), our protocol can achieve 0.92, 0.68, 0.70, and 0.80 accuracy on these datasets accordingly, and its performance is comparable to the original FED-χ2.
Again, our work is orthogonal to differential privacy, thus we leave it as future work to further study saving privacy budget, and boosting the algorithm’s performance on lower .

heading: F FURTHER RESULTS FOR FEATURE SELECTION
text: Our results in Sec. 4.2, paragraph Feature Selection, demonstrate that FED-χ2 performs well when encoding size l = 50. We conduct experiments with different encoding sizes l to further assess their effect on FED-χ2’s performance. In Fig. 11, we present the effect of encoding size l on the ratio of the commonly-selected features between the original centralized χ2-test and FED-χ2. A larger ratio of commonly-selected features means that FED-χ2 performs more closely to the original centralized χ2-test. And if the ratio is 1, these two algorithms select the identical features. The results in Fig. 11 show that when the encoding size l increases, the performance of FED-χ2 approaches that of the original centralized χ2-test.
Similar to Sec. 4.2, we evaluate FED-χ2’s performance by training the model with the features selected by FED-χ2. Fig. 12 shows the results. When trained with FED-χ2-selected features, the model can achieve comparable accuracy to the model trained with features selected by the original centralized χ2-test. Also, consistent with the results in Fig. 3 in Sec. 4.2, we see that when the encoding size l ≥ 25, models trained by FED-χ2-selected features achieve higher accuracy than that of the models without feature selection. These results further demonstrate the effectiveness of FED-χ2.
G FURTHER RESULTS ON FED-χ2 WITH DROPOUTS
We present the results of 10%, 15%, and 20% clients dropout in Fig. 13. The results further show that FED-χ2 can tolerate a considerable portion of clients dropout in Round 2 of Alg. 2.

heading: H SECURE AGGREGATION
text: The secure aggregation protocol from Bell et al. (2020) is presented in Alg. 4. The first step of the protocol is to generate a k-regular graph G, where the n vertices are the clients participating in the protocol. The server runs a randomized graph generation algorithm INITSECUREAGG presented in Alg. 3 that takes the number of clients n and samples output (G, t, k) from a distribution D. In Alg. 3, we uniformly rename the nodes of a graph known as a Harary graph defined in Definition 3 with n nodes and k degrees. The graph G is constructed by sampling k neighbours uniformly and without replacement from the set of remaining n− 1 clients. We choose k = O(log(n)), which is large enough to hide the updates inside the masks. t is the threshold of the Shamir’s Secret Sharing.
In the second step, the edges of the graph determine pairs of clients, each of which runs key agreement protocols to share random keys. The random keys will be used by each party to derive a mask for her input and enable dropouts.
In the third step, each client ci, i ∈ A1 sends secret share to its neighbors. In the fourth step, the server checks whether the clients dropout exceeds the threshold δ, and lets the clients know their neighbors who didn’t dropout.
In the fifth step, each pair (i, j) of connected clients in G runs a λ-secure key agreement protocol si,j = KA.Agree(sk1i , pk1j ) which uses the key exchange in the previous step to derive a shared random key si,j . The pairwise masks mi,j = F (si,j) can be computed, where F is the pseudorandom generator (PRG). If the semi-honest server announces dropouts and later some masked inputs of the claimed dropouts arrive, the server can recover the inputs. To prevent this happening, another level of masks, called self masks, ri is added to the input. Thus, the input of client ci is: yi = ei + ri − ∑ j∈NG(i),j<i mi,j + ∑ j∈NG(i),j>i mi,j .
Steps 6–8 deal with the clients dropout by recovering the self masks ri of clients who are still active and pairwise masks mi,j of the clients who have dropped out. Finally, the server can cancel out the pairwise masks and subtract the self masks in the final sum: ∑ i∈A′2
(yi − ri +∑ j∈NG(i)∩(A′1\A′2),0<j<i mi,j − ∑ j∈NG(i)∩(A′1\A′2),i<j≤n mi,j).
Definition 3 (HARARY(n, k) Graph). Let HARARY(n, k) denotes a graph with n nodes and degree k. This graph has vertices V = [n] and an edge between two distinct vertices i and j if and only if j − i (mod n) ≤ (k + 1)/2 or j − i (mod n) ≥ n− k/2.
Algorithm 3: INITSECUREAGG: Generate Initial Graph for SECUREAGG. 1 Function INITSECUREAGG(n): 2 . n: Number of nodes. 3 . t: Threshold of Shamir’s Secret Sharing. 4 k = O(log(n)). 5 Let H = HARARY(n, k). 6 Sample a random permutation π : [n]→ [n]. 7 Let G be the set of edges {(π(i), π(j))|(i, j) ∈ H}. 8 return (G, t, k)

heading: I PROOF FOR COMMUNICATION & COMPUTATION COST
text: We provide the proof for Theorem 4 and Theorem 5 in the following.
Theorem 4 (Communication Cost). Let Π be an instantiation of Alg. 2 with secure aggregation protocol from Bell et al. (2020), then (1) the client-side communication cost isO(log n+mx+my+`); (2) the server-side communication cost O(n log n+ nmx + nmy + n`).
Proof sketch for Theorem 4. Each client performs k key agreements (O(k) messages, line 9 in Alg. 4) and sends 3 masked inputs (O(mx + my + `) complexity, lines 3, 4, 15 in Alg. 2 and line 10 in Alg. 4). Thus, the client communication cost is O(log n+mx +my + `). The server receives or sends O(log n + mx + my + `) messages to each client, so the server communication cost is O(n log n+ nmx + nmy + n`).
Theorem 5 (Computation Cost). Let Π be an instantiation of Alg. 2 with secure aggregation protocol from Bell et al. (2020), then (1) the client-side computation cost isO(mx log n+my log n+` log n+ m`); (2) the server-side computation cost is O(mx +my + `).
Proof sketch for Theorem 5. Each client computation can be broken up as k key agreements (O(k) complexity, line 9 in Alg. 4), generating masks mi,j for all neighbors cj (O(k(mx + my + `)) complexity, lines 3, 4, 15 in Alg. 2 and line 10 in Alg. 4), and encoding computation cost O(m`) (line 14 in Alg. 2). Thus, the client computation cost is O(mx log n+my log n+ ` log n+m`). The server-side follows directly from the semi-honest computation analysis in Bell et al. (2020). The extra O(`) term is the complexity of the geometric mean estimator.
Algorithm 4: SECUREAGG: Secure Aggregation Protocol. (Algorithm 2 from Bell et al. (2020)) 1 Function SECUREAGG({ei}i∈[n]): 2 . Parties: Clients c1, · · · , cn, and Server. 3 . l: Vector length. 4 . Xl: Input domain, ei ∈ Xl. 5 . F : {0, 1}λ → Xl: PRG. 6 . We denote by A1, A2, A3 the sets of clients that reach certain points without dropping out.
Specifically A1 consists of the clients who finish step (3), A2 those who finish step (5), and A3 those who finish step (7). For each Ai, A′i is the set of clients for which the server sees they have completed that step on time.
7 (1) The server runs (G, t, k) = INITSECUREAGG(n), where G is a regular degree-k undirected graph with n nodes. By NG(i) we denote the set of k nodes adjacent to ci (its neighbors). 8 (2) Client ci, i ∈ [n], generates key pairs (sk1i , pk1i ), (sk2i , pk2i ) and sends (pk1i , pk2i ) to the server who forwards the message to NG(i). 9 (3) for each Client ci, i ∈ A1 do • Generates a random PRG seed bi. • Computes two sets of shares:
Hbi = {hbi,1, · · · , hbi,k} = ShamirSS(t, k, bi)
Hsi = {hsi,1, · · · , hsi,k} = ShamirSS(t, k, sk1i ) • Sends to the server a message m = (j, ci,j), where ci,j = Eauth.Enc(ki,j , (i||j||hbi,j ||hsi,j)) and ki,j = KA.Agree(sk2i , pk2j ), for each j ∈ NG(i).
10 (4) The server aborts if |A′1| < (1− δ)n and otherwise forwards (j, ci,j) to client cj who deduces A′1 ∩NG(j). 11 (5) for each Client ci, i ∈ A2 do • Computes a shared random PRG seed si,j as si,j = KA.Agree(sk1i , pk1j ). • Computes masks mi,j = F (si,j) and ri = F (bi). • Sends to the server their masked input
yi = ei + ri − ∑
j∈[n],j<i
mi,j + ∑
j∈[n],j>i
mi,j
12 (6) The server collects masked inputs. It aborts if |A′2| < (1− δ)n and otherwise sends (A′2 ∪NG(i), (A1\A′2) ∪NG(i)) to every client ci, i ∈ A′2. 13 (7) Client cj , j ∈ A3 receives (R1, R2) from the server and sends {(i, hbi,j)}i∈R1 ∪ {(i, hsi,j)}i∈R2 obtained by decrypting the ci,j received in Step (3). 14 (8) The server aborts if |A′3| < (1− δ)n and otherwise: • Collects, for each client ci, i ∈ A′2, the set Bi of all shares in Hbi sent by clients in A3. Then
aborts if |Bi| < t and otherwise recovers bi and ri using the t shares received which came from the lowest client IDs.
• Collects, for each client ci, i ∈ (A1\A′2), the set Si of all shares in Hsi sent by clients in A3. Then aborts if |Si| < t and otherwise recovers sk1i and mi,j .
• return ∑ i∈A′2 (yi − ri + ∑ j∈NG(i)∩(A′1\A′2),0<j<i mi,j − ∑ j∈NG(i)∩(A′1\A′2),i<j≤n mi,j).

heading: J DETAILS OF DATASETS
text: The details for the real-world datasets used in Sec. 4.1 are provided in Table 3. The license of Credit Risk Classification (Govindaraj, Praveen) is CC BY-SA 4.0, the license of German Traffic
Sign (Houben et al., 2013) is CC0: Public Domain. Other datasets without a license are from UCI Machine Learning Repository (Dua & Graff, 2017).

heading: K DETAILS OF REGRESSION MODELS
text: The details of the regression models trained in feature selection in Sec. 4.2 is reported in Table 4. The training and testing splits are the same for FED-χ2, centralized χ2-test and model without feature selection (i.e. there are 17,262 training and 4,316 test documents). We use the same learning rate; random seed and all other settings are also the same to make the comparison fair. We get the result of Fig. 3 and the models are all trained on NVIDIA GeForce RTX 3090.

heading: L SAFFRON PROCEDURE
text: In Sec. 4.2, we adopt the SAFFRON procedure (Ramdas et al., 2018) to perform online FDR control. SAFFRON procedure is currently the state of the arts for multiple hypothesis testing. In Alg. 5, we formally present the SAFFRON algorithm.
The initial error budget for SAFFRON is (1 − λ1W0) < (1 − λ1α), and this will be allocated to different tests over time. The sequence {λj}∞j=1 is defined by gt and λj serves as a weak estimation of αj . gt can be any coordinate wise non-decreasing function (line 8 in Alg. 5). Rj := I(pj < αj) is the indicator for rejection, while Cj := I(pj < λj) is the indicator for candidacy. τj is the jth rejection time. For each pt, if pt < λt, SAFFRON adds it to the candidate set Ct and sets the candidates after the jth rejection (lines 9-10 in Alg. 5). Further, the αt is updated by several parameters like current wealth, current total rejection numbers, the current size of the candidate set, and so on (lines 11-14 in Alg. 5). Then, the decision Rt is made according to the updated αt (line 15 in Alg. 5).
The hyper-parameters we use for the SAFFRON procedure in online false discovery rate control of Sec. 4 are aligned with the setting in Ramdas et al. (2018). In particular, the target FDR level is α = 0.05, the initial wealth is W0 = 0.0125, and γj is calculated in the following way: γj = 1/(j+1)1.6∑10000 j=0 1/(j+1) 1.6 .
Algorithm 5: SAFFRON Procedure. 1 Function SAFFRONPROCEDURE({p1, p2, · · · }, α, W0, {γj}∞j=0): 2 . {p1, p2, · · · }: Stream of p-values. 3 . α: Target FDR level. 4 . W0: Initial wealth. 5 . {γj}∞j=0: Positive non-increasing sequence summing to one. 6 i← 0 // Set rejection number. 7 for each p-value pt ∈ {p1, p2, · · · } do 8 λt ← gt(R1:t−1, C1:t−1) 9 Ct ← I(pt < λt) // Set the indicator for candidacy Ct.
10 Cj+ ← ∑t−1 i=τj+1 Ci // Set the candidates after the jth rejection. 11 if t = 1 then 12 α1 ← (1− λ1)γ1W0 13 else 14 αt ← (1− λt)(W0γt−C0+ + (α−W0)γt−τ1−C1+ + ∑ j≥2 αγt−τj−Cj+) 15 Rt ← I(pt ≤ αt) // Output Rt. 16 if Rt = 1 then 17 i← i+ 1 // Update rejection number. 18 τi ← t // Set the ith rejection time. 19 return {R0, R1, · · · }

Review summaries:
The paper proposed a federated $\chi^{2}$-test protocol. This is proposed as a technique that is computation- and communication-efficient and leaks much less information than other alternatives. The claim is that the proposed technique can tolerate up to 20\% of clients dropout with minor accuracy drop. The proposed technique does not include differential privacy guarantee. 

This paper discusses the problem of conducting correlation tests with sensitive data separately collected from $n$ clients, where centralizing data collection is risky but the available secure multiparty computation is costly in computation. The proposed test adjusts the classical chi-square test by first rewriting it as a second frequency moments estimation using $n$ vectors, each from a client. The proposed test prevent data recovering when performing the test by letting each client project its vector to a lower dimension. The higher the dimension is, the more accurate the test is, yet the higher the computation costs. 

This paper introduces a federated analytics technique for computing the Pearson correlation for two random variables. The method is based on repeated uses of secure aggregation, as well as stable random projections. The protocol is argued to be secure in a semi-honest security model.