I. INTRODUCTION

Federated learning (FL) has emerged as a powerful decentralized learning paradigm which trains a centralized model using local datasets distributed across many end users [1]- [4]. It finds broad practical applications such as virtual keyboard search suggestion in Google Keyboard [5]. In FL, a set of (possibly many) users, each holding a unique local dataset, wishes to collaboratively learn a shared machine learning model without directly revealing their individual data to the coordination server. More specifically, the training process alternates between local training where each user performs a number of stochastic gradient descent (SGD) on its own dataset, and global aggregation where the users upload their local model parameters to the server for aggregation. In the celebrated FedAvg algorithm [1], the server simply computes a weighted average of the local models, which is then broadcast to the users as an initialization point for a new round of local training. Convergence rates have later been established for FedAvg and related FL algorithms [6], [7].

Despite its potential, FL exposes vulnerability to security and privacy breaches [8]. For example, it was shown that a considerable amount of information of the users' local data can be inferred by the server by observing the local gradients through model inversion attack [9], which poses a threat if the server is not trustworthy. Therefore, a critical consideration in FL is to ensure that the server does not learn the locally trained models of the individual users during aggregation. Moreover, model aggregation should be robust against collusion (server gains access to the local data of some users) and user dropouts due to unreliable connection. Hence, the need for data security and user privacy has stimulated the study of the secure aggregation problem [10]- [12], under a multitude of constraints such as user dropout [13], [14], groupwise keys [15], [16], user selection [17], [18], weak security [19], oblivious servers [20] and malicious users [21]. For example, Bonawitz et al. [10] proposed a secure aggregation protocol which relies on pairwise random seed agreement between users to generate zero-sum random keys (masks) that hide individual users' models. When added for aggregation, the keys cancel out and the desired sum of local models can be recovered. Zhao et al. [17] proposed an information-theoretic formulation of the secure aggregation problem where the local models are abstracted as i.i.d. inputs. The optimal (upload) communication rate has been characterized under user collusion and dropout. Following this line of work, [15] and [16] considered the use of groupwise keys where multiple users may share an identical key. Weak security was considered in [19] where instead protecting all the inputs against an arbitrary subset of users, protection of a predetermined collection of inputs against a restricted subsets of users was studied. In addition, Sun [20] considered a scenario where the servers are oblivious and characterized the optimal communication and key rates.

Existing information-theoretic secure aggregation proto-cols focus exclusively on the canonical FL setup with one central server and many distributed users which faces challenges such as excessive communication overhead, latency and substantial user dropouts due to unstable connectivity [8].

To overcome, hierarchical FL [22]- [24] utilizes the clientedge-cloud architecture in edge computing systems to take advantage of the efficient communication between the users and edge servers. Motivated by this architecture, we study the hierarchical secure aggregation (HSA) problem in a 3layer network consisting of a server, U relays and UV users where each relay is connected to a disjoint set of V users (See Fig. 1). In the aggregation phase of HSA, each user uploads a message (as a function of its private input and key) to the associated relay and each relay also uploads a message to the server based on the collected messages from its connected users. Besides the conventional server security which requires that the server learn nothing about the users' inputs beyond the desired sum of inputs, relay security is also enforced.

In particular, each relay should not infer anything about the users' inputs even if it colludes with up to T users. Our goal is to design secure aggregation protocols that minimize the communication load and key consumption. We show that when T → (U ↑ 1)V , the proposed HSA problem is infeasible. Otherwise when T < (U ↑1)V , we find out that to securely compute 1 bit of the desired sum, each user needs to send at least 1 bit to the associated relay, each relay needs to send at least 1 bit to the server, each user needs to hold at least 1 key bit, and all users need to collectively hold at least max{V + T, min{U + T ↑ 1, UV ↑ 1}} (source) key bits. The characterization of the minimum source key rate is a major contribution of this work. We propose a novel scheme which achieves the optimal user-to-relay, relay-toserver communication rates, individual and source key rates simultaneously. A tight information-theoretic converse is also derived. Throughout the paper, we use the following notation:

II. PROBLEM STATEMENT

We study the secure aggregation problem in a hierarchical network consisting of three layers, an aggregation server, an intermediate layer consisting of U relays and a total of UV users at the bottom layer. The network has two hops, i.e., the server is connected to all the relays and each relay is connected to a disjoint subset of V users that form a cluster (See Fig. 1 for an example with U = 2, V = 3). This network structure finds practical applications in distributed machine learning systems such hierarchical Federated Learning (FL) [22]- [24] where the edge servers act as relays and forward the clients' partially aggregated local parameters to the cloud server for model aggregation. All connection links are orthogonal (i.e., no interference among links) and noiseless. The v th user of the u th cluster is labelled as

Relay 1

Aggregation Server

Relay 2 user

denote the u th cluster. Each user (u, v) is equipped with an input W u,v (e.g., the local gradient or model parameters in FL) of H(W u,v ) = L symbols (in q-ary units) from some finite field F q . The inputs of the users are assumed to be uniformly distributed 1 and independent of each other. Each user is also equipped with a key variable Z u,v of L Z symbols from F q which is generated from a source key variable Z " containing

