Conceptio › Archive › arXiv CS

arXiv CSopen access

Hierarchical Secure Distributed Linearly Separable Computation with Arbitrary Heterogeneous Data Assignment

Ziting Zhang et al. · arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

Hierarchical Secure Distributed Linearly Separable Computation with Arbitrary Heterogeneous Data Assignment

arXiv:2609.33092v1 [cs.DC] 27 Sep 2026

Ziting Zhang, Chenyi Sun, Kai Wan, Member, IEEE, Xiang Zhang, Member, IEEE

Abstract—This paper studies secure distributed linearly separable computation over a three-layer hierarchical network, where clustered users communicate with a central server through relays. The server aims to recover Kc linear combinations of K intermediate outcomes, where each intermediate outcome is a separable function of one dataset. We consider a more general setting with arbitrary heterogeneous data assignment across users, where ‘arbitrary’ means that the data assignment is given in advance (which can be in any form) and ‘heterogeneous’ means that the users may hold different numbers of datasets. Under this assignment, each user computes the intermediate outcomes of its assigned datasets and sends masked messages to its associated relay. The relays subsequently process and forward the received messages to the server. We impose two security constraints: (i) security against server, requiring the server to learn only the desired task function without gaining any additional information about users’ inputs; and (ii) security against relays, ensuring each relay learns nothing about users’ inputs. Moreover, the server or any relay may collude with a subset of users. For Kc = 1, the underlying computation reduces to distributed gradient coding. We propose a secure scheme tolerating user dropouts and user collusion, achieving the optimal two-layer communication rates in one regime and order-optimal communication rates within a factor of 2 in the other regime. For Kc > 1, we extend the proposed construction to multi-dimensional linearly separable tasks under the no-dropout setting. Index Terms—Distributed linearly separable computation, information theoretic security, hierarchical network, arbitrary data assignment

I. I NTRODUCTION Distributed computing underpins large-scale distributed learning and data analytics. In federated learning, users compute local gradients from their datasets, and a central server aggregates these local updates to obtain a global model update. To mitigate stragglers, gradient coding exploits redundancy in the data assignment, enabling the desired aggregate to be recovered from only a subset of user responses [1]–[3]. This line of work focuses on a one-dimensional computation task, in which the server seeks to recover a single linear combination of the locally computed intermediate outcomes. A short version of this paper was presented at the 2026 IEEE International Symposium on Information Theory (ISIT). Z. Zhang, C. Sun, and K. Wan are with the School of Electronic Information and Communications, Huazhong University of Science and Technology, 430074 Wuhan, China (e-mail: {ziting zhang, chenyi sun, kai wan}@hust.edu.cn). X. Zhang is with the Department of Electrical Engineering and Computer Science, Technical University of Berlin, 10623 Berlin, Germany (e-mail: [email protected]).

Beyond gradient aggregation, distributed computing systems may need to recover multiple linear combinations of the same intermediate outcomes, as in distributed linear transforms and coded matrix computations [4]–[7]. This broader class of tasks is captured by distributed linearly separable computation, in which the server aims to recover Kc ≥ 1 linear combinations of K intermediate outcomes [8]. Specifically, each intermediate outcome Wk = fk (Dk ) is obtained by applying a separable function fk (·) to one dataset Dk . Thus, gradient aggregation corresponds to the special case Kc = 1, whereas Kc > 1 represents general multi-dimensional linearly separable tasks. Rather than focusing on how each local function is evaluated, this framework studies how the server can recover the desired linear combinations of these intermediate outcomes under data assignment and communication constraints. The associated computation-communication tradeoffs have been studied under homogeneous or structured data assignments [8]–[10], while related coding-theoretic works formulate the joint design as a sparse matrix factorization problem [11]–[14]. Since intermediate outcomes may be sensitive, communication efficiency alone is insufficient. Secure distributed linearly separable computation was studied in [15] under the conventional star topology, where all users communicate directly with the server. Using random keys independent of the datasets, the server can recover the desired task without learning additional information about the inputs. The security requirement in this setting protects the users’ inputs against the central server. As the number of users grows, however, direct user-server communication creates bandwidth and connectivity burdens. A hierarchical architecture groups users into clusters that communicate with the server through intermediate relays. The introduction of intermediate relays changes not only the network topology but also the trust model. Hierarchical secure aggregation (HSA) has been studied under different user-relay association and collusion models [16]–[19]. Since each relay receives and processes the messages transmitted by the users in its cluster, the security against server alone is no longer sufficient; the users’ inputs must also be protected from the intermediate relays. This additional requirement, referred to as security against relays, distinguishes HSA from secure computation over a conventional star network. A three-layer hierarchical network was considered in [16], consisting of one server, U relays, and UV users under a symmetric architecture, where each relay serves V users. Two information theoretic security constraints are imposed: (i) security against server, requiring the server to learn only the sum of gradients without

TABLE I: Comparison of the considered model with existing related works. Work

Topology

Data assignment

[1]–[3] [8]–[10], [14] [15] [16]–[19] [20] [21] [22] This work

Star network Star network Star network Hierarchical network Star network Star network Hierarchical network Hierarchical network

Non-fixed with redundancy Non-fixed with redundancy Non-fixed with redundancy Fixed without redundancy Fixed with redundancy Fixed with redundancy Fixed with redundancy Fixed with redundancy

gaining any additional information about individual inputs; and (ii) security against relays, ensuring each relay learns nothing about users’ inputs. These security constraints must continue to hold even when the server or any relay colludes with up to T users. The relay-to-server and user-to-relay communication rates, denoted by R1 and R2 , respectively, are defined as the maximum normalized transmission loads over the corresponding links. The capacity region was characterized as {(R1 , R2 ) : R1 ≥ 1, R2 ≥ 1} when T < (U − 1)V, whereas secure aggregation is infeasible when T ≥ (U − 1)V. Subsequent works extended HSA to more general association and security models. The work in [17] considered a cyclic user-relay association pattern, where each user is connected to B relays in a cyclic wrap-around manner. It characterized the optimal communication cost and key rate region when B ≤ K − 1, showing that multi-relay association can reduce both the relay-to-server communication load and the required key size. Another work studied HSA against relays and user collusion in homogeneous multi-association networks [18], where each user is connected to n relays and each relay serves m users. By establishing a connection between HSA and network function computation, communication-optimal schemes were obtained under certain collusion thresholds. Heterogeneous security requirements were also investigated, where only prescribed subsets of users need to be protected against prescribed colluding sets [19]. In this setting, the communication rates remain optimal, while the source key rate is determined by the interaction between the protected input sets and the colluding user sets. Existing HSA models are primarily motivated by federated learning, where each user holds a private dataset and the server seeks to recover the sum of these updates. This model does not fully capture more general distributed computing systems, since data placement is often determined by data generation, caching, or storage constraints before the coding scheme is designed, and users may hold irregular subsets of datasets. This motivates the study of arbitrary heterogeneous data assignment, where the assignment is fixed in advance and may have an arbitrary structure across users. Some works consider arbitrary heterogeneous data assignment under a conventional star topology. Gradient coding under arbitrary heterogeneous data assignment was studied in [20], where a universal coding scheme was proposed. In the presence of s stragglers, the minimum normalized communication cost was characterized 1 as r−s , where r denotes the minimum replication factor among

Dimension of computation task Kc = 1 Kc ≥ 1 Kc ≥ 1 Kc = 1 Kc = 1 Kc ≥ 1 Kc = 1 Kc ≥ 1

Security No security No security Security against server Security against server and relays No security No security Security against relays Security against server and relays

all data partitions. Hence, the communication performance is determined by the least-replicated data partition. By allowing the server to recover Kc ≥ 1 linear combinations of the intermediate outcomes, distributed linearly separable computation under arbitrary heterogeneous data assignment was further studied in [21]. This work extended the setting to multidimensional tasks and characterized the fundamental tradeoff between communication cost and computable task dimension. More recently, this arbitrary heterogeneous data assignment model was extended to an asymmetric three-layer hierarchical network in [22], where relay u serves a cluster of Vu users. For the one-dimensional aggregation task Kc = 1, the optimal twolayer communication region was characterized under homogeneous rate constraints. Specifically, let R1 denote the relay(u) to-server communication load and let R2 denote the userto-relay communication load in cluster u.nIn the absence of (u) security constraints, the optimal region is (R1 , R2 ) : R1 ≥ o (u) 1 1 ≥ , for each u ∈ [U], where r1 (u) (u) r1 −s1 , R2 (u)

(r1 −s1 )(r2 −s2 )

and r2 denote the minimum replication factors across relays and among the users in cluster u, respectively, s1 denotes the (u) maximum number of straggling relays, and s2 denotes the maximum number of straggling users in cluster u. Its secure extension guarantees security against relays only under the (u) (u) restrictive conditions s1 + 1 ≤ r1 ≤ U − 1 and r2 = s2 + 1, while preserving the same communication rates. However, as summarized in Table I, the existing study of hierarchical networks with arbitrary heterogeneous data assignment is restricted to the one-dimensional aggregation task with Kc = 1. Moreover, its secure extension guarantees only security against relays under restrictive conditions and does not simultaneously ensure security against server. Consequently, the fundamental limits of secure distributed linearly separable computation over such networks, where the server aims to recover Kc ≥ 1 linear combinations, remain unexplored. In particular, it is unclear how the heterogeneous data availability at both the user and relay layers jointly affects the two-layer communication costs and the security against colluding users. Motivated by this gap, we investigate secure distributed linearly separable computation over an asymmetric three-layer hierarchical network with arbitrary heterogeneous data assignment. Main Contributions: Based on secure distributed linearly separable computation [15] and hierarchical gradient coding with arbitrary data assignment [22], we formulate the informa-

Fig. 1: Hierarchical secure distributed linearly separable computation problem (U, V1 , V2 ) = (2, 2, 4) where user (2, 4) is a straggler, relay 1 colludes with user (1, 2) and the server colludes with user (2, 1). tion theoretic secure distributed linearly separable computation over a three-layer hierarchical network, as illustrated in Fig. 1. The network consists of a central server, multiple relays, and clusters of users with arbitrary heterogeneous data assignment. The server aims to recover Kc ≥ 1 linear combinations of the intermediate outcomes from surviving users, while guaranteeing security against server and relays with user collusion. We aim to characterize the capacity region (R1 , R2 , RZ ). More precisely, our main contributions are as follows. • Secure gradient coding with user dropouts and collusion. For the case Kc = 1, where the desired task reduces (u) (u) to gradient aggregation, we consider up to s2 < r2 user dropouts and at most Tu colluding users in each cluster u ∈ [U]. We propose a secure linear-coding-based scheme against user dropouts and user collusion that achieves the optimal two-layer communication rates in one regime and order-optimal communication rates within a factor of 2 in the other regime. The main technical challenge lies in simultaneously satisfying the heterogeneous encodability constraints at both layers while preserving security against server and relays with user collusion. To address this challenge, we develop a security-aware nested task construction in which virtual demands and key-encrypted linear combinations are carefully designed. In particular, the virtual-demand and source-key dimensions are carefully chosen to compensate for the constraints imposed by unavailable datasets and to mask the additional information potentially exposed through user collusion. • Multi-dimensional tasks under the no-dropout setting. For the case Kc > 1, we further extend the construction to multi-dimensional linearly separable tasks under arbitrary heterogeneous data assignment. By applying the heterogeneous construction in a layer-wise manner and treating the source keys as symbols available to all users, we obtain achievable bounds on the computable dimension and guarantee security against server and relays with user collusion when Tu ≤ t2,u for each u ∈ [U]. Paper Organization: This paper is organized as follows. Section II introduces the hierarchical secure distributed linearly separable computation problem with arbitrary het-

