MDS Variable Generation and Secure Summation With User Selection
Yizhou Zhao, Hua Sun · IEEE Transactions on Information Theory · 2025
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\}$.