The keys

The aggregation server wishes to learn the sum of all inputs

and should be prohibited from learning anything about W more than the sum itself even if it colludes with (i.e., gaining access to the individual inputs and keys) any set of up to T users. The relays are oblivious, that is, each relay should not learn anything about W even if it colludes with up to T users.

A two-hop communication protocol is used. Over the first hop, User (u, v) sends a message X u,v containing H(X u,v ) = L X symbols to Relay u, as a function of W u,v and Z u,v . Over the second hop, Relay u sends a message Y u of H(Y u ) = L Y symbols to the aggregation server, as a function of the messages {X u,v } v→[V ] received from the users in its cluster. Hence,

From the relay's messages, the server should be able to recover the desired sum of inputs, i.e,

Security refers to the constraint that each relay should not infer any information about the inputs W (relay security) and the server should not obtain any information about W beyond the knowledge of the desired sum u,v W u,v (server security), even if each relay and the server can respectively collude with any set T of no more than T users, i.e., |T | ↘ T . More specifically, relay security can be expressed in terms of mutual information as

for any T . Server security requires that

Wu,v, {Wi,j, Zi,j} (i,j)→T = 0, ↓T

The communication rate R X (R Y ) characterizes how many symbols that each message X u,v (Y u ) contains per input symbol and the individual (source) key rate R Z (R Z! ) characterizes how many symbols that each key variable Z u,v (Z " ) contains per input symbol, i.e.,

) is said to be achievable if there exists a secure aggregation scheme (i.e., the design of the keys {Z u,v } u,v , Z " and messages {X u,v } u,v , {Y u } u subject to (3) and ( 4)) with communication rates R X , R Y and key rates R Z , R Z! for which the correctness constraint (5) and the security constraints ( 6), (7) are satisfied. The optimal rate region R ↑ is defined as the closure of the set of all achievable rate tuples. For ease of notation, let

→T denote the collection of inputs and keys at the colluding users T . Also denote W " ! = u,v W u,v and

as the sum of inputs of all users and the u th cluster respectively.

III. MAIN RESULT

Theorem 1: For the hierarchical secure aggregation problem with U relays, V users per cluster and a maximum of T colluding users, the optimal rate region is given by

We highlight the implications of Theorem 1 as follows: 1) Infeasible regime: When T → (U ↑ 1)V , the secure aggregation problem is not feasible. Intuitively, when T → (U ↑ 1)V , each relay can collude with all intercluster users so that it is able to recover the sum of all inputs because it has access to all the information necessary to construct the relay-to-server messages

. This violates the relay security constraint (6). 2) Source key rate: The optimal R Z! takes the maximum of V + T and min{U + T ↑ 1, UV ↑ 1}. An intuitive explanation to this formula is provided as follows. When T < (U ↑ 1)V , for any relay, in addition to the V intra-cluster users, we need T more independent keys to tackle user collusion with that relay, resulting in the V + T term. The second term is mainly due to server security. When T ↘ U (V ↑ 1), we have min{U + T ↑ 1, UV ↑1} = U +T ↑1. In this case, we need U ↑1 keys to protect the relay-to-server messages and T additional independent keys against user collusion for the sake of server security. Otherwise when T > U(V ↑1), we have min{U + T ↑ 1, UV ↑ 1} = UV ↑ 1, i.e., the source key rate will not exceed UV ↑ 1 (the total number of users minus one) and it does not depend on T in this regime. In Section V, the above intuitions are formalized through an information-theoretic converse proof. 3) Impact of network hierarchy: Ignoring the boundary cases of T → U (V ↑ 1), the optimal source key rate can be written as max{V + T, U + T ↑ 1}. Comparing with the basic one-hop secure aggregation setting [15] where the minimum source key rate is UV ↑1, we make two interesting observations. First, the total number of users UV is (approximately) replaced by the maximum value of U and V , i.e., a smaller amount source key consumption is required in HSA. This highlights the benefits of employing a hierarchical network structure where there exists a natural separation between the relays and the (inter-cluster) users, and also between the server and the users. Second, the collusion level T comes into play explicitly which necessitates more complicated design strategies than [15].

IV. ACHIEVABLE SCHEME

In this section, we illustrate the proposed secure aggregation scheme through an example. A brief sketch of the general scheme is provided due to space limit. We refer the readers to [25] for a detailed description.

Example 1: Consider (U, V, T ) = (2, 3, 1) as shown in Fig. 1. Each input W u,v contains one symbol from F 3 . The source key Z " = (N 1 , N 2 , N 3 , N 4 ) contains 4 i.i.d. uniform random variables from F 3 . The individual keys are chosen as

User (u, v) sends X u,v = W u,v + Z u,v to Relay u and Relay

v=1 X u,v to the server. In particular,

which matches the lower bound in Theorem 1. Correctness is straightforward because

Security is proved as follows.