erogeneous data assignment, where both user dropouts and user collusion are considered. Section III presents the main results of this paper. Section IV describes the proposed secure aggregation scheme. Building on this construction, Section V extends the proposed scheme to multi-dimensional linearly separable tasks under the no-dropout setting. Finally, Section VI concludes the paper, and the appendices provide the proofs. Notation Convention: [n] denotes the set [1 : n]; [a : b] represents the range {a, a + 1, . . . , b}. Let 0m×n and 1m×n represent the all-zero and all-one matrices of dimension m×n, respectively. For a set S, we denote the ith smallest element by S(i). We let XS = {Xi }i∈S for any index set S. M(S, .) and M(., S) represent the sub-matrices of M composed of the rows with indices in S and the columns with indices in S, respectively. The matrix [A; B] is expressed in a format A similar to Matlab, equivalent to . Calligraphic symbols B represent sets. Vectors and matrices are denoted using bold symbols. System parameters are represented in sans-serif font. | · | defines the cardinality of a set. Fq represents a finite field of order q. For any logical statement E, let 1{E} denote its indicator function, which equals 1 if E is true and 0 otherwise. II. S YSTEM M ODEL We consider the coding-theory-based formulation of secure distributed linearly separable computation in a hierarchical network with arbitrary data assignment, as illustrated in Fig. 1. The global dataset D is partitioned into K non-overlapping and equal-length subsets, denoted by D = {D1 , . . . , DK }, which are assigned to users in an arbitrary manner. For each dataset Dk , where k ∈ [K], a function fk (·) is applied to generate an intermediate outcome Wk = fk (Dk ), where Wk consists of L symbols over a finite field Fq . Each intermediate outcome Wk , where k ∈ [K], is further partitioned into p non-overlapping and equal-length pieces, denoted by Wk = (Wk,1 , Wk,2 , . . . , Wk,p ), where each piece consists of L/p symbols over Fq . Define the collection of all intermediate pieces as W = [W1,1 ; . . . ; WK,1 ; W1,2 ; . . . ; WK,p ]. The server aims to recover pKc linear combinations of these pieces, given by   F1   f (D1 , . . . , DK ) =  ...  = FW, (1) FpKc where F is the task coefficient matrix with elements uniformly i.i.d. over Fq . In particular, when Kc = 1, the task consists of p linear combinations of the pieces. By choosing each linear combination to aggregate the corresponding piece across all datasets, P these p outputs collectively recover the gradient aggregation k∈[K] Wk . In this paper, we consider Kc ≥ 1. The network consists of three layers: a central server, an intermediate layer of U relays, and distributed users at the bottom layer. The server is connected to all relays, while relay u is connected to a disjoint cluster of Vu users. Specifically, the v th user in cluster u is labeled as user (u, v) ∈ [U] × [Vu ]. All communication links are orthogonal and noiseless. Regarding

the data assignment, the set of datasets assigned to user (u, v) is denoted by D(u,v) , where D(u,v) ̸= ∅. Accordingly, the of datasets assigned to cluster u is D(u) ≜ S collection (u,v) . For each dataset Dk where k ∈ [K], let Nk v∈[Vu ] D (u)

(resp. Nk ) represent the set of clusters (resp. the set of users in cluster u) that are assigned dataset Dk . The cardinality of (u) (u) this set r1,k ≜ |Nk | (resp. r2,k ≜ Nk ) indicates the replication factor of the dataset Dk among clusters (resp. in cluster u). (u) (u) Define r1 ≜ mink∈[K] r1,k , r2 ≜ mink:Dk ∈D(u) r2,k , where r1 (u) (resp. r2 ) represents the minimum replication factor among clusters (resp. in cluster u). Based on its assigned datasets D(u,v) , user (u, v) computes the locally available intermediate outcomes Wu,v = {Wk : Dk ∈ D(u,v) }. To guarantee secure computation, a source key ZΣ , independent of the intermediate outcomes, is generated before communication. The source key consists of a collection of mutually independent subkeys, where each subkey contains L/p symbols over Fq . Each user (u, v) stores an individual (u,v) key Zu,v , which is generated as RZ linear combinations of the subkeys in ZΣ . The individual key rate is defined as the maximum normalized key size among all users, (u,v)

RZ ≜

RZ p u∈[U],v∈[Vu ]

max

(2)

(u,v)

