Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.26391

Multi-Server Secure Aggregation with Arbitrary Collusion and Heterogeneous Security Constraints

Zhou Li, Xiang Zhang, Jiguang He, Giuseppe Caire

Published Apr 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2604.26391

Related papers

Optimal Key Rates for Decentralized Secure Aggregation with Arbitrary Collusion and Heterogeneous Security Constraints

Li Zhou, Xiang Zhang, Giuseppe Caire

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} $\bm{\mathcal{S}}$, must be protected from another predefined collection, the \emph{collusion set} $\bm{\mathcal{T}}$. For an arbitrary security set $\mathcal{S}\in \bm{\mathcal{S}}$ and an arbitrary collusion set $\mathcal{T}\in \bm{\mathcal{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.

arXiv:2512.16112•Dec 18, 2025•0 citations

On the Fundamental Limits of Secure Summation and MDS Variable Generation

Yizhou Zhao

Secure multiparty computation refers to the problem where a number of users wish to securely compute a function on their inputs without revealing any unnecessary information. This dissertation focuses on the fundamental limits of secure summation under different constraints. We first focus on the minimal model of secure computation, in which two users each hold an input and wish to securely compute a function of their inputs at the server. We propose a novel scheme base on the algebraic structure of finite field and modulo ring of integers. Then we extend the minimal model of secure computation, in which K users wish to securely compute the sum of their inputs at the server. We prove a folklore result on the limits of communication cost and randomness cost. Then we characterized the optimal communication cost with user dropouts constraint, when some users may lose connection to the server and the server wishes to compute the sum of remaining inputs. Next, we characterize the optimal communication and randomness cost for symmetric groupwise keys and find the feasibility condition for arbitrary groupwise keys. Last, we study the secure summation with user selection, such that the server may select any subset of users to compute the sum of their inputs. This leads us to the MDS variable generation problem. We characterize the optimal individual key rate and the result is interestingly the harmonic number.

•Jul 1, 2023•0 citations

Weakly Secure Summation With Colluding Users

Zhou Li, Yizhou Zhao, Hua Sun

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.

IEEE Transactions on Information Theory•May 13, 2025•9 citations

Post-Quantum Secure Aggregation via Code-Based Homomorphic Encryption

Sebastian Bitzer, Maximilian K. Egger, Mumin Liu +1 more

Secure aggregation lets a server learn the sum of inputs from multiple users without learning individual contributions. Recent single-server protocols achieve this with key- and message-additive homomorphic encryption (KAHE), but existing instantiations rely on lattice assumptions. We instantiate a KAHE from the Learning Parity with Noise (LPN) assumption and analyze the challenges that arise with the Hamming metric. Decryption of the aggregate amounts to decoding over a q-ary symmetric channel whose crossover probability grows with the number of users. Security under leakage of the key sum reduces to LPN with a noise rate that is quadratic in the KAHE noise rate, and a matching attack shows that this loss is inherent when all but two users collude. Asymptotically, we characterize the optimal communication cost in closed form, showing that the overhead over the raw payload vanishes as the input length grows, and decouple the field size from the input range via the Chinese remainder theorem. In cross-silo settings, our protocol requires less communication than information-theoretically secure aggregation for moderate to high collusion.

arXiv:2601.13031•Jan 19, 2026•0 citations

Constrained Colluding Eavesdroppers: An Information-Theoretic Model

Mahtab Mirmohseni, Panos Papadimitratos

We study the secrecy capacity in the vicinity of colluding eavesdroppers. Contrary to the perfect collusion assumption in previous works, our new information-theoretic model considers constraints in collusion. We derive the achievable secure rates (lower bounds on the perfect secrecy capacity), both for the discrete memoryless and Gaussian channels. We also compare the proposed rates to the non-colluding and perfect colluding cases.

arXiv:1312.3200•Dec 11, 2013•2 citations

Information Theoretic Framework for Single and Multi-Server Private Authentication

Narges Kazempour, Mahtab Mirmohseni, Mohammad Reza Aref

In this paper, the private authentication problem is considered that consists of a certificate authority, a verifier (or verifiers), many legitimate users (prover) and arbitrary number of attackers. Each legitimate user wants to be authenticated (using his personal key) by the verifier(s), while simultaneously staying anonymous. However, an attacker must fail to be authenticated. We analyze this problem from an information theoretical perspective. First, we propose a general interactive information-theoretic model. As a metric to measure reliability, we consider the key rate whose rate maximization has a trade-off with establishing privacy. We consider the problem in two different setups: single server and multi-server scenarios. In single server scenario one verifier is considered, which all the provers connected to. In multi-server scenario, $n$ verifiers are assumed, where each verifier is connected to a subset of users. For both scenarios, two regimes are considered: finite size and asymptotic regimes. In single server scenario, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. Moreover, we show that our scheme achieves capacity in the asymptotic regime. For finite size regime our scheme achieves capacity for large field size. In multi-server scenario two methods are considered: individual and distributed authentication. In individual authentication, the process of authentication is done by one single verifier. In this case, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. In distributed authentication, the process of authentication is done collaboratively by all the verifiers. For this case, when all the provers are connected to all the verifiers, we propose an optimal scheme in finite size regime.

•Jan 17, 2019•1 citation
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 KKK 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 TTT 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\bm{\mathcal{S}}S, must be protected from another predefined collection, the \emph{collusion set} T\bm{\mathcal{T}}T. For an arbitrary security set S∈S\mathcal{S}\in \bm{\mathcal{S}}S∈S and an arbitrary collusion set T∈T\mathcal{T}\in \bm{\mathcal{T}}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.
Secure multiparty computation refers to the problem where a number of users wish to securely compute a function on their inputs without revealing any unnecessary information. This dissertation focuses on the fundamental limits of secure summation under different constraints. We first focus on the minimal model of secure computation, in which two users each hold an input and wish to securely compute a function of their inputs at the server. We propose a novel scheme base on the algebraic structure of finite field and modulo ring of integers. Then we extend the minimal model of secure computation, in which K users wish to securely compute the sum of their inputs at the server. We prove a folklore result on the limits of communication cost and randomness cost. Then we characterized the optimal communication cost with user dropouts constraint, when some users may lose connection to the server and the server wishes to compute the sum of remaining inputs. Next, we characterize the optimal communication and randomness cost for symmetric groupwise keys and find the feasibility condition for arbitrary groupwise keys. Last, we study the secure summation with user selection, such that the server may select any subset of users to compute the sum of their inputs. This leads us to the MDS variable generation problem. We characterize the optimal individual key rate and the result is interestingly the harmonic number.
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.
Secure aggregation lets a server learn the sum of inputs from multiple users without learning individual contributions. Recent single-server protocols achieve this with key- and message-additive homomorphic encryption (KAHE), but existing instantiations rely on lattice assumptions. We instantiate a KAHE from the Learning Parity with Noise (LPN) assumption and analyze the challenges that arise with the Hamming metric. Decryption of the aggregate amounts to decoding over a q-ary symmetric channel whose crossover probability grows with the number of users. Security under leakage of the key sum reduces to LPN with a noise rate that is quadratic in the KAHE noise rate, and a matching attack shows that this loss is inherent when all but two users collude. Asymptotically, we characterize the optimal communication cost in closed form, showing that the overhead over the raw payload vanishes as the input length grows, and decouple the field size from the input range via the Chinese remainder theorem. In cross-silo settings, our protocol requires less communication than information-theoretically secure aggregation for moderate to high collusion.
In this paper, the private authentication problem is considered that consists of a certificate authority, a verifier (or verifiers), many legitimate users (prover) and arbitrary number of attackers. Each legitimate user wants to be authenticated (using his personal key) by the verifier(s), while simultaneously staying anonymous. However, an attacker must fail to be authenticated. We analyze this problem from an information theoretical perspective. First, we propose a general interactive information-theoretic model. As a metric to measure reliability, we consider the key rate whose rate maximization has a trade-off with establishing privacy. We consider the problem in two different setups: single server and multi-server scenarios. In single server scenario one verifier is considered, which all the provers connected to. In multi-server scenario, nnn verifiers are assumed, where each verifier is connected to a subset of users. For both scenarios, two regimes are considered: finite size and asymptotic regimes. In single server scenario, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. Moreover, we show that our scheme achieves capacity in the asymptotic regime. For finite size regime our scheme achieves capacity for large field size. In multi-server scenario two methods are considered: individual and distributed authentication. In individual authentication, the process of authentication is done by one single verifier. In this case, for both regimes, we propose schemes that satisfy completeness, soundness and privacy properties. In distributed authentication, the process of authentication is done collaboratively by all the verifiers. For this case, when all the provers are connected to all the verifiers, we propose an optimal scheme in finite size regime.