MDS Variable Generation and Secure Summation With User Selection

A collection of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> random variables are called <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(K,n)$ </tex-math></inline-formula>-MDS if any <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> of the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> variables are independent and determine all remaining variables. In the MDS variable generation problem, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> users wish to generate variables that are <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(K,n)$ </tex-math></inline-formula>-MDS using a randomness variable owned by each user. We show that to generate 1 bit of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(K,n)$ </tex-math></inline-formula>-MDS variables for each <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \in \{1,2,\cdots , K\}$ </tex-math></inline-formula>, the minimum size of the randomness variable at each user is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1 + 1/2 + \cdots + 1/K$ </tex-math></inline-formula> bits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> users 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1 + 1/2 + \cdots + 1/(K-1)$ </tex-math></inline-formula> bits, whose achievability uses the generation of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(K,n)$ </tex-math></inline-formula>-MDS variables for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \in \{1,2,\cdots ,K-1\}$ </tex-math></inline-formula>.