Relay security. An important property of the key design ( 9) is that any 4 out of the total 6 keys are mutually independent. This means that for any relay u, even if it colludes with some inter-cluster user (u ↓ , v ↓ ) where u ↓ ⇐ = u and gains access to Z u → ,v → , it cannot infer the inputs {W u,v } 3 v=1 from the messages {W u,v + Z u,v } 3 v=1 due to the independence of {Z u,v } 3 v=1 and Z u → ,v → . Therefore, relay security is achieved. We formalize the above intuition as follows. Consider Relay 1 colluding with T = {(2, 1)} so that C T = {W 2,1 , Z 2,1 }:

(2)

where (11c) is because each X 1,v contains one symbol and uniform distribution maximizes entropy; (11f) is due to the independence of the inputs and the keys; In (11g) we plugged in the key design ( 9) and the last step is because N 1 , • • • , N 4 are i.i.d. and uniform. Since mutual information is nonnegative, we have proved I({X 1,v } 3 v=1 ; W|C T ) = 0. Server security. It can be seen from ( 10) that Y 1 and Y 2 are protected by ±(N 1 + N 2 + N 3 ) respectively. By the key design ( 9), colluding with any user will not eliminate the key component contained in Y 1 and Y 2 so that the inputs are still protected and the server security is guaranteed. Due to space limit, the rigorous proof of server security is omitted. ↭ Remark 1 (Key efficiency): A naive key generation method [13] suggests using UV ↑ 1 = 5 i.i.d. variables N 1 , • • • , N 5 each being assigned to one user and assigning ↑(N 1 + • • •+ N 5 ) to the last user. Our scheme uses a smaller number of i.i.d. variables and thus improving the source key.

Remark 2 (Sketch of the general scheme): Given the source key

). The server adds up the messages from the relays and obtains

To recover the input sum, the aggregated individual keys must cancel out, i.e.,

, the rows of H add up to zero. Moreover, the security constraints require statistical independence among subsets of up to R ↑ Z! individual keys which entails linear independence of every R ↑ Z! rows of H. We propose a specific construction of H utilizing a novel matrix structure called extended Vandermonde matrix which satisfies the zero-sum-of-rows and linear independence properties.

V. CONVERSE

In this section, we derive lower bounds on the communication and key rates R X , R Y , R Z and R Z! . Because these bounds match the achievable rates in Section IV, the optimality of the proposed scheme is established. For ease of presentation, we denote

A. Infeasible Regime: T → (U ↑ 1)V When T → (U ↑ 1)V , each relay can collude with all inter-cluster users and it is impossible to avoid leakage to this relay so that relay security is violated.

We start with a useful lemma which states that each message X u,v and Y u should contain at least L symbols even if all other inputs are known.

Lemma 1: For any u

we have

With Lemma 1, the converse bounds on R X , R Y and R Z follow immediately. We elaborate on the derivation of the lower bound on R Z! which is major novelty of this work.

Proof of R X → 1:

The proof of the individual key rate relies on (12a). Intuitively, to protect any individual input, the key must be at least the size of the input size. The detailed proof is omitted due to space limit.

Proof of R Z! → max{V + T, min{U + T ↑ 1, UV ↑ 1}}. This converse bound is given as the maximum of two terms, where the first term V + T is due to relay security and the second term min{U +T ↑1, UV ↑1} is mainly due to server security while relay security is also needed. We first show that for any relay, the joint entropy of the keys at any set of intra-cluster users V is at least |V|L as stated in Lemma 2.

Lemma 2: For any u ↓ [U ], V ⇒ [V ], and any T ⇑

Proof of R Z! → V +T : Suppose T = mV +n where m, n are non-negative integers and n ↘ V ↑1. We apply Lemma 2 repeatedly on different colluding set T with decreasing sizes as follows:

(1)

→ (m + 1)V L + nL (14i)

where from (14e) to (14g) we applied Lemma 2 with u =

colluding users. Since increasing T can only possibly increase the source key rate, we have R Z! → UV ↑1 when T → U (V ↑ 1), i.e., 2) is implied by 1). Hence, we only need to prove 1) which is shown as follows:

Choose T so that |T | = T and for any cluster u ↓ [U ], there is at least one user (u, v u ) ↓ M u that is not in T . 2 Note that such T exists because T ↘ U (V ↑ 1). We have

We find lower bounds for the two terms in (15) respectively. A lower bound on the first term can be derived as follows:

(3),( 4)

2 Because the security constraints have to be satisfied for every possible T , the converse derived for a specific choice of T is also a valid converse.

where in (17b) we used the chain rule of entropy and the last line is due to Lemma 2. Finally, by combining ( 16) and ( 17) in (15), we obtain L Z! → H (Z T ) + H (Z|Z T ) → (U + T ↑ 1)L, i.e., R Z! = L Z! /L → U + T ↑ 1, completing the converse proof.

VI. CONCLUSION

We studied the hierarchical secure aggregation problem where communication takes place on a 3-layer hierarchical network consisting of clustered users connected to an aggregation server via intermediate relay nodes. We characterized the optimal communication and key rate region under user collusion. Future directions may include extension to deeper network hierarchies, allowing user dropouts and more complicated connection patterns between the users and relays.