Xu,v,i = Eu,v,i W + Gu,v,i Zu,v , ∀i ∈ [R2

(3)

where Eu,v,i = {eu,v,i,1,1 , . . . , eu,v,i,K,1 , eu,v,i,1,2 , . . . , eu,v,i,K,p } and eu,v,i,k,l for each k ∈ [K] and l ∈ [p] denotes the encoding coefficient associated with Wk,l in the i-th encoded message. Thus, the message Xu,v can be expressed as       Xu,v,1 Eu,v,1 Gu,v,1 .. .. ..        = W +   Zu,v . . . 2

Eu,v,R(u,v)

Gu,v,R(u,v)

= Eu,v W + Gu,v Zu,v .

(4)

Since each user (u, v) only encodes the datasets assigned to it, the coefficients must satisfy the encodability constraint (u,v)

eu,v,i,k,l = 0, ∀ i ∈ [R2

], k : Dk ∈ / D(u,v) , l ∈ [p].

(5)

Thus, the user-to-relay communication rate is defined as the maximum normalized transmission load among all users, (u,v)

R2 ≜

R2 p u∈[U],v∈[Vu ] max

XMu (|Mu |) Thus, the message Yu can be expressed as        Yu,1 Au,1 XMu (1) XMu (1)     ..   ..   .. .. .  = Au   .  =  .  . . Yu,R(u) Au,R(u) X X Mu (|Mu |) Mu (|Mu |) 1 1 (8) The relay-to-server communication rate is defined as the maximum normalized transmission load among all relays, (u)

R1 . u∈[U] p

R1 ≜ max

(6)

Among Vu users inside cluster u, we consider at most (u) (u) s2 = Vu − Uu < r2 stragglers. Over the second hop, relay (u) u sends a message Yu = (Yu,j : j ∈ [R1 ]) to the server, based on the messages received from the surviving users in

(9)

Decodability. All relays are reliable, i.e., no relay straggling is considered. After receiving the messages from all relays, the server should be able to recover the desired task,     F1 Y1  ..   ..  (10)  .  = D . . FpKc

Over the first hop, user (u, v) sends a masked input Xu,v = (u,v) (Xu,v,i : i ∈ [R2 ]) to its associated relay u, as a function of (u,v) Wu,v and Zu,v . Specifically, each user (u, v) transmits R2 linearly encoded messages, each constructed as

Xu,v,R(u,v)

Mu , where Mu ⊆ {u}×[Vu ], |Mu | ≥ Uu . Specifically, relay (u) u transmits R1 linearly encoded messages,   XMu (1)   (u) .. Yu,j = Au,j  (7)  , ∀j ∈ [R1 ]. .

For any colluding user set Tu ⊆ {u} × [Vu ] with |Tu | ≤ Tu in eachScluster u ∈ [U], denote the global colluding set T ≜ u∈[U] Tu . The intermediate outcomes available to the users are denoted by WT ≜ {Wk : Dk ∈ S colluding (u,v) D }, and let the colluding keys be denoted by (u,v)∈T ZT ≜ (Zu,v : (u, v) ∈ T ). The security requirements ensure that, even if the server or any relay colludes with up to Tu users in each cluster u ∈ [U], the following two security constraints are satisfied. Security against server. For each Ti ⊆ {i}×[Vi ] with |Ti | ≤ Ti , where i ∈ [U], the server cannot obtain any information about the users’ inputs beyond the desired task, I {Yu }u∈[U] ; {Wk }k∈[K] FW, {WT , ZT } = 0. (11) Security against relays. For each Ti ⊆ {i}×[Vi ] with |Ti | ≤ Ti , where i ∈ [U], each relay cannot infer any information about the users’ inputs, I {Xu,v }v∈[Vu ] ; {Wk }k∈[K] {WT , ZT } = 0, ∀u ∈ [U]. (12) Objective. A rate tuple (R1 , R2 , RZ ) is said to be achievable if there exists a secure linear coding scheme with user encoding matrices {Eu,v , Gu,v : (u, v) ∈ [U] × [Vu ]}, relay encoding matrices {Au : u ∈ [U]}, and a decoding matrix D, such that the security constraints in (11) and (12) are satisfied, and the server can recover the desired task exactly for Kc = 1 q→∞ and a vanishing error probability ε −→ 0 for Kc > 1.1 The 1 For K = 1, by assuming that L is large enough, the symbols of each W c k can be grouped into blocks, with each block identified as one symbol over a sufficiently large extension field of Fq . Hence, without loss of generality, we can directly assume that q is large enough as in [23]. For Kc > 1, let ε denote the probability that the decodability constraint in (10) is not satisfied.

objective is to characterize the capacity region (i.e., the closure of the set of all achievable rate tuples), denoted by R. Theorem 1 ( [22]). For the distributed linearly separable computation problem in a hierarchical network with arbitrary data assignment and Kc = 1, consisting of one server, U relays, and Vu users in cluster u ∈ [U] with at most (u) (u) s2 < r2 stragglers, the minimum communication rates are characterized by ( ) 1 1 (u) (u) R1 , R2 : R1 ≥ R= , ∀u ∈ [U] , ,R ≥ (u) m1 2 m1 m2 (13) (u) (u) (u) where m1 ≜ r1 , m2 ≜ r2 − s2 . In addition, when the security against relays is considered (i.e., (12)), the optimal (u) rate region remains as (13) when 1 ≤ r1 ≤ U − 1 and r2 = (u) s2 + 1. Remark 1. The above result is derived under a homogeneous rate constraint, where all relays have the same transmission load and all users within each cluster are subject to the same transmission load. For a given dataset, if the users in cluster u transmit fewer coded messages involving this dataset, the corresponding relay may accordingly transmit fewer keyencrypted coded combinations. To preserve decodability, the resulting reduction in information must then be compensated by increased transmissions from users in other clusters storing the same dataset, which may further increase the transmission loads of their associated relays. So, reducing the communication load in one cluster may necessarily increase that in others. This inter-cluster user-load tradeoff motivates our definition of the worst-link user-to-relay communication load R2 in (6). III. M AIN R ESULTS A. Distributed Gradient Coding (Kc = 1) Recall that r1 represents the minimum replication factor (u) among clusters, and r2 denotes the minimum replication factor within cluster u. Consider a cluster u ∈ [U] satisfying (u) Tu > Vu − r2 , since each dataset in D(u) is assigned (u) to at least r2 users, the complement of any colluding set Tu ⊆ {u} × [Vu ] with |Tu | = Tu contains fewer than (u) r2 users. Hence, every dataset in D(u) must be stored by at least one colluding user in Tu . A stronger condition, (u) Tu ≥ Vu − s2 , implies that all surviving user messages in this cluster are available to the colluding users. This stronger condition leads to the second converse bound on the relay-toserver communication rate. We first establish converse bounds on the communication rates in the following theorem, whose proof is provided in Appendix A. Theorem 2. For the secure distributed linearly separable computation problem in a hierarchical network with arbitrary data assignment and Kc = 1, consisting of one server, U relays, and Vu users in cluster u ∈ [U], with at most (u) (u) s2 < r2 stragglers and at most Tu colluding users, any achievable rate tuple should satisfy • (R1 ≥ m11 , R2 ≥ m11n2 , RZ ≥ m11n2 ) when P (u) u∈[U] 1{Tu ≥ Vu − s2 } < U − r1 ;

(R1 ≥ m11−1 , R2 ≥ m11n2 , RZ ≥ m11n2 ) when m1 ≥ 2 and P (u) u∈[U] 1{Tu ≥ Vu − s2 } ≥ U − r1 ; P (u) • R = ∅ when m1 = 1 and u∈[U] 1{Tu ≥ Vu − s2 } ≥ U − r1 ,

•

(u)

where m1 ≜ r1 , m2

(u)

≜ r2 − s2

(u)

and n2 ≜ minu∈[U] m2 .

We explain the main theorem of this paper as follows. The threshold U − r1 arises from the minimum clusterlevel replication requirement. In particular, a cluster sat(u) isfying Tu ≥ Vu − s2 can be fully exposed through collusion, since all datasets assigned to this cluster and all surviving user messages can n be available toothe colluding P (u) users. Hence, 1 Tu ≥ Vu − s2 counts the u∈[U] number of such exposed clusters. • First regime. Consider a dataset Di whose cluster-level replication factor equals the minimum replication factor m1 = r1 . Its contribution to the desired aggregation can only be conveyed through the m1 relays storing it. Hence, at least one of these relays must transmit no fewer than L/m1 symbols, which yields R1 ≥ 1/m1 . For the bound on R2 , we continue to consider the same dataset Di . (u) In a cluster u storing Di , after at most s2 stragglers, (u) (u) (u) only m2 = r2 − s2 surviving users storing Di are guaranteed to remain. These users must collectively provide the information required by the corresponding relay. Therefore, at least one of them must transmit (u) no fewer than L/(m1 m2 ) symbols. Taking the worst case over all clusters gives R2 ≥ 1/(m1 n2 ). Finally, to guarantee security against relays, the size of the key stored by each user must be at least as large as the maximum transmission size. Combining this requirement with the converse bound on R2 yields RZ ≥ 1/(m1 n2 ). • Second regime. In this regime, only the lower bound on R1 is further tightened, whereas the converse bounds on R2 and RZn remain unchanged. o We first consider the case P (u) 1 T ≥ V − s = U − r1 . All datasets and u u 2 u∈[U] keys in these U − r1 clusters are fully exposed through collusion. After excluding the U−r1 clusters, the problem therefore reduces to a system with m1 = r1 effective clusters in which every non-colluding dataset is assigned to every effective cluster. By the security against relays, conditioned on the colluding side information available to any effective relay, its transmitted message must reveal no information about the non-colluding datasets. Hence, at the messages received by the server, the size of the keys should be at least equal to the maximum size of the transmission by each of the m1 effective relays. Thus the total received dimension by the server is at most m1 R1 , which should include the task dimension (i.e., 1) and the key dimension (at least n R1 ), which leads o to R1 ≥ 1/(m1 − P (u) 1). When u∈[U] 1 Tu ≥ Vu − s2 > U − r1 , since the optimal rates are non-decreasing when the number of colluding users increases, the same converse bound holds. • Third regime. In this case, at most one effective relay remains. Consider a non-colluding dataset Di that is assigned only to this effective relay. If this relay colludes

•

with the other U − 1 clusters, it has access to its own received user messages together with all information available in the remaining clusters. In contrast, the server has access to the information from the other U − 1 clusters together with only the message transmitted by this relay, which is a function of the relay’s received user messages. By the security against relays, the effective relay cannot recover any information about Wi even colluding with the other U − 1 clusters and knowing the remaining K − 1 datasets. However, the server does not obtain more information than this ‘super’ relay with the colluding information from the other U − 1 clusters; thus the server cannot recover Wi with the knowledge of the remaining K − 1 datasets either, which contradicts the decodability. Therefore, the security and decodability constraints cannot be simultaneously satisfied. We then propose an achievable secure scheme by using a hybrid design strategy. Theorem 3. Consider the secure distributed linearly separable computation problem in a hierarchical network with arbitrary data assignment and Kc = 1, consisting of one server, U relays, and Vu users in cluster u ∈ [U], with at (u) (u) most s2 < r2 stragglers and at most Tu colluding users, 1 1 1 • (R1 ≥ m , R2 ≥ m n , RZ ≥ m n ) is achievable when 1 1 2 1 2 P (u) u∈[U] 1{Tu > Vu − r2 } < U − r1 ; 1 1 1 • (R1 ≥ m −1 , R2 ≥ (m −1)n , RZ ≥ (m −1)n ) is achiev1 1 1 2 P2 (u) able when m1 ≥ 2 and u∈[U] 1{Tu > Vu − r2 } ≥ U − r1 , (u) (u) (u) (u) where m1 ≜ r1 , m2 ≜ r2 − s2 and n2 ≜ minu∈[U] m2 . We summarize the key idea of the scheme as follows. • A hybrid design strategy is employed to construct the computational tasks for both relays and users. Specifically, in the relay-to-server layer, the aggregation problem is reduced to a secure gradient coding formulation over a star network, where relays are treated as “special users” and transmit coded messages protected by the keys. Once the tasks for each relay are assigned, a gradient coding formulation over a star network is applied in each cluster, which also treats the keys in the message transmitted by the relay as the tasks in this gradient coding problem. • The proposed scheme guarantees the security against relays and server. The polynomial code-based scheme in [22] is unable to guarantee server-side security. This is because, from the polynomial recovered by the server, the number of inputs which zero-forces the keys is larger than the computational task, and thus information about the gradients beyond their sum is leaked. In contrast, we design the secure aggregation scheme based on linear space, ensuring that the key dimension in the linear space observed by the server is exactly sufficient for masking the additional information. Comparing the proposed converse and achievable bounds, we obtain the following optimality result. Theorem 4. For the secure distributed linearly separable computation problem in a hierarchical network with arbitrary

data assignment and Kc = 1, consisting of one server, U relays, and Vu users in cluster u ∈ [U], with at most (u) (u) s2 < r2 stragglers and at most Tu colluding users, 1 1 1 • (R1 ≥ m , R2 ≥ m n , RZ ≥ m n ) is optimal when 1 1 2 1 2 P (u) u∈[U] 1{Tu > Vu − r2 } < U − r1 ; 1 1 1 • (R1 ≥ m −1 , R2 ≥ (m −1)n , RZ ≥ (m −1)n ) is 1 1 2 1 2 order-optimal within a factor of 2 when m1 ≥ 2 and P (u) u∈[U] 1{Tu > Vu − r2 } ≥ U − r1 , (u)

where m1 ≜ r1 , m2

(u)

≜ r2 − s2

(u)

and n2 ≜ minu∈[U] m2 .

B. Multi-Dimensional Linearly Separable Tasks (Kc ≥ 1) We next consider the case Kc ≥ 1 under the no-dropout setting, where all users and all relays remain active.2 For each cluster u ∈ [U], let D(u) denote the set of datasets available in cluster u. We order the datasets in D(u) according to their global indices and denote the k-th dataset in this ordered list by D(u) (k), where k ∈ [|D(u) |]. We define the local data assignment matrix A2,u with dimension Vu ×|D(u) |, ( ∗, D(u) (k) ∈ D(u,v) , A2,u (v, k) = (14) 0, D(u) (k) ∈ / D(u,v) . Here, A2,u describes the data assignment in cluster u. The keys are not included because they are available to all users. For a given user-to-relay communication cost R2 , define Z2,u ≜ {(G, Q)|G ⊆ [Vu ], Q ⊆ [|D(u) |], A2,u (G, Q) = 0, R2 |G| + |Q| > R2 Vu }. ′ G2,u

Let ≜ (G,Q)∈Z2,u G. Let t2,u be the maximum ′ number of zeros in each column of A2,u (G2,u , .), i.e., ′ t2,u ≜ maxk∈[|D(u) |] v ∈ G2,u : A2,u (v, k) = 0 . Then, by directly applying the heterogeneous computation scheme in [21], relay u can recover n o K(u) ≜ min R2 (Vu − t2,u ), |D(u) | (15) c linear combinations of the data pieces available in cluster u and keys. Since different clusters may have different local data (1) (2) (U) assignment matrices, the values Kc , Kc , . . . , Kc may also be different. Hence, we choose R1 ≜ min K(u) c , u∈[U]

(16)

which guarantees that each relay u ∈ [U] can locally recover at least R1 linear combinations of the datasets {Wk : Dk ∈ D(u) } and keys, with coefficients generated uniformly i.i.d. over Fq . We now apply the heterogeneous computation scheme in [21] again across relays. We define the cluster-level data assignment matrix A1 with dimension U × K. Specifically, ( ∗, Dk ∈ D(u) , A1 (u, k) = (17) 0, Dk ∈ / D(u) . 2 The main challenge of considering K ≥ 1 with user dropouts is that the c impact of stragglers depends on the heterogeneous data assignment. Different datasets may be replicated among different user subsets, and thus the same set of stragglers can result in different losses of available information for different datasets. Unlike the case of Kc = 1, where only one aggregate function needs to be recovered, recovering multiple independent linear combinations requires preserving sufficient dimensions for all datasets for all possible stragglers.

Again, A1 describes the data assignment across relays. The keys are available to all relays. For a given relay-to-server communication cost R1 , define

A1 (G, Q) = 0, R1 |G| + |Q| > R1 U}.

S Let G1′ ≜ (G,Q)∈Z1 G, and t1 be the maximum number of zeros in each column of A1 (G1′ , .), i.e., t1 ≜ maxk∈[K] |{u ∈ G1′ : A1 (u, k) = 0}|. The server can recover (18)

linear combinations of {W1 , . . . , WK } and keys with coefficients uniformly i.i.d. over Fq . Letting the coefficients of the keys be zero, the server can recover the Ksrv c -dimensional task. Theorem 5. Consider the secure distributed linearly separable computation problem in a hierarchical network with arbitrary data assignment and Kc > 1, consisting of one server, U relays, and Vu users in cluster u ∈ [U], with at most Tu ≤ t2,u colluding users. For a given user-to-relay communication cost dimension in cluster R2 , the computable (u) (u) , and the relay-tou is Kc ≜ min R2 Vu − t2,u , D (u) server communication cost is chosen as R1 ≜ minu∈[U] Kc . Then, the achievable task dimension at the server is Kc ≤ Ksrv = min {R1 (U − t1 ), K} . c

relay 1

Z1 ≜ {(G, Q)|G ⊆ [U], Q ⊆ [K],

Ksrv ≜ min {R1 (U − t1 ), K} c

TABLE II: Data assignment

(19)

The proposed scheme for Kc > 1 is presented in Section V. IV. P ROOF OF T HEOREM 3: ACHIEVABLE S CHEME In this section, we present the proposed secure aggregation scheme that achieves the rate region in Theorem 3 for the P (u) first regime (i.e., u∈[U] 1{Tu > Vu − r2 } < U − r1 ). The construction for the second regime (i.e., m1 ≥ 2 and P (u) u∈[U] 1{Tu > Vu −r2 } ≥ U−r1 ) follows a similar coding principle, and the main difference will be summarized in Remark 2. We begin with an illustrative example to highlight the main ideas of the construction. A. A Motivating Example Consider an aggregation server connected to U = 2 relays, with V1 = 2 and V2 = 3 users in the two clusters. The training dataset is partitioned into K = 6 non-overlapping and equal-length datasets D = {D1 , . . . , D6 }, where each partial gradient Wk is computed from Dk . The datasets are assigned to users in an arbitrary manner, as shown in Table II. For (1) (2) this assignment, we have r1 = 1, r2 = 1, and r2 = 2. Assume that the numbers of stragglers in the two clusters (1) (2) are s2 = 0 and s2 = 1. Hence, m1 = r1 = 1 and (u) (u) (u) n2 = minu∈[2] m2 = minu∈[2] (r2 − s2 ) = 1. In this example, we assume that q is a sufficiently large prime for the sake of illustration, although this assumption is not required in the general scheme. In addition, assume that T1 = T2 = 1. Introduce three independent keys (each with L elements uniformly i.i.d. over Fq ), denoted by ZΣ = {N1 , N2 , N3 }.

user (1, 1) (1, 2) (2, 1) (2, 2) (2, 3)

D1 ✓ ✓

dataset D3 D4 ✓ ✓

✓ ✓ ✓ ✓

✓ ✓

D6 ✓ ✓

✓ ✓

Relay-to-Server layer. Based on Theorem 3, we have R1 ≥ m11 = 1. Each relay transmits one linear combination of {W1 , . . . , W6 , N1 , . . . , N3 } to the server. The server recovers   W1  ..     .   W F1×6 01×3  W6  ; (20) (F1 )2×6 (B1 )2×3 =  N V1×6 B1×3  N1    .   ..  N3 W we define W′ ≜ . The first row corresponds to the N desired aggregation task, and hence F = [1 1 1 1 1 1], while the remaining row is the virtual to be designed. #demand " (1) 3 1 S1 Define the matrix S1 ≜ (2) = , whose elements 2 1 S1 are uniformly i.i.d. over Fq . Then each relay u ∈ [2] transmits (u) Yu = S1 F1 B1 W′ . Since relay u can only form linear combinations of the datasets available in cluster u, the coefficients corresponding to the datasets that are not in D(u) must be ‘0’. Therefore, we design the matrix V according to the encodability constraints. For example, for the first column of F1 , since D1 is not available at relay 2, we require (2) S1 F1 (., {1}) = 0. Thus, we can solve F1 (., {1}) = [1, −2]T . The remaining columns of F1 can be obtained in the same manner, and the detailed construction is 1 1 1 1 1 1 F1 = . (21) −2 −2 3 1 −3 −2

Then we further choose the top-layer key coefficient matrix B = 1 1 2 , whose elements are uniformly i.i.d. over Fq . Thus, we complete the design of the matrix in (20) 1 1 1 1 1 1 0 0 0 F1 B1 = . (22) −2 −2 3 1 −3 −2 1 1 2 Consequently, the transmissions of the two relays are Y1=W1 +W2 + 6W3 + 4W4 + W6 + N1 + N2 + 2N3 , (23a) Y2 = 5W3 + 3W4 − W5 + N1 + N2 + 2N3 .

(23b)

Decodability. After receiving the messages from all relays, ′ −1 Y1 the server can recover F1 B1 W = S1 , where the Y2 first row of the P recovered vector is exactly the desired aggregation result k∈[6] Wk . Therefore, the server can decode the aggregation result from the relay transmissions. User-to-Relay layer. We assign the key-encrypted linear combinations in (23) as local computation tasks to the clusters.

By R2 ≥ m11n2 = 1, each user transmits one linear combination to its associated relay. For cluster 1, the assigned relay-layer computation is (1) S1 F1 B1 W′ = 1 1 6 4 0 1 1 1 2 W′ . To enable relay 1 to recover this linear combination while preserving security, we let relay 1 recover two key-encrypted linear combinations, i.e., (1) i h (1) S1 F1 S1 B1 (1) (1) ′ W′ , (24) F2 B2 W = V2,1 B2,1 where V2,1 is a virtual demand coefficient matrix designed according to the users’ encodability constraints, and B2,1 denotes the lower-layer key coefficient that is to be " # matrix (1,1) S2,1 4 −1 designed. We generate S2,1 ≜ (1,2) = 1 −1 , where S2,1 the elements are uniformly i.i.d. over Fq . Then i v), h each user (1, (1,v) (1) where v ∈ [2], transmits X1,v = S2,1 F(1) B2 W′ , 2 where the coefficients corresponding to the datasets that are not in D(1,v) must be ‘0’. Therefore, V2,1 is chosen so that the encodability constraints of the two users are sat(1) isfied. Specifically, for the first column of F2 , since D1 is available at users (1, 1) and (1, 2), we randomly select (1) V2,1 (., {1}) = {5}. Thus, we have F2 (., {1}) = [1, 5]T ; for (1) the second column of F2 , since D2 is not available at user (1,1) (1) (1, 1), we require S2,1 F2 (., {2}) = 0. Thus, we can solve (1) (1) F2 (., {2}) = [1, 4]T . The remaining columns of F 2 can be obtained in the same manner. By choosing B2,1 = 3 2 3 , whose elements are uniformly i.i.d. over Fq , we have i h (1) (1) ′ 1 1 6 4 0 1 1 1 2 ′ F2 B2 W = 5 4 6 4 0 3 3 2 3 W . (25) So the transmissions of the two users in cluster 1 are X1,1 = −W1 + 18W3 + 12W4 + W6 + N1 + 2N2 + 5N3 , X1,2 = −4W1 − 3W2 − 2W6 − 2N1 − N2 − N3 , where the individual keys of user (1, 1) and user (1, 2) are chosen as Z1,1 = N1 + 2N2 + 5N3 and Z1,2 = −2N1 − N2 − N3 , respectively. Hence, relay 1 can recover the assigned relaylayer computation from (X1,1 , X1,2 ) since S2,1 is invertible. For cluster 2, the assigned relay-layer computation is (2) S1 F1 B1 W′ = 0 0 5 3 −1 0 1 1 2 W′ . We let relay 2 recover two key-encrypted linear combinations from any two surviving users, i.e., (2) i h (2) S1 F1 S1 B1 (2) (2) ′ W′ . (26) F2 B2 W = V2,2 B2,2  (2,1)    S2,2 2 −1    4 3 , whose Similarly, we generate S2,2 ≜ S(2,2) 2,2  = (2,3) −1 1 S2,2 elements are uniformly i.i.d. overh Fq . Each user i (2, v), where (2,v) (2) v ∈ [3], transmits X2,v = S2,2 F(2) W′ , where the B 2 2 coefficients corresponding to the datasets that are not in D(2,v) must be ‘0’. Thus, V2,2 is chosen in the above manner so that

the encodability constraints of the three users are satisfied. By choosing B2,2 = 4 5 3 with elements uniformly i.i.d. over Fq , we have i h 0 0 5 3 −1 0 1 1 2 (2) (2) ′ W W′ . = F2 B2 0 0 2 6 −1 0 4 5 3 Then the transmissions of the three users in cluster 2 are X2,1 = 8W3 − W5 − 2N1 − 3N2 + N3 ,

(27a)

X2,2 =26W3 +30W4 −7W5 +16N1 +19N2 +17N3 , (27b) X2,3 = −3W3 + 3W4 + 3N1 + 4N2 + N3 ,

(27c)

where the individual keys of user (2, 1), user (2, 2), and user (2, 3) are chosen as Z2,1 = −2N1 −3N2 +N3 , Z2,2 = 16N1 + 19N2 + 17N3 , and Z2,3 = 3N1 + 4N2 + N3 , respectively. Next we explain intuitively the security of the proposed scheme, while the formal information theoretic proof can be found in Appendices B and C. Security against relays. For the security against relays, recall that T1 = T2 = 1, i.e., at most one user in each cluster may collude. By construction, each relay receives two key-encrypted linear combinations from the surviving (1) (2) users. Since both B2 and B2 are row-wise full rank, the local observations at each relay are perfectly protected by independent keys. Therefore, without collusion, each relay cannot infer any information about the users’ inputs. We next consider the case where a relay colludes with users. For example, consider relay 2 colluding with users (1, 1) and (2, 1), i.e., T = {(1, 1), (2, 1)}. The keys contained in the observations of relay 2 are K2,1 = N1 + N2 + 2N3 , K2,2 = 4N1 + 5N2 + 3N3 . (28) The colluding user (2, 1) reveals the key Z2,1 = −2N1 − 3N2 + N3 , which lies in the span of {K2,1 , K2,2 }. Hence, relay 2 can remove the corresponding masking key and recover 8W3 − W5 from its observations. However, W3 and W5 are already available from the colluding users’ side information. Therefore, no information about the non-colluding datasets is revealed. Meanwhile, the key information revealed by user (1, 1) is linearly independent of {K2,1 , K2,2 }. Consequently, this additional key information cannot help relay 2 eliminate the masking keys protecting the messages of non-colluding users. Thus, the security of relay 2 is guaranteed. The same argument applies to relay 1 and all possible cases of the colluding users. Therefore, the security against relays is satisfied for all relays. Security against server. In (20), besides the desired aggregation, the server also obtains one key-encrypted linear combination from the relay transmissions. In addition, the server may obtain the key information from the colluding users. For example, consider the case where the server colludes with users (1, 1) and (2, 1). The key N1 + N2 + 2N3 used to mask the linear combination is linearly independent of the colluding users’ keys Z1,1 and Z2,1 . So the server obtains no information about the non-colluding datasets beyond the desired sum. The same argument applies to all possible cases of collusion. Hence, the security against server is guaranteed. Hence, the proposed scheme achieves (R1 , R2 , RZ ) = (1, 1, 1), satisfying the security against server and relays.



B. General Scheme Given an arbitrary data assignment, the minimum replication factors in cluster u and across all relays are denoted (u) (u) by r2 and r1 , based on which n2 = minu∈[U] m2 = (u) (u) minu∈[U] (r2 − s2 ) and m1 = r1 are determined. For each k ∈ [K], we divide Wk into m = m1 n2 non-overlapping and equal-length pieces, each containing L′ = mL i.i.d. uniform symbolsover Fq , denoted byWk = (Wk,1 , . . . , Wk,m ). We inP troduce i∈[U] Ui − m1 n2 uniformly i.i.d. keys (each also ′

i∈[U] with L′ symbols) over FLq as ZΣ , and hence RZΣ = m − 1 n2 3 T 1. We denote W ≜ [W1,1 , · · · , WK,1 , W1,2 , · · · , WK,m ] , N ≜ [N1 , · · · , NmRZΣ ]T . As explained in Footnote 1, by taking L large enough, q can be assumed to be large enough. Relay-to-Server layer. To achieve R1 ≥ m11 in Theorem 3, we let each relay transmit n2 linear combinations of the data pieces and the keys to the server, where each linear combination contains L′ symbols. Hence, after receiving the messages from all U relays, the server obtains 2 a total of Un ′ F B W = linear combinations, which can be written as 1 1 F 0 W , where the received coefficient matrix is V B N divided into two parts. The upper part consists of the first m rows, where F is determined by the desired gradient aggregation task. The lower part consists of the remaining rows, which are introduced as virtual key-encrypted linear combinations. In this lower part, the top-layer key coefficient matrix B can be generated directly as a full-rank matrix with elements uniformly i.i.d. over Fq to ensure the security against server. Therefore, it remains to design the virtual demand matrix V such that the encodability constraints of all relays are satisfied. We let each relay u ∈ [U] transmit (u) Yu = S1 F1 B1 W′ , (29)

(u)

whereS1  is of dimension n2 × Un2 . We choose the matrix (1) S1  .   S1 ≜   ..  as a full-rank matrix of dimension Un2 × Un2 , (U)

S1 whose elements are uniformly i.i.d. over Fq . The encodability constraint requires that relay u only forms linear combinations of the datasets available in cluster u. Therefore, the coefficients corresponding to the datasets that are not in D(u) must be ‘0’. For each dataset Dk ∈ D \ D(u) , we require (u) S1 F1 ., {k + (j − 1)K} = 0, ∀j ∈ [m]. (30) For each dataset Dk ∈ D\D(u) , it is unavailable at most U−r1 relays, yielding at most n2 (U − r1 ) zero-forcing constraints. The number of rows of the virtual demand matrix is Un2 −m = n2 (U − r1 ), where m = m1 n2 = r1 n2 . Hence, the matrix V has enough degrees of freedom to satisfy all encodability constraints. After receiving the messages from all relays, the 3 Following the key construction in [24], we generalize the “total number of users minus one” principle by choosing the source-key dimension as the total number of surviving user-layer transmissions minus the number of the desired aggregation dimensions.

server can recover F1

 Y1  .  B1 W′ = S−1 1  ..  . Therefore,

YU the server can recover the aggregation result from these first m linear combinations. User-to-Relay layer. Then, for each relay u ∈ [U], we assign the key-encrypted linear combinations in (29) as the computational task to be recovered. By the converse bound R2 ≥ m11n2 , each user transmits one linearly independent message, each of length L′ . From the surviving users, relay u receives Uu linear combinations, which can be written as (u) h i (u) W S1 F1 S1 B1 (u) (u) ′ W = . (31) F2 B2 N V2,u B2,u The first n2 rows are predetermined and correspond exactly to the assigned task in (29), whereas the remaining rows are introduced as virtual key-encrypted linear combinations. To construct these virtual rows, the lower-layer key coefficient matrix B2,u is generated as a full-rank matrix with elements uniformly i.i.d. over Fq , and the virtual demand matrix V2,u is designed accordingly to ensure that the encodability constraints of all users within cluster u are satisfied. Each user (u, v) transmits i h (u,v) (u) W′ , (32) Xu,v = S2,u F(u) B 2 2 (u,v)

is of dimension1 × Uu .For each cluster u, we (u,1) S  2,u .   choose the matrix S2,u ≜   ..  , whose elements are (u,Vu ) S2,u uniformly i.i.d. over Fq . The encodability constraint requires that user (u, v) only forms linear combinations of the datasets assigned to it. Therefore, the coefficients corresponding to the datasets that are not in D(u,v) must be ‘0’. For each dataset Dk ∈ D(u) \ D(u,v) , we require (u,v) (u) S2,u F2 ., {k + (j − 1)K} = 0, ∀j ∈ [m]. (33) where S2,u

For each dataset Dk ∈ D(u) \ D(u,v) , it is unavailable at most (u) (u) Vu − r2 users, yielding at most (Vu − r2 ) zero-forcing constraints. The number of rows of the virtual demand matrix (u) (u) received by relay u is Uu −n2 ≥ Uu −m2 = Vu −r2 , where (u) m2 ≥ n2 . Hence, the virtual demand matrix has enough degrees of freedom to satisfy all encodability constraints. We next verify the security. For each cluster i ∈ [U], let ST2,ii denote the submatrix of S2,i formed by selecting the rows corresponding to the colluding users  T (1)  in Ti , where |Ti | ≤ Ti . S2,ii   ..  , where Ti (j) denotes the More specifically, ST2,ii =  .   Ti (|Ti |) S2,i j-th colluding user in cluster i. For each cluster i ∈ [U], define the key coefficient matrix by the colluding users in ( T revealed (i) i S B , |T | i < Ui , 2,i 2 (i) cluster i as KT ≜ (i) B2 , |Ti | ≥ Ui . Security against relays. For relay u ∈ [U], if cluster u is a (u) colluding cluster, i.e., |Tu | > Vu − r2 , then all inputs associ(u) ated with D are already contained in the side information

WT . Thus, the security against relays holds trivially for this (u) cluster. It remains to consider the case |Tu | ≤ Vu − r2 . The total key coefficient matrix revealed by the external colluding (1) (u−1) (u+1) (U) users is Ku,T ≜ [KT ; . . . ; KT ; KT ; . . . ; KT ]. It will be proved in Appendix B-A that, if Constraint 1 is satisfied, the information theoretic security against relays is guaranteed. Constraint 1 (Security against relays with collusion). For each relay u ∈ [U] and each collection of colluding user sets (u) B2 {Ti : i ∈ [U] \ {u}} satisfying |Ti | ≤ Ti , the matrix Ku,T has row-wise full rank. In Appendix B-B, we will further prove that Constraint 1 holds for the proposed scheme. Hence, the information theoretic security against relays is guaranteed. Security against server. Recall that theo set of colluding n (u) clusters is B ≜ u ∈ [U] : |Tu | > Vu − r2 . For each u ∈ B, every dataset assigned to cluster u is stored by at least one colluding user, and thus the corresponding inputs are already contained  in the  side information WT . We further B(1) S1  .   .  , whose dimension is |B|n2 × Un2 . define SB 1 ≜  .  B(|B|) S1 Let KT denote the total key coefficient matrix revealed by (1) (U) the colluding users, i.e., KT ≜ [KT ; . . . ; KT ]. It will be proved in Appendix C-A that, if Constraint 2 is satisfied, the information theoretic security against server is guaranteed. Constraint 2 (Security against server with collusion). For each collection of colluding user sets {Ti : i ∈ [U]} satisfying |Ti | ≤ Ti, we have rowspan(B) ∩ rowspan(KT ) ⊆ rowspan SB 1 B1 . In Appendix C-B, we will further prove that Constraint 2 holds for the proposed scheme. Hence, the information theoretic security against server is guaranteed. Performance. Each relay transmits Yu in (29), consisting of n2 messages of length L′ ; thus R1 = m11 . Each user (u, v) (u) sends one message of length L′ ; thus R2 = m11n2 . Remark 2. For the second regime where m1 ≥ 2 and P (u) u∈[U] 1{Tu > Vu − r2 } ≥ U − r1 , the proposed scheme follows a similar construction as in the first regime. We divide each Wk into m = (m1 − 1)n2 non-overlapping and L equal-length pieces, each containing L′ = (m1 −1)n symbols. 2 Each user transmits one linear combination of length L′ to its associated relay, while each relay transmits n2 linear combinations to the server. Hence, R1 = m11−1 , R2 = RZ = 1 (m1 −1)n2 . The encodability follows from the same virtualdemand construction. At the user-to-relay layer, the number (u) of virtual-demand dimensions satisfies Vu − s2 − n2 ≥ (u) (u) (u) (u) Vu − r2 , since m2 = r2 − s2 ≥ n2 . At the relay-toserver layer, the number of virtual-demand dimensions satisfies Un2 − (m1 − 1)n2 ≥ (U − r1 )n2 . Hence, the available virtualdemand dimensions are sufficient to satisfy all encodability constraints at both layers. The security proof follows a similar argument as in the first regime. For any cluster satisfying

(u)

|Tu | > Vu − r2 , all datasets assigned to this cluster are already contained in the colluding side information, and hence the security constraint holds trivially. For the remaining relays, n o P (u) if 1 |T | > V − r > U − r1 , the colluding u u 2 u∈[U] datasets available at the considered relay cover all datasets in the system, and hence the security constraint is also satisfied. Otherwise, the additional keys revealed through collusion are linearly independent of the keys protecting the messages received by the relay. Therefore, the security against relays is guaranteed. For the server, the key information revealed through collusion is either linearly independent of the keys protecting the messages received by the server or associated only with datasets already contained in the colluding side information. Therefore, the server cannot obtain any additional information about the non-colluding datasets. Hence, the security against server is also satisfied. V. P ROOF OF T HEOREM 5: ACHIEVABLE S CHEME In this section, we extend the heterogeneous linearly separable computation scheme in [21] to a hierarchical network with multi-dimensional tasks (i.e., Kc ≥ 1). Recall that, in our system model, each Wk is partitioned into p non-overlapping and equal-length pieces. Accordingly, we adopt the fractional communication construction in [21], which allows message subpacketization and fractional communication costs. Since the heterogeneous scheme in [21] does not consider user dropouts, we also focus on the no-dropout setting in this extension, where all users and all relays remain active. The construction is applied in a layer-wise manner: in the relay-to-server layer, each cluster is treated as a virtual user, while in the user-to-relay layer, the users within each cluster are treated as local users. Recall that W = [W1,1 ; . . . ; WK,1 ; W1,2 ; . . . ; WK,p ]. To incorporate secure aggregation, the source keys are viewed as data symbols available P to all users. We introduce pR2 i∈[U] Ui − p uniformly ′

i.i.d. keys (each containing L′ = pL symbols) over FLq as ZΣ , W T ′ P i.e., N ≜ [N1 , · · · , NpR2 i∈[U] Ui −p ] . Let W = . N Let Cu,k ⊆ [Vu ] denote the set of indices v in cluster u such that user (u, v) is not assigned dataset Dk , and let Ck ⊆ [U] denote the set of relays that are not assigned dataset Dk . From the messages of all relays, the server can recover pR1 U linear F 0 ′ ′ combinations, i.e., [F1 B1 ] W = W , where FW V B is the desired task, V is the virtual demand matrix to be determined by the encodability constraints of all relays, and B is the top-layer key coefficient matrix, whose elements are chosen uniformly i.i.d. over Fq . Following the fractional communication construction in [21], the heterogeneous construction proceeds as follows. (u) First, we generate {S1 : u ∈ G1′ } with elements uniformly i.i.d. over Fq . Then, for each k ∈ [K] and j ∈ [p], we impose (u)

S1 F1 (., {k + (j − 1)K}) = 0, u ∈ Ck ∩ G1′ .

(34)

There are at most pR1 |Ck ∩ G1′ | ≤ pR1 t1 linearly independent constraints. Recall in (18), we have Ksrv ≤ R1 (U − t1 ); the c number of rows of the virtual demand matrix is pR1 U −

pKsrv ≥ pR1 t1 . These free entries are sufficient to satisfy c all the zero-forcing constraints. (u) After V is fixed, for each u ∈ / G1′ , we construct S1 from the left null space induced by the unavailable data-piece columns. More precisely, define n o (u) K ≜ k + (j − 1)K : Dk ∈ D \ D(u) , j ∈ [p] . (u)

(u)

is chosen such that S1 F1 (.,  K ) = 0. By (1) S  1.   Lemma 1 in [21], the matrix S1 =  ..   is full rank with Then S1

(U)

S1 high probability, and the server can recover the task FW. For relay u ∈ [U], the assigned relay-to-server task is (u) Yu = S1 [F1 B1 ] W′ . From the messages of all users within cluster u, relay u can recover linearcombina (u)pR2 Vu (u) h i (u) (u) S F S 1 1 1 B1 W′ . We tions, i.e., F2 B2 W′ = V2,u B2,u can also choose the elements in B2,u uniformly i.i.d. over Fq . Then the heterogeneous construction proceeds as follows. n o (u,v) ′ We first generate S2,u : v ∈ G2,u with elements uniformly i.i.d. over Fq . We then choose V2,u so that, for each k satisfying Dk ∈ D(u) and each j ∈ [p], we impose (u,v)

(u)

′ S2,u F2 (., {k + (j − 1)K}) = 0, v ∈ Cu,k ∩ G2,u . (35) ′ There are at most pR2 |Cu,k ∩ G2,u | ≤ pR2 t2,u linearly independent constraints. Recall in (15) and (16), we have (u) R1 ≤ Kc ≤ R2 (Vu − t2,u ); the number of rows of the virtual (u) demand matrix is pR2 Vu − pR1 ≥ pR2 Vu − pKc ≥ pR2 t2,u . These free entries are sufficient to satisfy all the zero-forcing constraints. For each k such that Dk ∈ / D(u) , all the p columns of V2,u corresponding to Dk are set to ‘0’. (u,v) ′ After V2,u is fixed, for each v ∈ / G2,u , we construct S2,u from the left null space induced by the unavailable local datapiece columns. More precisely, define n o (u,v) K ≜ k + (j − 1)K : Dk ∈ D(u) \ D(u,v) , j ∈ [p] . (u,v)

(u,v)

(u)

(u,v)

is chosen such that S2,u F2 (., K  ) = 0.  (u,1) S2,u  .   Hence, following Lemma 1 in [21], S2,u =   ..  (u,V ) S2,u u his full rank iwith high probability. Thus, relay u recovers (u) (u) F2 B2 W′ . From the first pR1 rows, relay u can send the required message Yu to the server. Performance. The above scheme achieves the task dimension Ksrv = min{R1 (U − t1 ), K} with communic (u) cation rates (R1 , R2 ), where R1 ≜ minu∈[U] Kc = minu∈[U] min R2 (Vu − t2,u ), |D(u) | . Therefore, any task dimension satisfying Kc ≤ Ksrv is achievable. c Now suppose that at most Tu ≤ t2,u users in cluster u may collude. In this case, the security against server and relays can be guaranteed in the same spirit as the condition (u) Tu ≤ Vu − r2 in Section IV. Specifically, the amount of key information revealed by the colluding users in cluster Then S2,u

u is no larger than pR2 Tu , whereas the number of keyencrypted virtual-demand dimensions satisfies p(R2 Vu −R1 ) ≥ pR2 t2,u ≥ pR2 Tu . Since the corresponding key coefficients are chosen uniformly i.i.d. over Fq , these virtual-demand dimensions provide sufficient independent masking dimensions with high probability. Therefore, the security against both the server and the relays is preserved. VI. C ONCLUSIONS This paper studied the information theoretic secure distributed linearly separable computation problem over a threelayer hierarchical network with arbitrary heterogeneous data assignment. For gradient aggregation with Kc = 1, we established converse and achievable bounds in the presence of user dropouts and collusion, and proposed a linear-coding-based secure coding scheme that achieves the optimal two-layer communication rates in one regime and order-optimal communication rates within a factor of 2 in the other regime, while guaranteeing security against the server and relays. We further extended the proposed construction to multi-dimensional linearly separable tasks with Kc > 1 under the no-dropout setting and established an achievable task dimension determined by the user-level and cluster-level data assignment structures. The resulting scheme satisfies the security requirements against user collusion within the prescribed thresholds. Ongoing work focuses on three directions: characterizing the tradeoff between communication cost and achievable task dimension for multidimensional tasks in the presence of user dropouts; determining the minimum total number of keys required to guarantee the security against server and relays; and developing secure schemes that tolerate stronger user collusion. A PPENDIX A P ROOF OF T HEOREM 2 A. Proof for the first regime We first prove R1 ≥ m11 . Choose a dataset Di such that |Ni | = m1 , and let A ≜ Ni denote the set of relays assigned Di . By the decodability constraint, we have   X 0=H Wk {Yu }u∈[U]  (36a) k∈[K]

≥ H Wi {Wk }k∈[K]\{i} , ZΣ , {Yu }u∈[U] .

(36b)

Hence, L = H Wi {Wk }k∈[K]\{i} , ZΣ

(37a)

= I Wi ; {Yu }u∈[U] {Wk }k∈[K]\{i} , ZΣ = I Wi ; {Yu }u∈A {Wk }k∈[K]\{i} , ZΣ ≤ H {Yu }u∈A {Wk }k∈[K]\{i} , ZΣ X ≤ H Yu {Wk }k∈[K]\{i} , ZΣ

(37b) (37c) (37d) (37e)

u∈A

≤

X u∈A

H(Yu ).

(37f)

Thus, we have maxu∈A H(Yu ) ≥ mL1 and

B. Proof for the second regime

1 R1 ≥ . m1

(38)

Next, we prove the converse bound on R2 ≥ From (37e), we obtain X H Yu | {Wk }k∈[K]\{i} , ZΣ ≥ L.

1 m1 n2 .

(39)

u∈A

Then we let

In the following, we prove the tightened converse bound on P (u) R1 for the case u∈[U] 1{Tu ≥ Vu − s2 } = U − r1 . Define n o (u) E ≜ u ∈ [U] : Tu ≥ Vu − s2 . (46) Then we have |E| = U − r1 . By the security constraint against relays, for each u ∈ [U], we have   X (47a) I Yu ; Wk {WT , ZT } k∈[K]

H Yu1 | {Wk }k∈[K]\{i} , ZΣ

≤ I {Xu,v }v∈[Vu ] ; {Wk }k∈[K] {WT , ZT }

= max H Yu | {Wk }k∈[K]\{i} , ZΣ ≥ u∈A

L . m1

(40)

We assume that in cluster u1 , the dataset Di has the minimum replication factor, and the surviving users H, where (u ) H ⊆ {u1 } × [Vu1 ], |H| = m2 1 , are assigned Di . Thus, (u ) m2 1 R 2 L ≥ H

(Xu1 ,v )(u1 ,v)∈H |{Wk }k∈[K]\{i} , ZΣ

(41a)

≥ I (Xu1 ,v )(u1 ,v)∈H ; Yu1 {Wk }k∈[K]\{i} , ZΣ = H Yu1 {Wk }k∈[K]\{i} , ZΣ

(41b)

− H Yu1 {Wk }k∈[K]\{i} , ZΣ , (Xu1 ,v )(u1 ,v)∈H {z } |

(41c)

L ≥ , m1

(41d)

(12)

= 0.

(47b)

Hence,     X X H Wk WT , ZT  . (48) Wk Yu , WT , ZT  =H  k∈[K]

k∈[K]

On the other hand, the decodability constraint gives ! X H Wk {Yu }u∈[U] = 0.

(49)

k∈[K]

Suppose there exists a non-colluding dataset. For any i ∈ [U]\ E, by (48) and (49) we have   X L = H Wk WT , ZT  (50a) k∈[K]

where (41c) follows since (Xu1 ,v )(u1 ,v)∈Mu1 \H can be recovered from {{Wk }k∈[K]\{i} , ZΣ } and Yu1 is a function of (Xu1 ,v )(u1 ,v)∈Mu1 . Thus, we have R2 ≥

1 (u ) m1 m2 1

1 = . (u) m 1 n2 m1 minu∈[U] m2 1

! X

 X

Wk Yi , {Yu }u∈E , WT , ZT  !

−H

(44b)

= H(Xu,v | Wu,v ) − H(Xu,v | Wu,v , Zu,v )

(44c)

= H(Xu,v | Wu,v )

(44d)

= H(Xu,v ) − I(Xu,v ; Wu,v )

(44e) (44f)

From (43), we obtain maxu∈[U],v∈[Vu ] H(Zu,v ) L maxu∈[U],v∈[Vu ] H(Xu,v ) 1 ≥ ≥ . L m 1 n2

(50b)

k∈[K]

(43)

≥ I(Xu,v ; Zu,v | Wu,v )

= H(Xu,v ),

Wk {Yu }u∈[U] , WT , ZT

k∈[K]

= H

(44a)

(12)

Wk Yi , WT , ZT 



H(Zu,v ) ≥ H(Zu,v | Wu,v )

(3)

 X

k∈[K]

(42)

Finally, we will prove that RZ ≥ m11n2 . For any u ∈ [U] and v ∈ [Vu ], we have

RZ ≥

= H −H

Therefore, taking the worst-case cluster yields R2 ≥



(45a) (45b)

Wk {Yu }u∈[U] , WT , ZT

(50c)

k∈[K]



 X = I Wk ;{Yu }u∈[U]\({i}∪E) Yi ,{Yu }u∈E , WT , ZT (50d) k∈[K]

≤ H {Yu }u∈[U]\({i}∪E) Yi ,{Yu }u∈E , WT , ZT X ≤ H(Yu ),

(50e) (50f)

u∈[U]\({i}∪E)

where (50b) follows from (48) and (49), together with the fact that conditioning reduces entropy. Moreover, (50c) follows since, for every u ∈ E, all surviving user messages in cluster u are generated by colluding users and are therefore determined by (WT , ZT ). Since Yu is a deterministic function of these surviving user messages, conditioning additionally on {Yu }u∈E does not change the conditional entropy. So we have maxu∈[U]\({i}∪E) H(Yu ) ≥ r1 L−1 = m1L−1 and thus R1 ≥ m11−1 .

C. Proof for the third regime We consider the case m1 = r1 = 1 and

u∈[U] 1{Tu ≥

(u)

Vu − s2 } ≥ U − r1 . Define n o (u) E ≜ u ∈ [U] : Tu ≥ Vu − s2 .

(51)

u ∈ E.

(52)

Suppose that there exists at least one non-colluding dataset. Then E ̸= [U], and thus |E| = U − 1. Let u⋆ = [U] \ E denote the unique effective relay. Since every dataset assigned to a cluster in E is contained in WT , every non-colluding dataset can only be assigned to cluster u⋆ . By the security against relay u⋆ in (12), we have (53) I {Xu⋆ ,v }v∈[Vu⋆ ] ; {Wk }k∈[K] WT , ZT = 0. Since Yu⋆ is a deterministic function of the surviving user P messages in cluster u⋆ and W k is a function of k∈[K] {Wk }k∈[K] , the data-processing inequality gives   X I Yu⋆ ; Wk WT , ZT  = 0. (54) k∈[K]

Combining (52) and (54), we obtain   X I Wk ; {Yu }u∈[U] WT , ZT  k∈[K]

 =I

 X

Wk ; Yu⋆ , {Yu }u∈E WT , ZT 

k∈[K]

 =I

 X

Wk ; Yu⋆ WT , ZT  = 0.

(55)

k∈[K]

Since there exists at least one non-colluding dataset and the intermediate outcomes are independent of the keys,   X H Wk WT , ZT  = L. (56) k∈[K]

Hence, from (55)  H

 X

Wk {Yu }u∈[U] , WT , ZT 

(57)

k∈[K]

 =H

 X

Wk WT , ZT  = L.

(58)

k∈[K]

On the other hand, by the decodability constraint in (10),   X H Wk {Yu }u∈[U]  = 0, (59) k∈[K]

(60)

k∈[K]

For each u ∈ E, consider the surviving user set Mu and the colluding user set Tu satisfying Mu ⊆ Tu . This is feasible (u) since |Mu | = Vu − s2 ≤ Tu . By the constraint in (8), H (Yu |WT , ZT ) = 0,

which further implies   X H Wk {Yu }u∈[U] , WT , ZT  = 0.

This contradicts (58). Therefore, the security against relays and the decodability cannot be simultaneously satisfied, and secure distributed linearly separable computation is infeasible P (u) when m1 = 1 and u∈[U] 1{Tu ≥ Vu − s2 } ≥ U − r1 . R EFERENCES [1] R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding: Avoiding stragglers in distributed learning,” in International Conference on Machine Learning. PMLR, 2017, pp. 3368–3376. [2] M. Ye and E. Abbe, “Communication-computation efficient gradient coding,” in International Conference on Machine Learning. PMLR, 2018, pp. 5610–5619. [3] H. Cao, Q. Yan, X. Tang, and G. Han, “Adaptive gradient coding,” IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 717–734, 2021. [4] S. Dutta, V. Cadambe, and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” Advances In Neural Information Processing Systems, vol. 29, 2016. [5] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” IEEE Transactions on Information Theory, vol. 64, no. 3, pp. 1514–1529, 2017. [6] K. Lee, C. Suh, and K. Ramchandran, “High-dimensional coded matrix multiplication,” in 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 2418–2422. [7] S. Dutta, M. Fahim, F. Haddadpour, H. Jeong, V. Cadambe, and P. Grover, “On the optimal recovery threshold of coded matrix multiplication,” IEEE Transactions on Information Theory, vol. 66, no. 1, pp. 278–301, 2019. [8] K. Wan, H. Sun, M. Ji, and G. Caire, “Distributed linearly separable computation,” IEEE Transactions on Information Theory, vol. 68, no. 2, pp. 1259–1278, 2021. [9] ——, “On the tradeoff between computation and communication costs for distributed linearly separable computation,” IEEE Transactions on Communications, vol. 69, no. 11, pp. 7390–7405, 2021. [10] W. Huang, K. Wan, H. Sun, M. Ji, R. C. Qiu, and G. Caire, “Fundamental limits of distributed linearly separable computation under cyclic assignment,” IEEE Transactions on Communications, vol. 74, pp. 5944– 5960, 2026. [11] A. Khalesi and P. Elia, “Multi-user linearly-separable distributed computing,” IEEE Transactions on Information Theory, vol. 69, no. 10, pp. 6314–6339, 2023. [12] ——, “Perfect multi-user distributed computing,” in 2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 2024, pp. 1349–1354. [13] ——, “Tessellated distributed computing,” IEEE Transactions on Information Theory, 2025. [14] K. Namboodiri, E. Peter, D. Malak, and P. Elia, “Fundamental limits of distributed computing for linearly separable functions,” arXiv preprint arXiv:2509.23447, 2025. [15] K. Wan, H. Sun, M. Ji, and G. Caire, “On secure distributed linearly separable computation,” IEEE Journal on Selected Areas in Communications, vol. 40, no. 3, pp. 912–926, 2022. [16] X. Zhang, K. Wan, H. Sun, S. Wang, M. Ji, and G. Caire, “Optimal communication and key rate region for hierarchical secure aggregation with user collusion,” IEEE Transactions on Information Theory, vol. 72, no. 2, pp. 1030–1050, 2026. [17] X. Zhang, Z. Li, K. Wan, H. Sun, M. Ji, and G. Caire, “Fundamental limits of hierarchical secure aggregation with cyclic user association,” arXiv preprint arXiv:2503.04564, 2025. [18] M. Xu, X. Han, K. Wan, and G. Ge, “On hierarchical secure aggregation against relay and user collusion,” arXiv preprint arXiv:2511.20117, 2025. [19] Z. Li, X. Zhang, J. Lv, J. Fan, H. Chen, and G. Caire, “Hierarchical secure aggregation with heterogeneous security constraints and arbitrary user collusion,” arXiv preprint arXiv:2507.14768, 2025. [20] T. Jahani-Nezhad and M. A. Maddah-Ali, “Optimal communicationcomputation trade-off in heterogeneous gradient coding,” IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 3, pp. 1002–1011, 2021.

[21] Z. Zhang, K. Wan, M. Cheng, S. Shao, and G. Caire, “Distributed linearly separable computation with arbitrary heterogeneous data assignment,” arXiv preprint arXiv:2601.10177, 2026. [22] A. Gholami, T. Jahani-Nezhad, K. Wan, and G. Caire, “Hierarchical gradient coding: From optimal design to privacy at intermediate nodes,” 2025. [Online]. Available: https://arxiv.org/abs/2502.18251 [23] Y. Zhao and H. Sun, “Information theoretic secure aggregation with user dropouts,” IEEE Transactions on Information Theory, vol. 68, no. 11, pp. 7471–7484, 2022. [24] ——, “Secure summation: Capacity region, groupwise key, and feasibility,” IEEE Transactions on Information Theory, vol. 70, no. 2, pp. 1376–1387, 2023.

A PPENDIX B P ROOFS OF THE INFORMATION THEORETIC SECURITY AGAINST RELAYS

A. Proof of the information theoretic security We aim to prove that, if Constraint 1 is satisfied, the proposed scheme is information theoretically secure against relays. For relay u ∈ [U], it suffices to consider the case |Tu | ≤ (u) Vu − r2 < Uu , since otherwise all inputs in cluster u are already contained in the side information WT . Define 

 Fu,1 h  ..  (u)  .  = F2

(u)

W′ .

(61)

Fu,Uu To prove the security constraint in (12), we have I {Xu,v }v∈[Vu ] ; {Wk }k∈[K] {WT , ZT } ≤ I {Fu,1 , . . . , Fu,Uu }; {Wk }k∈[K] {WT , ZT } = H {Fu,1 , . . . , Fu,Uu } {WT , ZT } − H {Fu,1 , . . . , Fu,Uu } {Wk }k∈[K] , {WT , ZT } (u) ≤ (Uu − |Tu |)L′ − H B2 N ZTu , ZT[U]\{u}

(62a) (62b)

(62c) (62d)

= (Uu − |Tu |)L′ − (Uu − |Tu |)L′

(62e)

= 0,

(62f)

where (62b) follows since {Xu,v }v∈[Vu ] are in the linear space spanned by {Fu,1 , . . . , Fu,Uu }, and hence are determined by {Fu,1 , . . . , Fu,Uu }. (62d) follows since the messages sent by the colluding users in cluster u are deterministic functions of {WTu , ZTu }; the side information {WTu , ZTu } u reveals ST2,u [Fu,1 ; . . . ; Fu,Uu ]. Since S2,u is generated with elements uniformly i.i.d. over Fq , any |Tu | < Uu rows of S2,u are linearly independent with high probability as q → ∞. Therefore, conditioning on the colluding users’ information removes exactly |Tu | independent linear combinations from {Fu,1 , . . . , Fu,Uu }, and at most (Uu − |Tu |) independent dimensions remain unknown. Meanwhile, by Constraint 1, the (u) row space of B2 is linearly independent of the row space (u) of Ku,T . Hence, the local key space B2 N is independent of the external colluding key information ZT[U]\{u} ≜ Ku,T N. Moreover, the colluding users inside cluster u reveal ZTu ≜ (u) u ST2,u B2 N, which consists of |Tu | independent linear combinations of the local key space. Therefore, after conditioning (u) on ZTu and ZT[U]\{u} , the remaining entropy of B2 N is ′ (Uu − |Tu |)L , which gives (62e). Hence, the security against relays is proved. B. Proof of Constraint 1 Recall that m = m1 n2 , where m1 = r1 and n2 = (u) minu∈[U] m2 . In the relay-to-server layer, the server recovers Un2 linear combinations, among which the first m rows correspond to the desired aggregation task and the remaining

Un2 − m rows are virtual key-encrypted combinations with key coefficients uniformly i.i.d. over Fq . Hence, rank(B) = Un2 − m.

(63)

For each cluster u ∈ [U], relay u receives Uu linear combinations from the surviving users. The corresponding (u) local key coefficient matrix B2 can be written as (u) (u) S B1 B2 = 1 , (64) B2,u (u)

where the first n2 rows, S1 B1 , correspond to the relay-layer task assigned to cluster u, and B2,u is generated with elements uniformly i.i.d. over Fq . For relay u ∈ [U], let n o (i) Bu ≜ i ∈ [U] \ {u} : |Ti | > Vi − r2 (65)

The first term in (72) lies in the top-layer key space, while the second term lies in the space generated by B2,i . Since S2,i is generated with elements uniformly i.i.d. over Fq and |Ti | ≤ Ui − n2 , the submatrix ST2,ii (., [n2 + 1 : Ui ]) has rank equal to |Ti | with high probability. Moreover, B2,i is generated independently with elements uniformly i.i.d. over Fq . Therefore, the second term in (72) contributes |Ti | linearly independent key directions outside the top-layer key space B1 . Next, consider a cluster i ∈ Bu . Since cluster i is colluding, all datasets assigned to this cluster are already covered by the colluding users. For the purpose of proving security against relays, we may consider the worst case where the colluding users reveal the whole local key space of cluster i, namely (i) (i) S B B2 N = 1 1 N. (73) B2,i Thus, the matrix in (67) can be written as   (u) S1 B1   B2,u   (Bu (1))   S1 B1     B2,Bu (1)     .   . .    . (Bu (|Bu |))   S B 1 1     B 2,B (|B |) u u    STGu (1) B(Gu (1))    2,Gu (1) 2   ..   .   TGu (|Gu |) (Gu (|Gu |)) S2,G B 2 u (|Gu |)

denote the set of colluding clusters other than cluster u, and let n o (i) Gu ≜ i ∈ [U] \ {u} : |Ti | ≤ Vi − r2 (66) denote the remaining non-colluding clusters. Since the total number of colluding clusters satisfies |B| ≤ U − r1 − 1 and cluster u is non-colluding, we have |Bu | ≤ U − r1 − 1. We aim to prove that, for each relay u ∈ [U] and each collection of colluding user sets {Ti : i ∈ [U] \ {u}} satisfying |Ti | ≤ Ti , the matrix (u) B2 (67) Ku,T has row-wise full rank, where Ku,T denotes the key coefficient matrix revealed to relay u through collusion with users in the external clusters. Since Bu ∪ Gu = [U] \ {u}, the external key information can be decomposed according to the two types of clusters in Bu and Gu . For each cluster i ∈ Gu , we have (i)

|Ti | ≤ Vi − r2 < Ui .

(68)

For each i ∈ Gu , since (i)

(i)

n2 ≤ m2 = r2 − s2 ,

(69)

it follows that (i)

(i)

|Ti | ≤ Vi − r2 ≤ Vi − s2 − n2 = Ui − n2 .

(70)

The key information revealed by the colluding users in cluster (i) i is ST2,ii B2 N. Using (i) (i) S B B2 = 1 1 , (71) B2,i we can write (i)

(i)

ST2,ii B2 = ST2,ii (., [n2 ])S1 B1 + ST2,ii (., [n2 + 1 : Ui ])B2,i . (72)

(74)

We check that      (u) (u) (u) S1 S1 B1 S1  (Bu (1))  (Bu (1))    (B (1))   0  S1  S1  B1   S1 u       B = = .. .. ..  B .   1          . . . 

(B (|Bu |))

S1 u

(B (|Bu |))

S1 u

(B (|Bu |))

S1 u

(75) Since B and S1 are generated with elements uniformly i.i.d. over Fq , and (|Bu | + 1)n2 ≤ (U − r1 )n2 = Un2 − m = rank(B),

(76)

the matrix in (75) has rank equal to (|Bu | + 1)n2 , and these row vectors in (75) are linearly independent with high probability as q → ∞. Moreover, the elements in B2,u and {B2,i : i ∈ Bu } are generated independently with elements uniformly i.i.d. over Fq . Hence, the matrix in Constraint 1 is row-wise full rank with high probability. A PPENDIX C P ROOFS OF THE INFORMATION THEORETIC SECURITY AGAINST SERVER

A. Proof of the information theoretic security After receiving the messages from all relays, the server can recover F 0 W ′ [F1 B1 ]W = . (77) V B N

We denote 



T1   ..   .    Tm  F    T1,1  = V     ..   . T1,Un2 −m

0 W , B N

(78)

where {TP 1 , . . . , Tm } correspond to the desired aggregation task FW = k∈[K] Wk . Besides the relay-to-server transmissions, the server can obtain key information through collusion. Recall that KT denotes the total key coefficient matrix revealed by the colluding users. Define ∆T ≜ dim (rowspan(B) ∩ rowspan(KT )) .

(79)

By Constraint 2, we have rowspan(B) ∩ rowspan(KT ) ⊆ rowspan SB 1 B1 .

(80)

For each u ∈ B, all datasets assigned to cluster u are already covered by the colluding users. Hence, the corresponding data (u) part S1 F1 W is contained in WT , and thus H SB (81) 1 F1 W WT = 0. To prove the security constraint in (11), we have X Wk , {WT , ZT } I {Yu }u∈[U] ; {Wk }k∈[K]

(82a)

k∈[K]

≤ I {T1 , . . . , Tm , T1,1 , . . . , T1,Un2 −m }; {Wk }k∈[K] X Wk , {WT , ZT }

data part CT SB 1 F1 W is known from WT by (81). Therefore, ′ CT SB 1 [F1 B1 ]W is known from WT and ZT , which gives ∆T independent linear combinations of [F1 B1 ]W′ . Since the first m rows correspond to the desired aggregation and are already conditioned on, this further determines ∆T independent linear combinations of the virtual vectors T1,1 , . . . , T1,Un2 −m . Therefore, at most Un2 − m − ∆T dimensions of the virtual vectors remain unknown. (82f) follows since the top-layer key space BN, which masks the virtual linear combinations T1,1 , . . . , T1,Un2 −m , contains Un2 −m independent key dimensions, and the colluding key information ZT ≜ KT N reveals exactly ∆T dimensions inside rowspan(B), which gives (82f). B. Proof of Constraint 2 We aim to prove that for each collection of colluding user sets {Ti : i ∈ [U]} satisfying |Ti | ≤ Ti , rowspan(B) ∩ rowspan(KT ) ⊆ rowspan SB (83) 1 B1 . Recall that 0 B1 = , B and for each cluster i ∈ [U], (i) B2 =

(85)

(i)

KT = ST2,ii B2

(i)

= ST2,ii (., [n2 ])S1 B1 + ST2,ii (., [n2 + 1 : Ui ])B2,i , (86)

k∈[K]

= I {T1,1 , . . . , T1,Un2 −m }; {Wk }k∈[K] X Wk , {WT , ZT }

(i) S1 B1 , B2,i

where B2,i is generated independently with elements uniformly i.i.d. over Fq . Let G ≜ [U]\B denote the set of non-colluding clusters. For (i) each i ∈ G, the revealed key coefficient matrix KT satisfies (i)

(82b)

(84)

and (82c)

k∈[K]

(i)

|Ti | ≤ Vi − r2 ≤ Vi − s2 − n2 = Ui − n2 , (i)

X = H {T1,1 , . . . , T1,Un2 −m } Wk , {WT , ZT } k∈[K]

− H {T1,1 , . . . , T1,Un2 −m } {Wk }k∈[K] , {WT , ZT } (82d) ≤ (Un2 − m − ∆T ) L′ − H BN ZT (82e) = (Un2 − m − ∆T ) L′ − (Un2 − m − ∆T ) L′

(82f)

= 0,

(82g)

where (82b) follows since {Yu }u∈[U] are linear combinations of {T1 , . . . , Tm , T1,1 , . . . , T1,Un2 −m }, and hence are determined by these recovered linear combinations. (82c) follows since {T1 , . . . , Tm } correspond P to the desired aggregation task and are already given by k∈[K] Wk . (82e) follows since, by the definition of ∆T , the colluding users reveal ∆T key dimensions inside the top-layer key space rowspan(B). By Constraint 2, the ∆T revealed key dimensions inside rowspan(B) lie in rowspan(SB 1 B1 ). Hence, there exists a row-wise full rank coefficient matrix CT of dimension ∆T × |B|n2 . The key part CT SB 1 B1 N is known from ZT . The

(87) (i)

where the second inequality follows from n2 ≤ m2 = r2 − (i) s2 . Hence, ST2,ii (., [n2 + 1 : Ui ]) has at least |Ti | columns, and since S2,i is generated with elements uniformly i.i.d. over Fq , this submatrix has rank equal to |Ti | with high probability. Since B2,i is generated with elements uniformly i.i.d. over Fq , (i) all rows in KT are independent of rowspan(B) with high probability. For each i ∈ B, we consider the worst case where the colluding users reveal the whole local key space of cluster i, which is (i) (i) (i) S B (88) KT = B2 = 1 1 . B2,i Again, the rows of B2,i are independent of rowspan(B) with high probability. Hence, the only rows in the revealed key information that can overlap with rowspan(B) are the top(i) layer key rows S1 B1 for i ∈ B. Therefore, rowspan(B) ∩ rowspan(KT ) ⊆ rowspan SB (89) 1 B1 , which proves Constraint 2.

Record · ID 1108737 · SHA-256 89ec2081ea76900a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.