We study the multi-server secure aggregation problem in a two-hop network, where users communicate with their designated server, and servers exchange messages to compute a global sum under the information-theoretic threat of up to T colluding users. We characterize the complete optimal rate region involving user-server and server-server communication rates, individual key rate, and common randomness (source key) rate.Our results show that the minimum communication and individual key rates are all one symbol per input symbol. The optimal source key rate is min{U + V + T − 2,UV − 1}, where U and V are the numbers of servers and users per server, respectively. Achievability is proven via a novel linear key scheme, and the converse follows from tight entropy bounds derived from correctness and security constraints.
We study the multi-server secure aggregation problem in a two-hop network, where users communicate with their designated server, and servers exchange messages to compute a global sum under the information-theoretic threat of up to T colluding users. We characterize the complete optimal rate region involving user-server and server-server communication rates, individual key rate, and common randomness (source key) rate.Our results show that the minimum communication and individual key rates are all one symbol per input symbol. The optimal source key rate is min{U + V + T − 2,UV − 1}, where U and V are the numbers of servers and users per server, respectively. Achievability is proven via a novel linear key scheme, and the converse follows from tight entropy bounds derived from correctness and security constraints.
We study the fundamental limits of multi-server secure aggregation over a two-hop network where multiple servers, each connected to a disjoint subset of users, jointly compute the sum of all users' inputs. The goal is to ensure that no server can infer any information about prescribed subsets of inputs beyond the desired aggregate, even when colluding with an arbitrary subset of users. Existing works largely focus on homogeneous security requirements, where all inputs are protected against colluding sets up to a given size. Such formulations are insufficient to capture more general scenarios in which different subsets of inputs may require protection against different collusion patterns. In this paper, we consider a general model with heterogeneous security requirements and arbitrary user collusion. We characterize the communication rates for all parameter regimes, and determine the minimum key rate required for secure aggregation in most regimes. In particular, we establish tight information-theoretic lower bounds and matching achievable schemes in a broad class of regimes. For the remaining regime, we derive a general lower bound together with an achievable scheme that attains it within a bounded gap. Our results reveal how the interplay between network topology and heterogeneous security constraints fundamentally determines the communication and key generation requirements, and generalize existing results on secure aggregation.
Decentralized secure aggregation (DSA) considers a fully-connected network of K users, where each pair of users can communicate bidirectionally over an error-free channel. Each user holds a private input, and the goal is for each user to compute the sum of all inputs without revealing any additional information, even in the presence of collusion among up to T users. Traditional DSA typically requires large key sizes to protect all information except for the input sum and the information of colluding users. To mitigate the source keys overhead, we study decentralized secure aggregation with arbitrary collusion and heterogeneous security constraints. In this setting, the inputs of a predefined collection of user subsets, called the \emph{security set} S, must be protected from another predefined collection, the \emph{collusion set} T. For an arbitrary security set S∈S and an arbitrary collusion set T∈T, we characterize the optimal communication and source key rates. A key contribution of this work is the characterization of the optimal source key rate, i.e., the minimum number of key bits per input bit that must be shared among users for decentralized secure aggregation with arbitrary collusion and heterogeneous security constraints to be feasible. In general, this characterization reduces to solving a linear program.
In secure summation, K parties each hold an input, and the sum of the inputs is computed at one party, securely against at most T colluding parties. Communication typically takes one hop: each party sends one message directly to the party that computes the sum, using correlated randomness that is independent of the inputs and held in advance. We consider interactive secure summation, where every pair of parties is connected by a secure link, so that each party can send messages to every other party, each party has only independent local randomness, and the messages may depend on the inputs and on earlier messages over multiple rounds. We characterize the capacity region, the set of achievable rates of communication, counting all messages exchanged among the parties over all rounds, and of the randomness of every party, counted in symbols per symbol of the sum. For 0≤T≤K−2, the optimal communication rate is K(K−1)/(K−T), and the randomness rates form a polyhedron with, up to a relabeling of the parties, a single extreme point: T parties have the randomness rates (K+T−2t)/(K−T), t=1,…,T, and the others none. In particular, the optimal total randomness rate is T(K−1)/(K−T). Linear schemes achieve every extreme point together with the optimal communication rate. The same techniques give the capacity region when every party recovers the sum and when the sum is computed at a server without input.
Decentralized secure aggregation (DSA) considers a fully-connected network of K users, each holding a private input. The goal is for every user to compute the sum of all inputs without revealing additional information, even if up to T users collude. Traditional DSA often requires large key sizes to protect all information except the input sum. To reduce key overhead, we study DSA with arbitrary collusion and heterogeneous security constraints, where the inputs of predefined user subsets, called the security set S, must be protected from predefined collusion sets T. For any S∈S and T∈T, we characterize the optimal communication and source key rates. In particular, we determine the minimum number of key bits per input bit required for secure aggregation, which in general reduces to solving a linear program.
In secure summation,Kusers, each holds an input, wish to compute the sum of the inputs at a server without revealing any information aboutall the inputseven if the server may collude withan arbitrary subset of users. In this work, we relax the security and colluding constraints, where the set of inputs whose information is prohibited from leakage is from a predetermined collection of sets (e.g., any set of up toSinputs) and the set of colluding users is from another predetermined collection of sets (e.g., any set of up toTusers). For arbitrary collection of security input sets and colluding user sets, we characterize the optimal randomness assumption, i.e., the minimum number of key bits that need to be held by the users, per input bit, for weakly secure summation to be feasible, which generally involves solving a linear program.
We consider a two-source two-destination two-hop relay network, where all data communication must be kept secret from the relay node. The model considered is the simplest primitive that embodies a multi-transmitter multi-receiver network that needs to communicate sharing an untrusted relay node. We focus on two scenarios. In the first scenario, each source aims to send two messages to be kept secret from the relay: a common message that should be decoded by both destinations, and a private message that should be decoded by the first destination while kept secret from the second one. We define an achievable rate region by utilizing stochastic encoding at the sources, the Gaussian noise cooperative jamming from the destinations, and compress-and-forward at the relay. In the second scenario, each source aims to send a confidential message to its intended destination, which should be kept secret from the other one as well as the relay. We define an achievable rate region using a combination of nested lattice codes and random binning at the sources, structured cooperative jamming from destinations, and scaled compute-and-forward at the relay. We also derive genie-aided outer bounds on the secrecy rate regions. We present numerical results that demonstrate the performance of the proposed achievable schemes. Overall, this paper provides insights into how to utilize an untrusted relay to communicate to destinations with different levels of security clearance, and how intentional interference is an enabler of communication.