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:2211.01220 · IEEE Transactions on Information Theory

MDS Variable Generation and Secure Summation With User Selection

Yizhou Zhao, Hua Sun

Published Feb 13, 2025• 14 citations
arXivHTMLPDF

Abstract

A collection ofKrandom variables are called$(K,n)$-MDS if anynof theKvariables are independent and determine all remaining variables. In the MDS variable generation problem,Kusers wish to generate variables that are$(K,n)$-MDS using a randomness variable owned by each user. We show that to generate 1 bit of$(K,n)$-MDS variables for each$n \in \{1,2,\cdots , K\}$, the minimum size of the randomness variable at each user is$1 + 1/2 + \cdots + 1/K$bits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset ofKusers and securely compute the sum of the inputs of the selected users. We show that to compute 1 bit of an arbitrarily chosen sum securely, the minimum size of the key held by each user is$1 + 1/2 + \cdots + 1/(K-1)$bits, whose achievability uses the generation of$(K,n)$-MDS variables for$n \in \{1,2,\cdots ,K-1\}$.

DOI
10.1109/tit.2025.3541551

Related papers

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

The Optimal Rate of MDS Variable Generation

Yizhou Zhao, Hua Sun

A collection of K random variables are called (K,n)-MDS if any n of the K variables are independent and determine all remaining variables. In the MDS variable generation problem, K users wish to generate variables that are (K,n)-MDS using a randomness variable owned by each user. We show that to generate 1 bit of (K,n)-MDS variables for each n ∈ {1,2, ⋯ ,K}, the minimum size of the randomness variable at each user is 1+1/2+ ⋯ +1/K bits.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2023•9 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

The Capacity of Interactive Secure Summation

Hua Sun

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\le T\le 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,\ldots,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.

arXiv:2610.29954•Oct 21, 2026•0 citations

Secure Modulo Zero-Sum Randomness as Cryptographic Resource.

Masahito Hayashi, Takeshi Koshiba

•Jan 1, 2018•4 citations

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

Zhou Li, Xiang Zhang, Jiguang He +1 more

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.

arXiv:2604.26391•Apr 29, 2026•0 citations
A collection ofKrandom variables are called(K,n)(K,n)(K,n)-MDS if anynof theKvariables are independent and determine all remaining variables. In the MDS variable generation problem,Kusers wish to generate variables that are(K,n)(K,n)(K,n)-MDS using a randomness variable owned by each user. We show that to generate 1 bit of(K,n)(K,n)(K,n)-MDS variables for eachn∈{1,2,⋯ ,K}n \in \{1,2,\cdots , K\}n∈{1,2,⋯,K}, the minimum size of the randomness variable at each user is1+1/2+⋯+1/K1 + 1/2 + \cdots + 1/K1+1/2+⋯+1/Kbits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset ofKusers and securely compute the sum of the inputs of the selected users. We show that to compute 1 bit of an arbitrarily chosen sum securely, the minimum size of the key held by each user is1+1/2+⋯+1/(K−1)1 + 1/2 + \cdots + 1/(K-1)1+1/2+⋯+1/(K−1)bits, whose achievability uses the generation of(K,n)(K,n)(K,n)-MDS variables forn∈{1,2,⋯ ,K−1}n \in \{1,2,\cdots ,K-1\}n∈{1,2,⋯,K−1}.
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.
In secure summation, KKK parties each hold an input, and the sum of the inputs is computed at one party, securely against at most TTT 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−20\le T\le K-20≤T≤K−2, the optimal communication rate is K(K−1)/(K−T)K(K-1)/(K-T)K(K−1)/(K−T), and the randomness rates form a polyhedron with, up to a relabeling of the parties, a single extreme point: TTT parties have the randomness rates (K+T−2t)/(K−T)(K+T-2t)/(K-T)(K+T−2t)/(K−T), t=1,…,Tt=1,\ldots,Tt=1,…,T, and the others none. In particular, the optimal total randomness rate is T(K−1)/(K−T)T(K-1)/(K-T)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.
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.