# The Capacity Region of Information Theoretic Secure Aggregation with Uncoded
Groupwise Keys

Kai Wan, Hua Sun, Mingyue Ji, Tiebin Mi, and Giuseppe Caire  K. Wan and T. Mi
are with the School of Electronic Information and Communications, Huazhong
University of Science and Technology, 430074 Wuhan, China, (e-mail:
{kai_wan,mitiebin}@hust.edu.cn). The work of K. Wan and T. Mi was partially
funded by the National Natural Science Foundation of China (NSFC-12141107). M.
Ji is with the Electrical and Computer Engineering Department, University of
Utah, Salt Lake City, UT 84112, USA (e-mail: mingyue.ji@utah.edu). The work of
M. Ji was supported in part by NSF CAREER Award 2145835 and NSF Award 231222.
H. Sun is with the Department of Electrical Engineering, University of North
Texas, Denton, TX 76203, USA (email: hua.sun@unt.edu). The work of H. Sun was
supported in part by NSF Awards 2007108 and 2045656. G. Caire is with the
Electrical Engineering and Computer Science Department, Technische Universität
Berlin, 10587 Berlin, Germany (e-mail: caire@tu-berlin.de). The work of G.
Caire was partially funded by the European Research Council under the ERC
Advanced Grant N. 789190, CARENET.

###### Abstract

This paper considers the secure aggregation problem for federated learning
under an information theoretic cryptographic formulation, where distributed
training nodes (referred to as users) train models based on their own local
data and a curious-but-honest server aggregates the trained models without
retrieving other information about users’ local data. Secure aggregation
generally contains two phases, namely key sharing phase and model aggregation
phase. Due to the common effect of user dropouts in federated learning, the
model aggregation phase should contain two rounds, where in the first round
the users transmit masked models and, in the second round, according to the
identity of surviving users after the first round, these surviving users
transmit some further messages to help the server decrypt the sum of users’
trained models. The objective of the considered information theoretic
formulation is to characterize the capacity region of the communication rates
in the two rounds from the users to the server in the model aggregation phase,
assuming that key sharing has already been performed offline in prior. In this
context, Zhao and Sun completely characterized the capacity region under the
assumption that the keys can be arbitrary random variables. More recently, an
additional constraint, known as “uncoded groupwise keys,” has been introduced.
This constraint entails the presence of multiple independent keys within the
system, with each key being shared by precisely ${\mathsf{S}}$ users, where
${\mathsf{S}}$ is a defined system parameter. The capacity region for the
information-theoretic secure aggregation problem with uncoded groupwise keys
was established in our recent work subject to the condition
${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$, where ${\mathsf{K}}$ is the number
of total users and ${\mathsf{U}}$ is the designed minimum number of surviving
users (which is another system parameter). In this paper we fully characterize
of the the capacity region for this problem by proposing a new converse bound
and an achievable scheme. Experimental results over the Tencent Cloud show the
improvement on the model aggregation time compared to the original secure
aggregation scheme.

###### Index Terms:

Secure aggregation, federated learning, uncoded groupwise keys, information
theoretic security

##  I Introduction

###  I-A Background on secure aggregation for federated learning

Federated learning is a decentralized machine learning approach that enables
multiple devices or users (such as smartphones, edge devices, or Internet of
Things devices) to collaboratively train a shared model without sharing their
local raw data to the central server [1, 2, 3, 4]. Rather than centralizing
all data in a single location, federated learning allows each device training
by using its own local data. After initialization, the process of federated
learning involves several iterations among the users and the server. In one
iteration, each user trains the model using its own local data without sharing
it with the central server. After training on local data, the users send their
model updates (weights or gradients) to the server. Then the central server
collects the model updates from all the users and aggregates the updated
models to create an updated global model. Federated learning has two main
advantages over traditional centralized and distributed learning: (i) it
reduces communication costs and eliminates the need for frequent data
transfers; (ii) it preserves data privacy against the server by keeping data
local. Despite these advantages, federated learning also suffers from some
challenges. On the one hand, assume that the training devices/users are
smartphones or edge devices; during the training process of federated
learning, the server may lose the connectivity to some users due to user
mobility and fluctuating communication quality. Thus an efficient federated
learning scenario should be resilient to this unpredictable effect of user
dropouts. On the other hand, each user needs to transmit to the server the
computed model in terms of the local data; thus the information of local data
can be leaked at some level to the server, and this is known as the model
inversion attacks in federated learning [5].

To deal with the effect of user dropouts and strengthen local data privacy in
federated learning, a new cryptographic problem, referred to as secure
aggregation, was originally introduced in [6]. Except the desired sum of the
users’ updated models, the server should not learn other information about the
users’ local data. In order to guarantee the computational or information
theoretic security, the key-based encryption could be used, where keys are
shared among the users and thus the users’ computed updated models (e.g., sub-
gradients) could be masked by the keys. The keys are generated and then shared
to the users according to some key generation protocols. If the key generation
is independent of the training data, the key sharing is called offline;
otherwise, it is called online. Model aggregation follows key sharing, where
the users compute, mask, and send their computed updated models to the server.
For the resilience to user dropouts, multi-round communications among the
users and server could be used, where in the first round the users send masked
updated models and in the remaining rounds the users send some messages
composed of keys. The number of rounds depend on the threat models of the
server (e.g., the server may be honest-but-curious, or malicious and lie on
the identity of the dropping users, or even collude with some users). The
secure aggregation protocol in [6] uses the pairwise offline key sharing
(i.e., each pair of users share a key) based on Shamir’s secret sharing [7] in
order to deal with user dropouts.

Following the secure aggregation problem with user dropouts in [6], several
works have developed more efficient and/or more secure schemes for
aggregation, for example, by using common seeds through homomorphic
pseudorandom generator [8], secure multi-party computing [9], non-pairwise
keys [10], online key sharing [11, 12, 13], improved El Gamal encryption [14].
The readers can refer to the survey for more details [15, 16].

###  I-B Information theoretic secure aggregation

In this paper, we follow the $({\mathsf{K}},{\mathsf{U}})$ information
theoretic formulation on secure aggregation with user dropouts and offline key
sharing proposed in [10], where ${\mathsf{K}}$ represents the number of users
in the system and ${\mathsf{U}}$ represents the minimum number of non-dropped
users. The input vector (i.e., updated model) of each user $k$ is denoted by
$W_{k}$, which contains ${\mathsf{L}}$ uniform and i.i.d. symbols over a
finite field.111 Note that the system is designed to tolerate up to
${\mathsf{K}}-{\mathsf{U}}$ user dropouts. If more than
${\mathsf{K}}-{\mathsf{U}}$ users drop, there is insufficient data for update
and the server does not update the model and will ask for a retransmission. In
this paper, we directly assume that there are at most
${\mathsf{K}}-{\mathsf{U}}$ user dropouts.  The main information theoretic
problem for this model is to determine the optimal transmission in the model
aggregation phase with the assumption that enough keys have been shared among
the users in a prior key sharing phase, such that the information theoretic
security of the users’ local data is protected against the server (with the
exception of the sum of the updated models of the non-dropped users).222
Information theoretic security was proposed in the seminal work by Shannon
[17], under which constraint even if the adversary has infinite computation
power it still cannot get any information about the data. In the literature of
secure aggregation with user dropouts, the secure aggregation schemes proposed
in [10, 18, 13] guarantee the information theoretic security constraint. Thus
each user $k$ has a key $Z_{k}$, which can be any random variable independent
of $W_{1},\ldots,W_{{\mathsf{K}}}$. It was proved in [10] that to preserve the
security of users’ local data against the honest-but-curious server with the
existence of user dropouts, two-round transmission in the model aggregation
phase is necessary and also sufficient. In the first round, each user masks
its input vector by the stored key and transmits the masked input vector to
the server. The server receives and then returns a feedback to the non-dropped
users about the identity of the non-dropped users. In the second round, each
non-dropped user further transmits a coded message as a function of its local
data, key, and the server feedback. The users may also drop in the second
round; the secure aggregation scheme should guarantee that by the two-round
transmission the server could recover the sum of the input vectors of the non-
dropped users in the first round. The objective of this problem is to
characterize the region of all possible achievable rate tuples
$({\mathsf{R}}_{1},{\mathsf{R}}_{2})$, where ${\mathsf{R}}_{i}$ represents the
largest number of transmissions in the $i^{\text{th}}$ transmission round
among all users normalized by ${\mathsf{L}}$ for $i\in\\{1,2\\}$. The capacity
region was proved to be
$\\{({\mathsf{R}}_{1},{\mathsf{R}}_{2}):{\mathsf{R}}_{1}\geq
1,{\mathsf{R}}_{2}\geq 1/{\mathsf{U}}\\}$ in [10] with an achievability
strategy based on Minimum Distance Separable (MDS) codes in the key generation
and one-time pad coding in the model aggregation. Another secure aggregation
scheme which can also achieve capacity was proposed in [18], based on a
pairwise coded key generation. Compared to [10], the scheme in [18]
significantly reduces the size of keys stored by each user.

There are some other extended information theoretic formulations on secure
aggregation in federated learning, following the model in [10]. A weaker
information theoretic security constraint compared to the one in [10] was
considered in [19], where we only need to preserve the security on a subset of
users’ input vectors. User collusion was also considered in [10], where the
server may collude with up to ${\mathsf{T}}<{\mathsf{U}}$ users; to deal with
potential user collusion, the capacity region reduces to
$\\{({\mathsf{R}}_{1},{\mathsf{R}}_{2}):{\mathsf{R}}_{1}\geq
1,{\mathsf{R}}_{2}\geq 1/({\mathsf{U}}-{\mathsf{T}})\\}$, characterized in
[10]. Information theoretic secure aggregation with cluster federated learning
was originally considered in [20], to aggregate the updated models from
multiple clusters of users simultaneously, without learning any information
about the cluster identities or users’ local data.

Recently a modified version of the above problem, referred to as
$({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information theoretic secure
aggregation with uncoded groupwise keys, was proposed in [21] as illusrated in
Fig. 1. An additional constraint on the keys was considered, where the key
sharing among the users is “uncoded” and “groupwise”. More precisely, given a
system parameter ${\mathsf{S}}$, the system generates
${{\mathsf{K}}\choose{\mathsf{S}}}$ mutually independent keys, such that each
key is shared exactly by one group of ${\mathsf{S}}$ distinct users and is
also independent of the input vectors.333In contrast, coded pairwise keys were
used in [18, 6] where the keys shared by the users are not mutually
independent. This constraint is motivated by the fact that in practical
cryptographic system, each key may be generated by some key agreement protocol
as in [22, 23, 24, 25, 26, 27, 28] among a set of nodes. An interesting
question arises for the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information
theoretic secure aggregation with uncoded groupwise keys: do the capacity
region remains the same as the secure aggregation problem in [10]? When
${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$, a secure aggregation scheme with
groupwise keys was proposed in [21] which achieves the same capacity region
$\\{({\mathsf{R}}_{1},{\mathsf{R}}_{2}):{\mathsf{R}}_{1}\geq
1,{\mathsf{R}}_{2}\geq 1/{\mathsf{U}}\\}$ as in [10]. Hence, in this case, the
key group sharing constraint does not involve any loss of optimality. When
${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$, a converse bound was proposed in
[21] showing that the capacity region in [10] is not achievable. However, the
capacity region for the case ${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$ still
remains open.

(a) First round.

(b) Second round.

Figure 1: $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})=(4,2,2)$ information
theoretic secure aggregation problem with uncoded groupwise keys.

###  I-C Main Contribution

The main contribution of this paper is to characterize the capacity region on
the rate tuples for the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information
theoretic secure aggregation with uncoded groupwise keys,
$\left\\{({\mathsf{R}}_{1},{\mathsf{R}}_{2}):{\mathsf{R}}_{1}\geq\frac{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}},{\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}\right\\}$.
More precisely, our focus is on the open case
${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$, and we develop the following
results.

  * •

We first derive a new converse bound on the rate of the first round
${\mathsf{R}}_{1}$, which is strictly tighter than the converse bound in [21].

  * •

We propose a new secure aggregation scheme based on the interference alignment
strategy, which achieves the converse bound. The main difference between the
proposed scheme and the secure aggregation scheme in [21] (which works for the
case ${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$) is that, when
${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$ the optimal rate in the first
round ${\mathsf{R}}_{1}$ is strictly larger than $1$, and in addition to the
masked input vector, each user should also transmit some additional messages
composed of the keys. Hence, when a whole group of users sharing the same key
drops in the second phase, the server can leverage these additional messages
transmitted in the first round to decrypt.

  * •

We implement the proposed secure aggregation scheme into the Tencent Cloud.
Experimental results show that the proposed secure aggregation scheme reduces
the model aggregation time by up to $67.2\%$ compared to the original secure
aggregation scheme in [6].

###  I-D Paper Organization

The rest of this paper is organized as follows. Section II reviews the
information theoretic secure aggregation problem with uncoded groupwise keys.
Section III introduces the main theorem of the paper, which characterizes the
capacity region. Sections IV and V present the converse and achievability
proofs of the main theorem, respectively. Section VII concludes the paper,
while some proofs are given in the Appendices.

###  I-E Notation Convention

Calligraphic symbols denote sets, bold symbols denote vectors and matrices,
and sans-serif symbols denote system parameters. We use $|\cdot|$ to represent
the cardinality of a set or the length of a vector;
$[a:b]:=\left\\{a,a+1,\ldots,b\right\\}$ and $[n]:=[1:n]$;
$\mathbb{F}_{{\mathsf{q}}}$ represents a finite field with order
${\mathsf{q}}$; ${\mathbf{e}}_{n,i}$ represents the vertical $n$-dimensional
unit vector whose entry in the $i^{\text{th}}$ position is $1$ and $0$
elsewhere; $\mathbf{A}^{\text{\rm T}}$ and $\mathbf{A}^{-1}$ represent the
transpose and the inverse of matrix $\mathbf{A}$, respectively;
$\text{rank}(\mathbf{A})$ represents the rank of matrix $\mathbf{A}$;
$\mathbf{I}_{n}$ represents the identity matrix of dimension $n\times n$;
${\bf 0}_{m,n}$ represents all-zero matrix of dimension $m\times n$; ${\bf
1}_{m,n}$ represents all-one matrix of dimension $m\times n$;
$(\mathbf{A})_{m\times n}$ explicitly indicates that the matrix $\mathbf{A}$
is of dimension $m\times n$; $<\cdot>_{a}$ represents the modulo operation
with integer quotient $a>0$ and in this paper we let
$<\cdot>_{a}\in\\{1,\ldots,a\\}$ (i.e., we let $<b>_{a}=a$ if $a$ divides
$b$); let $\binom{x}{y}=0$ if $x<0$ or $y<0$ or $x<y$; let
$\binom{{\mathcal{X}}}{y}=\\{{\mathcal{S}}\subseteq{\mathcal{X}}:|{\mathcal{S}}|=y\\}$
where $|{\mathcal{X}}|\geq y>0$. In this paper, for a set of real numbers
${\mathcal{S}}$, we sort the elements in ${\mathcal{S}}$ in an increasing
order and denote the $i^{\text{th}}$ smallest element by ${\mathcal{S}}(i)$,
i.e., ${\mathcal{S}}(1)<\ldots<{\mathcal{S}}(|{\mathcal{S}}|)$. In the rest of
the paper, entropies will be in base ${\mathsf{q}}$, where ${\mathsf{q}}$
represents the field size.

##  II System Model

We consider a $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information theoretic
secure aggregation problem with uncoded groupwise keys originally formulated
in [21], as illustrated in Fig 1. Note that
${\mathsf{K}},{\mathsf{U}},{\mathsf{S}}$ are given system parameters, where
${\mathsf{K}}$ represents the number of users in the system, ${\mathsf{U}}$
represents the minimum number of surviving users, and ${\mathsf{S}}$
represents the group-sharing parameter, i.e., the size of the groups uniquely
sharing the same key. Each user $k\in[{\mathsf{K}}]$ holds one input vector
$W_{k}$ containing ${\mathsf{L}}$ uniform and i.i.d. symbols on a finite field
$\mathbb{F}_{{\mathsf{q}}}$, where ${\mathsf{q}}$ is a prime power. In
addition, for each set ${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$,
the users in ${\mathcal{V}}$ share a common key $Z_{{\mathcal{V}}}$ with large
enough size. Considering that the key sharing is offline, the keys and the
input vectors are assumed to be mutually independent, i.e.,

$\displaystyle
H\left(\left(Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}\right),(W_{1},\ldots,W_{{\mathsf{K}}})\right)=\sum_{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}}H(Z_{{\mathcal{V}}})+\sum_{k\in[{\mathsf{K}}]}H(W_{k}).$
(1)

We define
$Z_{k}:=\left(Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},k\in{\mathcal{V}}\right),$
as the keys accessible by user $k\in[{\mathsf{K}}]$.

A server is connected with the users via dedicated error-free links.444In this
context, the nature of these links is irrelevant. Federated learning is a
distributed process running at the application layer, i.e., on top of some
possibly heterogeneous networks with possibly different lower protocol layers.
In any case, at the application layer, it is reasonable and practical to
assume that the server and the users establish end-to-end communication
sessions using TCP/IP. In fact, in most practical applications federated
learning runs over geographically widely separated users (imagine to run such
application on the local picture library of smartphones all over the world).
The server aims to aggregates the input vectors computed by the users. In this
paper, we consider the effect of user dropouts, i.e., the system is designed
to tolerate up to ${\mathsf{K}}-{\mathsf{U}}>0$ user dropouts; in this case,
it was proved in [10] that one transmission round in the model aggregation is
not enough. Thus we consider the two-round model aggregation as in [10, 21].

First round. In the first round, each user $k\in[{\mathsf{K}}]$ sends a coded
message $X_{k}$ to the server without knowing which user will drop in the
future, where $X_{k}$ is completely determined by $W_{k}$ and $Z_{k}$, i.e,

$\displaystyle H(X_{k}|W_{k},Z_{k})=0.$ (2)

The transmission rate of the first round ${\mathsf{R}}_{1}$ is defined as the
largest transmission load among all users normalized by ${\mathsf{L}}$, i.e.,

$\displaystyle{\mathsf{R}}_{1}:=\max_{k\in[{\mathsf{K}}]}\frac{H\left(X_{k}\right)}{{\mathsf{L}}}.$
(3)

Users may drop during the first round. We denote the set of surviving users
after the first round by ${\mathcal{U}}_{1}$. Since ${\mathsf{U}}$ represents
the minimum number of surviving users, we have
${\mathcal{U}}_{1}\subseteq[{\mathsf{K}}]$ and
$|{\mathcal{U}}_{1}|\geq{\mathsf{U}}$. Hence, the server receives
$(X_{k}:k\in{\mathcal{U}}_{1})$.

Second round. In the second round, the server first sends the list of the
surviving users ${\mathcal{U}}_{1}$ to the users in ${\mathcal{U}}_{1}$.
According to this information, each user $k\in{\mathcal{U}}_{1}$ sends another
coded message $Y^{{\mathcal{U}}_{1}}_{k}$ to the server, where

$\displaystyle H(Y^{{\mathcal{U}}_{1}}_{k}|W_{k},Z_{k},{\mathcal{U}}_{1})=0.$
(4)

The transmission rate of the second round ${\mathsf{R}}_{2}$ is defined as the
largest transmission load among all ${\mathcal{U}}_{1}$ and all users in
${\mathcal{U}}_{1}$ normalized by ${\mathsf{L}}$, i.e.,

$\displaystyle{\mathsf{R}}_{2}:=\max_{{\mathcal{U}}_{1}\subseteq[{\mathsf{K}}]:|{\mathcal{U}}_{1}|\geq{\mathsf{U}}}\
\max_{k\in{\mathcal{U}}_{1}}\frac{H\left(Y^{{\mathcal{U}}_{1}}_{k}\right)}{{\mathsf{L}}}.$
(5)

Users may also drop during the second round transmission, and the set of
surviving users after the second round is denoted as ${\mathcal{U}}_{2}$. By
definition, we have ${\mathcal{U}}_{2}\subseteq{\mathcal{U}}_{1}$ and
$|{\mathcal{U}}_{2}|\geq{\mathsf{U}}$. Thus the server receives
$Y^{{\mathcal{U}}_{1}}_{k}$ where $k\in{\mathcal{U}}_{2}$.

Decoding. From the two-round transmissions, the server totally receives
$(X_{k_{1}}:k_{1}\in{\mathcal{U}}_{1})$ and
$(Y^{{\mathcal{U}}_{1}}_{k_{2}}:k_{2}\in{\mathcal{U}}_{2})$, from which the
server should recover the sum of input vectors by the first round surviving
users, i.e., $\sum_{k\in{\mathcal{U}}_{1}}W_{k}$. Thus

$\displaystyle
H\left(\sum_{k\in{\mathcal{U}}_{1}}W_{k}\Big{|}(X_{k_{1}}:k_{1}\in{\mathcal{U}}_{1}),(Y^{{\mathcal{U}}_{1}}_{k_{2}}:k_{2}\in{\mathcal{U}}_{2})\right)=0,\
\forall{\mathcal{U}}_{1}\subseteq[{\mathsf{K}}],{\mathcal{U}}_{2}\subseteq{\mathcal{U}}_{1}:|{\mathcal{U}}_{1}|\geq|{\mathcal{U}}_{2}|\geq{\mathsf{U}}.$
(6)

Security. For the security constraint, we consider the worst-case, where the
users are not really dropped but too slow in the transmission and thus the
server may receive all the possible transmissions by the users. More
precisely, it may receive $(X_{k_{1}}:k_{1}\in[{\mathsf{K}}])$ from the first
round and $(Y^{{\mathcal{U}}_{1}}_{k_{2}}:k_{2}\in{\mathcal{U}}_{1})$ from the
second transmission. By security, from the received messages, the server can
only obtain the computation task without retrieving other information about
the input vectors, i.e.,

$\displaystyle
I\left(W_{1},\ldots,W_{{\mathsf{K}}};X_{1},\ldots,X_{{\mathsf{K}}},(Y^{{\mathcal{U}}_{1}}_{k}:k\in{\mathcal{U}}_{1})\Big{|}\sum_{k\in{\mathcal{U}}_{1}}W_{k}\right)=0,\
\forall{\mathcal{U}}_{1}\subseteq[{\mathsf{K}}]:|{\mathcal{U}}_{1}|\geq{\mathsf{U}}.$
(7)

It is worth noticing that this mutual information is strictly equal to $0$;
that is, we consider zero leakage, instead of vanishing leakage as
${\mathsf{L}}\to\infty$.

Objective. A rate tuple $({\mathsf{R}}_{1},{\mathsf{R}}_{2})$ is achievable if
there exist keys
$\left(Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}\right)$
satisfying (1) and a secure aggregation scheme satisfying the decodability and
security constraints in (6) and (7), respectively. Our objective is to
determine the capacity region (i.e., the closure of all achievable rate
tuples), denoted by ${\mathcal{R}}^{\star}$.

Existing converse bounds. By removing the uncoded groupwise constraint on the
keys in our problem, we obtain the information theoretic aggregation problem
in [10]. Hence, the converse bound on the capacity region in [10] is also a
converse bound for our problem.

######  Theorem 1 ([10]).

For the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information theoretic
secure aggregation problem with uncoded groupwise keys, any achievable rate
tuple $({\mathsf{R}}_{1},{\mathsf{R}}_{2})$ satisfies

$\displaystyle{\mathsf{R}}_{1}\geq 1,\
{\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}.$ (8)

$\square$

Considering the uncoded groupwise constraint, an improved converse bound was
given in [21] for the case ${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$.

######  Theorem 2 ([21]).

For the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information theoretic
secure aggregation problem with uncoded groupwise keys, when
$1={\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$, secure aggregation is not
possible; when $2\leq{\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$, any
achievable rate tuple $({\mathsf{R}}_{1},{\mathsf{R}}_{2})$ satisfies

$\displaystyle{\mathsf{R}}_{1}\geq
1+\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-1},{\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}.$
(9)

$\square$

Existing achievable bound. A secure aggregation scheme with uncoded groupwise
keys was proposed in [21] for the case
${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$, achieving the following rates.

######  Theorem 3 ([21]).

For the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information theoretic
secure aggregation problem with uncoded groupwise keys, when
${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$, the following rate tuples are
achievable,

$\displaystyle{\mathsf{R}}_{1}\geq
1,{\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}.$ (10)

$\square$

Comparing the achievable bound in Theorem 3 and the converse bound in Theorem
1, we can characterize the capacity region for the case
${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$, which is

$\displaystyle{\mathcal{R}}^{\star}=\left\\{({\mathsf{R}}_{1},{\mathsf{R}}_{2}):{\mathsf{R}}_{1}\geq
1,{\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}\right\\}.$ (11)

However, no achievable scheme has been provided for the case
${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$, and the capacity region for this
case remained open until this paper.

##  III Main Result

The main contribution of this paper is to fully characterize the capacity
region for the information theoretic secure aggregation problem with uncoded
groupwise keys. This is stated in the following theorem.

######  Theorem 4.

For the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$ information theoretic
secure aggregation problem with uncoded groupwise keys, when ${\mathsf{S}}=1$,
secure aggregation is not possible; when ${\mathsf{S}}\geq 2$, we have

$\displaystyle{\mathcal{R}}^{\star}=\left\\{({\mathsf{R}}_{1},{\mathsf{R}}_{2}):{\mathsf{R}}_{1}\geq\frac{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}},{\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}\right\\}.$
(12)

$\square$

The converse proof of Theorem 4 is given in Section IV and the achievability
proof is given in Section V. The following remarks on Theorem 4 are in order:

  * •

When ${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$, we have
$\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=0$ and thus the capacity
region in (12) reduces to the one in (11), which is also equal to the capacity
region for the information theoretic secure aggregation problem in [10] (the
one without the constraint on the uncoded groupwise keys). When
$2\leq{\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$, the additional communication
rate from the optimal secure aggregation scheme with uncoded groupwise keys
compared to the generally optimal secure aggregation scheme in [10] is only at
the first round and is equal to
$\frac{\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}.$

  * •

The converse bound to prove (12) is strictly tighter than the existing one in
(9).

  * •

The secure aggregation scheme proposed in Section V is a new and unified
scheme working for all system parameters when ${\mathsf{S}}>1$. In constrast,
in [21] only the regime ${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$ was
considered, where this regime was first divided into three cases and a
different secure aggregation scheme was proposed for each case.

  * •

The scheme in Section V uses all the $\binom{{\mathsf{K}}}{{\mathsf{S}}}$ keys
in the system , where each key contains
$\frac{{\mathsf{S}}{\mathsf{L}}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}$
symbols. In comparison, the secure aggregation in [21] uses at most
${\mathcal{O}}({\mathsf{K}}^{2})$ keys, where each key has
$\frac{({\mathsf{K}}-{\mathsf{U}}+1){\mathsf{L}}}{{\mathsf{U}}}$ symbols.

##  IV Converse Proof of Theorem 4

Since the converse bound for the information theoretic aggregation problem in
[10] is also a converse bound for our considered problem, by Theorem 1 we can
directly obtain ${\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}$. Hence, for
Theorem 4 we only need to prove

$\displaystyle{\mathsf{R}}_{1}\geq\frac{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}},$
(13)

for the case ${\mathsf{S}}\geq 2$.

Let us focus on user $1$ and derive the lower bound of
$\frac{H(X_{1})}{{\mathsf{L}}}$. For each set
${\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}$, letting
${\mathcal{U}}_{1}=\\{1\\}\cup{\mathcal{U}}$ and
${\mathcal{U}}_{2}={\mathcal{U}}$, by the decodability constraint (6) the
server can recover $\sum_{i\in\\{1\\}\cup{\mathcal{U}}}W_{i}$ from
$\left(X_{k}:k\in\\{1\\}\cup{\mathcal{U}}\right)$ and
$\left(Y^{{\mathcal{U}}_{1}}_{k}:k\in{\mathcal{U}}\right)$. In addition, for
each $k\in{\mathcal{U}}$, $\left(X_{k},Y^{{\mathcal{U}}_{1}}_{k}\right)$ is a
function of $(Z_{k},W_{k})$. Hence, the server can recover
$\sum_{i\in\\{1\\}\cup{\mathcal{U}}}W_{i}$ from
$(X_{1},(Z_{k},W_{k}:k\in{\mathcal{U}}))$; thus

$\displaystyle
0=H\left(\sum_{i\in\\{1\\}\cup{\mathcal{U}}}W_{i}\Bigg{|}X_{1},(Z_{k},W_{k}:k\in{\mathcal{U}})\right)$
(14a)
$\displaystyle=H\left(W_{1}|X_{1},(Z_{k},W_{k}:k\in{\mathcal{U}})\right)$
(14b)
$\displaystyle=H\left(W_{1}\Big{|}X_{1},\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right)$
(14c)
$\displaystyle=H\left(W_{1}\Big{|}\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right)-I\left(X_{1};W_{1}\Big{|}\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right),$
(14d)

where (14c) comes from (1) and (2). In addition, from (14d) we have

$\displaystyle
I\left(X_{1};W_{1}\Big{|}\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right)$
$\displaystyle=H\left(W_{1}\Big{|}\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right)$
(15a) $\displaystyle=H(W_{1})={\mathsf{L}},$ (15b)

where (15b) follows since $W_{1}$ is independent of the keys. In addition, we
have

$\displaystyle
I\left(X_{1};\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\Big{|}W_{1}\right)$
$\displaystyle=I\left(X_{1};W_{1},\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right)-I(X_{1};W_{1})$
(16a)
$\displaystyle=I\left(X_{1};W_{1},\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right)$
(16b) $\displaystyle\geq
I\left(X_{1};W_{1}\Big{|}\Big{(}Z_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}},{\mathcal{U}}\cap{\mathcal{V}}\neq\emptyset\Big{)}\right)$
(16c) $\displaystyle={\mathsf{L}},$ (16d)

where (16b) comes from the security constraint (7) and (16d) comes from (15b).

We sort the sets ${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ where
$1\in{\mathcal{V}}$ in the lexicographic order, denoted by
${\mathcal{S}}_{1,1},\ldots,{\mathcal{S}}_{1,\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}$.
Then by the chain rule of mutual information, we have

$\displaystyle{\mathsf{R}}_{1}{\mathsf{L}}\geq H(X_{1})$ (17a)
$\displaystyle\geq
I\left(X_{1};Z_{{\mathcal{S}}_{1,1}},\ldots,Z_{{\mathcal{S}}_{1,\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}}|W_{1}\right)$
(17b)
$\displaystyle=\sum_{i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]}I(X_{1};Z_{{\mathcal{S}}_{1,i}}|W_{1},Z_{{\mathcal{S}}_{1,1}},\ldots,Z_{{\mathcal{S}}_{1,i-1}})$
(17c)
$\displaystyle=\left(\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}\right)\sum_{i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]}\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}I(X_{1};Z_{{\mathcal{S}}_{1,i}}|W_{1},Z_{{\mathcal{S}}_{1,1}},\ldots,Z_{{\mathcal{S}}_{1,i-1}})$
(17d)
$\displaystyle=\sum_{{\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}}\
\sum_{i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]:{\mathcal{U}}\cap{\mathcal{S}}_{1,i}\neq\emptyset}\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}I(X_{1};Z_{{\mathcal{S}}_{1,i}}|W_{1},Z_{{\mathcal{S}}_{1,1}},\ldots,Z_{{\mathcal{S}}_{1,i-1}}),$
(17e)

where (17e) follows since for each
$i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]$, there are exactly
$\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}$
sets in $\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}$, each of which intersects
${\mathcal{S}}_{1,i}$.

From (17e), we have

$\displaystyle{\mathsf{R}}_{1}{\mathsf{L}}\geq\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}\sum_{{\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}}\
\sum_{i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]:{\mathcal{U}}\cap{\mathcal{S}}_{1,i}\neq\emptyset}I(X_{1};Z_{{\mathcal{S}}_{1,i}}|W_{1},Z_{{\mathcal{S}}_{1,1}},\ldots,Z_{{\mathcal{S}}_{1,i-1}})$
(18a)
$\displaystyle=\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}\sum_{{\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}}\
\sum_{i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]:{\mathcal{U}}\cap{\mathcal{S}}_{1}(i)\neq\emptyset}$
$\displaystyle\Big{(}I(X_{1},(Z_{{\mathcal{S}}_{1,j}}:j\in[i-1],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}=\emptyset);Z_{{\mathcal{S}}_{1,i}}|W_{1},(Z_{{\mathcal{S}}_{1,j}}:j\in[i-1],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}\neq\emptyset))$
$\displaystyle-I((Z_{{\mathcal{S}}_{1,j}}:j\in[i-1],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}=\emptyset);Z_{{\mathcal{S}}_{1,i}}|W_{1},(Z_{{\mathcal{S}}_{1,j}}:j\in[i-1],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}\neq\emptyset))\Big{)}$
(18b)
$\displaystyle=\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}\sum_{{\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}}\
\sum_{i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]:{\mathcal{U}}\cap{\mathcal{S}}_{1,i}\neq\emptyset}$
$\displaystyle
I(X_{1},(Z_{{\mathcal{S}}_{1,j}}:j\in[i-1],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}=\emptyset);Z_{{\mathcal{S}}_{1,i}}|W_{1},(Z_{{\mathcal{S}}_{1,j}}:j\in[i-1],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}\neq\emptyset))$
(18c)
$\displaystyle\geq\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}\sum_{{\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}}\
\sum_{i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]:{\mathcal{U}}\cap{\mathcal{S}}_{1,i}\neq\emptyset}I(X_{1};Z_{{\mathcal{S}}_{1,i}}|W_{1},(Z_{{\mathcal{S}}_{1,j}}:j\in[i-1],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}\neq\emptyset))$
(18d)
$\displaystyle=\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}\sum_{{\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}}I\left(X_{1};\Big{(}Z_{{\mathcal{S}}_{1,j}}:j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right],{\mathcal{U}}\cap{\mathcal{S}}_{1,j}\neq\emptyset\Big{)}\Big{|}W_{1}\right)$
(18e)
$\displaystyle\geq\frac{1}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}\sum_{{\mathcal{U}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{U}}}}{\mathsf{L}}$
(18f)
$\displaystyle=\frac{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}{\mathsf{L}},$
(18g)

where (18c) follows since the uncoded keys and input vectors are independent,
(18e) comes from the chain rule of mutual information, and (18f) comes from
(16d).

Thus we have

$\displaystyle{\mathsf{R}}_{1}$
$\displaystyle\geq\frac{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}}{\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}}$
(19a)
$\displaystyle=\frac{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}},$
(19b)

where (19b) follows since

$\displaystyle\binom{{\mathsf{K}}-1}{{\mathsf{U}}}\binom{({\mathsf{K}}-1)-{\mathsf{U}}}{{\mathsf{S}}-1}=\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\binom{({\mathsf{K}}-1)-({\mathsf{S}}-1)}{{\mathsf{U}}}=\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$
(20a)
$\displaystyle\Longleftrightarrow\binom{{\mathsf{K}}-1}{{\mathsf{U}}}\left(\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right)=\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\left(\binom{{\mathsf{K}}-1}{{\mathsf{U}}}-\binom{{\mathsf{K}}-{\mathsf{S}}}{{\mathsf{U}}}\right).$
(20b)

Hence, we proved (13) and thus the converse bound of Theorem (4).

##  V Achievability Proof of Theorem 4

In this section, we describe the proposed secure aggregation scheme achieving
the rate region in Theorem 4. We first illustrate the main ideas of the
proposed scheme through the following example.

######  Example 1 ($({\mathsf{K}},{\mathsf{U}},{\mathsf{S}}))=(5,2,3)$).

We consider the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})=(5,2,3)$ information
theoretic secure aggregation problem with uncoded groupwise keys. Note that in
this example, for the ease of illustration, we assume that the field size
${\mathsf{q}}$ is a large enough prime; it will be proved later that our
proposed scheme works for arbitrary field size.

By the converse bound derived in Section IV, we have
${\mathsf{R}}_{1}\geq\frac{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}=\frac{6}{5}$
and ${\mathsf{R}}_{2}\geq\frac{1}{{\mathsf{U}}}=\frac{1}{2}$. Inspired by the
converse bound, we divide each input vector $W_{i}$ where $i\in[{\mathsf{K}}]$
into
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=5$
non-overlapping and equal-length pieces, $W_{i}=\\{W_{i,1},\ldots,W_{i,5}\\}$.
For each set ${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$, we
generate a key $Z_{{\mathcal{V}}}$ containing
$\frac{{\mathsf{S}}{\mathsf{L}}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}=\frac{3{\mathsf{L}}}{5}$
symbols uniformly i.i.d. over $\mathbb{F}_{{\mathsf{q}}}$; let
$Z_{{\mathcal{V}}}$ be shared by the users in ${\mathcal{V}}$. In addition, we
further divide each key $Z_{{\mathcal{V}}}$ into ${\mathsf{S}}=3$ sub-keys,
$Z_{{\mathcal{V}}}=\\{Z_{{\mathcal{V}},k}:k\in{\mathcal{V}}\\}$, where each
sub-key $Z_{{\mathcal{V}},k}$ has $\frac{{\mathsf{L}}}{5}$ symbols.

From the converse bound we see that in the first round each user $k\in[5]$
should send more than ${\mathsf{L}}$ symbols, while input vector $W_{k}$
contains ${\mathsf{L}}$ symbols. Thus, unlike the secure aggregation scheme in
[21] which has ${\mathsf{R}}_{1}=1$, in the first round besides the encrypted
input vector, we also need to transmit some coded messages composed of keys,
to cope with the fact that some keys cannot be transmitted in the second round
due to user dropouts. For each key ${\mathcal{Z}}_{{\mathcal{V}}}$, we select
a $6$-length vector
${\mathbf{a}}_{{\mathcal{V}}}=[a_{{\mathcal{V}},1},\ldots,a_{{\mathcal{V}},6}]^{\text{\rm
T}}$ which will serve as the coefficient vector of its sub-keys during the
first round. The selection of these coefficient vectors to guarantee the
encodability, decodability and security, is the most important step in the
proposed secure aggregation scheme. We denote the sets
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ where
$k\in{\mathcal{V}}$ by
${\mathcal{S}}_{k,1},\ldots,{\mathcal{S}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}$;
denote the sets in $\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$ by
$\overline{{\mathcal{S}}}_{k,1},\ldots,\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}$.
For the security and encodability, it will be explained later that the
selection has the following two properties respectively:

$\displaystyle\left[{\mathbf{a}}_{{\mathcal{S}}_{k,1}},\ldots,{\mathbf{a}}_{{\mathcal{S}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}}\right]\
\text{ has rank equal to }\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}=6,\ \forall
k\in[{\mathsf{K}}];$ (21)
$\displaystyle\left[{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,1}},\ldots,{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}}\right]\
\text{ has rank equal to }\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}=3,\ \forall
k\in[{\mathsf{K}}].$ (22)

In order to guarantee (21) and (22), we select the coefficient vectors by the
following two steps:

  * •

We first select each vector ${\mathbf{a}}_{{\mathcal{V}}}$ for each
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ where
$1\in{\mathcal{V}}$. More precisely, we choose each element in
${\mathbf{a}}_{{\mathcal{V}}}$ uniformly i.i.d. over
$\mathbb{F}_{{\mathsf{q}}}$. In this example, we let

$\displaystyle{\mathbf{a}}_{\\{1,2,3\\}}=[0,1,0,0,1,1]^{\text{\rm T}},\
{\mathbf{a}}_{\\{1,2,4\\}}=[1,0,1,1,1,1]^{\text{\rm T}},\
{\mathbf{a}}_{\\{1,2,5\\}}=[0,0,0,1,0,1]^{\text{\rm T}},$
$\displaystyle{\mathbf{a}}_{\\{1,3,4\\}}=[0,1,1,1,0,1]^{\text{\rm T}},\
{\mathbf{a}}_{\\{1,3,5\\}}=[1,1,0,1,0,1]^{\text{\rm T}},\
{\mathbf{a}}_{\\{1,4,5\\}}=[1,0,0,0,0,1]^{\text{\rm T}}.$

  * •

Then we fix each of the remaining vectors by a linear combination of the
selected vectors in the first step. More precisely, to fix
${\mathbf{a}}_{\\{2,3,4\\}}$, we let ${\mathbf{a}}_{\\{2,3,4\\}}$ be a linear
combination of ${\mathbf{a}}_{\\{1,3,4\\}}$, ${\mathbf{a}}_{\\{1,2,4\\}}$, and
${\mathbf{a}}_{\\{1,2,3\\}}$, where the coefficients are either $+1$ or $-1$
and alternated,

$\displaystyle{\mathbf{a}}_{\\{2,3,4\\}}={\mathbf{a}}_{\\{1,3,4\\}}-{\mathbf{a}}_{\\{1,2,4\\}}+{\mathbf{a}}_{\\{1,2,3\\}}.$
(23)

Similarly, for each ${\mathcal{V}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{S}}}$,
we let ${\mathbf{a}}_{{\mathcal{V}}}$ be the following linear combination of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{k\\}\cup\\{1\\}}$ where
$k\in{\mathcal{V}}$, (recall that ${\mathcal{V}}(i)$ represents the
$i^{\text{th}}$ smallest element in ${\mathcal{V}}$)

$\displaystyle{\mathbf{a}}_{{\mathcal{V}}}=\sum_{i\in[3]}(-1)^{i-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}.$
(24)

The detailed section on the coefficient vectors is given in Table I. It can be
checked that this selection has the two properties in (21) and (22). The first
property could be directly checked. For the second property, we have

$\displaystyle{\mathbf{a}}_{\\{3,4,5\\}}={\mathbf{a}}_{\\{2,4,5\\}}-{\mathbf{a}}_{\\{2,3,5\\}}+{\mathbf{a}}_{\\{2,3,4\\}};$
(25)

thus the rank of
$[{\mathbf{a}}_{\\{2,3,4\\}},{\mathbf{a}}_{\\{2,3,5\\}},{\mathbf{a}}_{\\{2,4,5\\}},{\mathbf{a}}_{\\{3,4,5\\}}]$
is equal to the rank of
$[{\mathbf{a}}_{\\{2,3,4\\}},{\mathbf{a}}_{\\{2,3,5\\}},{\mathbf{a}}_{\\{2,4,5\\}}]$
which is equal to $3$. In addition, since

$\displaystyle{\mathbf{a}}_{\\{3,4,5\\}}={\mathbf{a}}_{\\{1,4,5\\}}-{\mathbf{a}}_{\\{1,3,5\\}}+{\mathbf{a}}_{\\{1,3,4\\}};$
(26)

thus the rank of
$[{\mathbf{a}}_{\\{1,3,4\\}},{\mathbf{a}}_{\\{1,3,5\\}},{\mathbf{a}}_{\\{1,4,5\\}},{\mathbf{a}}_{\\{3,4,5\\}}]$
is equal to the rank of
$[{\mathbf{a}}_{\\{1,3,4\\}},{\mathbf{a}}_{\\{1,3,5\\}},{\mathbf{a}}_{\\{1,4,5\\}}]$
which is equal to $3$. Similarly, we can also check that the rank of
$[{\mathbf{a}}_{\\{1,2,4\\}},{\mathbf{a}}_{\\{1,2,5\\}},{\mathbf{a}}_{\\{1,4,5\\}},{\mathbf{a}}_{\\{2,4,5\\}}]$
is equal to the rank of
$[{\mathbf{a}}_{\\{1,2,4\\}},{\mathbf{a}}_{\\{1,2,5\\}},{\mathbf{a}}_{\\{1,4,5\\}}]$
which is equal to $3$; the rank of
$[{\mathbf{a}}_{\\{1,2,3\\}},{\mathbf{a}}_{\\{1,2,5\\}},{\mathbf{a}}_{\\{1,3,5\\}},{\mathbf{a}}_{\\{2,3,5\\}}]$
is equal to the rank of
$[{\mathbf{a}}_{\\{1,2,3\\}},{\mathbf{a}}_{\\{1,2,5\\}},{\mathbf{a}}_{\\{1,3,5\\}}]$
which is equal to $3$; the rank of
$[{\mathbf{a}}_{\\{1,2,3\\}},{\mathbf{a}}_{\\{1,2,4\\}},{\mathbf{a}}_{\\{1,3,4\\}},{\mathbf{a}}_{\\{2,3,4\\}}]$
is equal to the rank of
$[{\mathbf{a}}_{\\{1,2,3\\}},{\mathbf{a}}_{\\{1,2,4\\}},{\mathbf{a}}_{\\{1,3,4\\}}]$
which is equal to $3$. Thus the property is satisfied. We will show later that
this selection guarantees the encodability, decodability and security.

TABLE I: Choice of $6$-dimensional vectors ${\mathbf{a}}_{{\mathcal{V}}}$ in the $({\mathsf{K}},{\mathsf{U}},{\mathsf{S}}))=(5,2,3)$ information theoretic secure aggregation problem.  ${\mathbf{a}}_{{\mathcal{V}}}$ | Value | ${\mathbf{a}}_{{\mathcal{V}}}$ | Value
---|---|---|---
${\mathbf{a}}_{\\{1,2,3\\}}$ | $[0,1,0,0,1,1]^{\text{\rm T}}$ | ${\mathbf{a}}_{\\{1,4,5\\}}$ | $[1,0,0,0,0,1]^{\text{\rm T}}$
${\mathbf{a}}_{\\{1,2,4\\}}$ | $[1,0,1,1,1,1]^{\text{\rm T}}$ | ${\mathbf{a}}_{\\{2,3,4\\}}$ | ${\mathbf{a}}_{\\{1,3,4\\}}-{\mathbf{a}}_{\\{1,2,4\\}}+{\mathbf{a}}_{\\{1,2,3\\}}=[-1,2,0,0,0,1]^{\text{\rm T}}$
${\mathbf{a}}_{\\{1,2,5\\}}$ | $[0,0,0,1,0,1]^{\text{\rm T}}$ | ${\mathbf{a}}_{\\{2,3,5\\}}$ | ${\mathbf{a}}_{\\{1,3,5\\}}-{\mathbf{a}}_{\\{1,2,5\\}}+{\mathbf{a}}_{\\{1,2,3\\}}=[1,2,0,0,1,1]^{\text{\rm T}}$
${\mathbf{a}}_{\\{1,3,4\\}}$ | $[0,1,1,1,0,1]^{\text{\rm T}}$ | ${\mathbf{a}}_{\\{2,4,5\\}}$ | ${\mathbf{a}}_{\\{1,4,5\\}}-{\mathbf{a}}_{\\{1,2,5\\}}+{\mathbf{a}}_{\\{1,2,4\\}}=[2,0,1,0,1,1]^{\text{\rm T}}$
${\mathbf{a}}_{\\{1,3,5\\}}$ | $[1,1,0,1,0,1]^{\text{\rm T}}$ | ${\mathbf{a}}_{\\{3,4,5\\}}$ | ${\mathbf{a}}_{\\{1,4,5\\}}-{\mathbf{a}}_{\\{1,3,5\\}}+{\mathbf{a}}_{\\{1,3,4\\}}=[0,0,1,0,0,1]^{\text{\rm T}}$

After the selection of the above coefficient vectors, the transmission in the
first round by each user $k\in[{\mathsf{K}}]$ can be divided into two parts
(as explained before):

  * •

The first part contains
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=5$
linear combinations of pieces and sub-keys, where each linear combination
contains ${\mathsf{L}}/5$ symbols. For each $j\in[5]$, let user $k$ transmit

$\displaystyle
X_{k,j}=W_{k,j}+\sum_{{\mathcal{V}}\in\binom{[5]}{3}:k\in{\mathcal{V}}}a_{{\mathcal{V}},j}Z_{{\mathcal{V}},k}.$
(27)

  * •

The second part contains
$\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=1$ linear combination of
sub-keys with ${\mathsf{L}}/5$ symbols; let user $k$ transmit

$\displaystyle
X_{k,6}=\sum_{{\mathcal{V}}\in\binom{[5]}{3}:k\in{\mathcal{V}}}a_{{\mathcal{V}},6}Z_{{\mathcal{V}},k}.$
(28)

Hence, user $k$ transmits $X_{k}=(X_{k,1},\ldots,X_{k,6})$, totally
$6{\mathsf{L}}/5$ symbols in the first round. Since the selection of the
coefficient vectors has the property in (21), the rank of the sub-keys in
$X_{k}$ is equal to the dimension of $X_{k}$ and thus from $X_{k}$ the server
cannot get any information about $W_{k}$ (see [21, Appendix C] for the formal
proof).

Now we consider the case ${\mathcal{U}}_{1}=[5]$, i.e., no user drops in the
first round. From the first round, the server can recover

$\displaystyle\sum_{k_{1}\in[5]}X_{k_{1},j}=\sum_{k_{2}\in[5]}W_{k_{2},j}+\sum_{{\mathcal{V}}\in\binom{[5]}{3}}a_{{\mathcal{V}},j}\underbrace{\sum_{k_{3}\in{\mathcal{V}}}Z_{{\mathcal{V}},k_{3}}}_{:=Z_{{\mathcal{V}}}^{[5]}}$
(29)

for each $j\in[5]$, and recover

$\displaystyle\sum_{k_{1}\in[5]}X_{k_{1},6}=\sum_{{\mathcal{V}}\in\binom{[5]}{3}}a_{{\mathcal{V}},6}Z_{{\mathcal{V}}}^{[5]}.$
(30)

Hence, the server should further recover the second term on the RHS of (29),
$\sum_{{\mathcal{V}}\in\binom{[5]}{3}}a_{{\mathcal{V}},j}Z_{{\mathcal{V}}}^{[5]}$
for $j\in[5]$, in the second round.

In the second round, to achieve ${\mathsf{R}}_{2}=1/2$, we divide each
$Z_{{\mathcal{V}}}^{[5]}$ where ${\mathcal{V}}\in\binom{[5]}{3}$ into $2$ non-
overlapping and equal-length coded keys,
$Z_{{\mathcal{V}}}^{[5]}=\left\\{Z_{{\mathcal{V}},1}^{[5]},Z_{{\mathcal{V}},2}^{[5]}\right\\}$,
where each coded key contains $\frac{{\mathsf{L}}}{10}$ symbols. Hence, we can
write the recovery task of the second round in the matrix form

$\displaystyle\left[\begin{array}[]{c}F_{1}\\\ \vdots\\\
F_{12}\end{array}\right]={\bf
F}\left[\begin{array}[]{c}Z_{\\{1,2,3\\},1}^{[5]}\\\
Z_{\\{1,2,4\\},1}^{[5]}\\\ \vdots\\\ Z_{\\{3,4,5\\},1}^{[5]}\\\
Z_{\\{1,2,3\\},2}^{[5]}\\\ Z_{\\{1,2,4\\},2}^{[5]}\\\ \vdots\\\
Z_{\\{3,4,5\\},2}^{[5]}\end{array}\right]$ (42)

where (recall that ${\bf 0}_{m\times n}$ represents the zero matrix with
dimension $m\times n$)

$\displaystyle{\bf
F}=\left[\begin{array}[]{c:c}{\mathbf{a}}_{\\{1,2,3\\}},{\mathbf{a}}_{\\{1,2,4\\}},\ldots,{\mathbf{a}}_{\\{3,4,5\\}}&{\bf
0}_{6\times 10}\\\ \hdashline{\bf 0}_{6\times
10}&{\mathbf{a}}_{\\{1,2,3\\}},{\mathbf{a}}_{\\{1,2,4\\}},\ldots,{\mathbf{a}}_{\\{3,4,5\\}}\\\
\end{array}\right]$ (45)

Note that
$F_{6}=\sum_{{\mathcal{V}}\in\binom{[5]}{3}}a_{{\mathcal{V}},6}Z_{{\mathcal{V}},1}^{[5]}$
and
$F_{12}=\sum_{{\mathcal{V}}\in\binom{[5]}{3}}a_{{\mathcal{V}},6}Z_{{\mathcal{V}},2}^{[5]}$
have been already recovered by the server from the first round.

We focus on each user $k\in[5]$, who should transmit
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=5$
linear combinations of $F_{1},\ldots,F_{12}$ in the second round; in the
matrix form these $5$ linear combinations are

$\displaystyle{\bf S}_{k}\left[\begin{array}[]{c}F_{1}\\\ \vdots\\\
F_{12}\end{array}\right],$ (49)

where ${\bf S}_{k}$ is a matrix with dimension $5\times 12$. Note that for the
encodability, user $k$ can only compute the coded keys
$Z_{{\mathcal{V}},j}^{[5]}$ where $k\in{\mathcal{V}}$; thus in the transmitted
linear combinations the coefficients of the coded keys which user $k$ cannot
compute should be equal to $0$.

For user $1$, the columns of ${\bf S}_{1}{\bf F}$ with indices in
$[7:10]\cup[17:20]$ should be ${\bf 0}_{5\times 1}$, since these columns
correspond to

$Z_{\\{2,3,4\\},1},Z_{\\{2,3,5\\},1},Z_{\\{2,4,5\\},1},Z_{\\{3,4,5\\},1},Z_{\\{2,3,4\\},2},Z_{\\{2,3,5\\},2},Z_{\\{2,4,5\\},2},Z_{\\{3,4,5\\},2},$

which cannot be computed by user $1$. Assume that the column-wise sub-matrix
of ${\bf F}$ including the columns with indices in $[7:10]\cup[17:20]$ is
${\bf F}_{1}$ with dimension $12\times 8$, where

$\displaystyle{\bf
F}_{1}=\left[\begin{array}[]{c:c}{\mathbf{a}}_{\\{2,3,4\\}},{\mathbf{a}}_{\\{2,3,5\\}},{\mathbf{a}}_{\\{2,4,5\\}},{\mathbf{a}}_{\\{3,4,5\\}}&{\bf
0}_{6\times 4}\\\ \hdashline{\bf 0}_{6\times
4}&{\mathbf{a}}_{\\{2,3,4\\}},{\mathbf{a}}_{\\{2,3,5\\}},{\mathbf{a}}_{\\{2,4,5\\}},{\mathbf{a}}_{\\{3,4,5\\}}\\\
\end{array}\right].$ (52)

We need to find $5$ linearly independent left null vectors of ${\bf F}_{1}$,
and let ${\bf S}_{1}$ be the matrix of these $5$ vectors. Note that if ${\bf
F}_{1}$ is full rank, the left null space of ${\bf F}_{1}$ only contains
$12-8=4$ linearly independent vectors. However, by our construction, it has
been shown in (25) that
${\mathbf{a}}_{\\{3,4,5\\}}={\mathbf{a}}_{\\{2,4,5\\}}-{\mathbf{a}}_{\\{2,3,5\\}}+{\mathbf{a}}_{\\{2,3,4\\}}$;
in other words, the coefficient vectors corresponding to the unknown coded
keys of user $1$ are aligned. Thus by this interference alignment-like
construction leading to (22), the rank of ${\bf F}_{1}$ is $6$, and thus the
left null space of ${\bf F}_{1}$ contains $12-6=6$ linearly independent
vectors. More precisely, the left null space of
$[{\mathbf{a}}_{\\{2,3,4\\}},{\mathbf{a}}_{\\{2,3,5\\}},{\mathbf{a}}_{\\{2,4,5\\}}]$
is the linear space spanned by

${\mathbf{s}}_{1,1}=(0,-1,-2,0,0,2),\ {\mathbf{s}}_{1,2}=(-2,-1,0,0,4,0),\
{\mathbf{s}}_{1,3}=(0,0,0,1,0,0).$

Hence, the left null space of ${\bf F}_{1}$ is the linear space spanned by

$\displaystyle({\mathbf{s}}_{1,1},{\bf 0}_{1\times 6}),\
({\mathbf{s}}_{1,2},{\bf 0}_{1\times 6}),\ ({\mathbf{s}}_{1,3},{\bf
0}_{1\times 6}),\ ({\bf 0}_{1\times 6},{\mathbf{s}}_{1,1}),\ ({\bf 0}_{1\times
6},{\mathbf{s}}_{1,2}),\ ({\bf 0}_{1\times 6},{\mathbf{s}}_{1,3}).$ (53)

We let each row of ${\bf S}_{1}$ be one random linear combination of the
vectors in (53); in this example, we let

$\displaystyle{\bf
S}_{1}=\left[\begin{array}[]{cccccccccccc}0&-1&-2&0&0&2&0&0&0&0&0&0\\\
-2&-1&0&0&4&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&-1&-2&0&0&2\\\
0&0&0&0&0&0&-2&-1&0&0&4&0\\\ 0&0&0&1&0&0&0&0&0&1&0&0\end{array}\right].$ (59)

For user $2$, the columns of ${\bf S}_{2}{\bf F}$ with indices in
$\\{4,5,6,10,14,15,16,20\\}$ should be ${\bf 0}_{5\times 1}$, since these
columns correspond to

$Z_{\\{1,3,4\\},1},Z_{\\{1,3,5\\},1},Z_{\\{1,4,5\\},1},Z_{\\{3,4,5\\},1},Z_{\\{1,3,4\\},2},Z_{\\{1,3,5\\},2},Z_{\\{1,4,5\\},2},Z_{\\{3,4,5\\},2},$

which cannot be computed by user $2$. Assume that the column-wise sub-matrix
of ${\bf F}$ including the columns with indices in
$\\{4,5,6,10,14,15,16,20\\}$ is ${\bf F}_{2}$ with dimension $12\times 8$,
where

$\displaystyle{\bf
F}_{2}=\left[\begin{array}[]{c:c}{\mathbf{a}}_{\\{1,3,4\\}},{\mathbf{a}}_{\\{1,3,5\\}},{\mathbf{a}}_{\\{1,4,5\\}},{\mathbf{a}}_{\\{3,4,5\\}}&{\bf
0}_{6\times 4}\\\ \hdashline{\bf 0}_{6\times
4}&{\mathbf{a}}_{\\{1,3,4\\}},{\mathbf{a}}_{\\{1,3,5\\}},{\mathbf{a}}_{\\{1,4,5\\}},{\mathbf{a}}_{\\{3,4,5\\}}\\\
\end{array}\right].$

By construction we have
${\mathbf{a}}_{\\{3,4,5\\}}={\mathbf{a}}_{\\{1,4,5\\}}-{\mathbf{a}}_{\\{1,3,5\\}}+{\mathbf{a}}_{\\{1,3,4\\}}$
as shown in (26). The left null space of
$[{\mathbf{a}}_{\\{2,3,4\\}},{\mathbf{a}}_{\\{2,3,5\\}},{\mathbf{a}}_{\\{2,4,5\\}}]$
is the linear space spanned by

${\mathbf{s}}_{2,1}=(-1,0,-1,0,0,1),\ {\mathbf{s}}_{2,2}=(0,0,0,0,1,0),\
{\mathbf{s}}_{2,3}=(0,-1,0,1,0,0).$

Hence, the left null space of ${\bf F}_{2}$ is the linear space spanned by

$\displaystyle({\mathbf{s}}_{2,1},{\bf 0}_{1\times 6}),\
({\mathbf{s}}_{2,2},{\bf 0}_{1\times 6}),\ ({\mathbf{s}}_{2,3},{\bf
0}_{1\times 6}),\ ({\bf 0}_{1\times 6},{\mathbf{s}}_{2,1}),\ ({\bf 0}_{1\times
6},{\mathbf{s}}_{2,2}),\ ({\bf 0}_{1\times 6},{\mathbf{s}}_{2,3}).$

We let each row of ${\bf S}_{2}$ be one random linear combination of the
vectors in (53); in this example, we let

$\displaystyle{\bf
S}_{2}=\left[\begin{array}[]{cccccccccccc}-1&0&-1&0&0&1&0&0&0&0&0&0\\\
0&0&0&0&1&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&-1&0&-1&0&0&1\\\
0&0&0&0&0&0&0&0&0&0&1&0\\\ 0&-1&0&1&0&0&0&-2&0&2&0&0\end{array}\right].$ (65)

Similarly, we let

$\displaystyle{\bf
S}_{3}=\left[\begin{array}[]{cccccccccccc}-1&0&1&-1&0&1&0&0&0&0&0&0\\\
0&0&-1&0&1&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&-1&0&1&-1&0&1\\\
0&0&0&0&0&0&0&0&-1&0&1&0\\\ 0&1&0&0&0&0&0&3&0&0&0&0\end{array}\right],$ (71)
$\displaystyle{\bf
S}_{4}=\left[\begin{array}[]{cccccccccccc}1&-1&0&-1&0&1&0&0&0&0&0&0\\\
1&-1&0&0&1&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&1&-1&0&-1&0&1\\\
0&0&0&0&0&0&1&-1&0&0&1&0\\\ 0&0&1&0&0&0&0&0&4&0&0&0\end{array}\right],$ (77)
$\displaystyle{\bf
S}_{5}=\left[\begin{array}[]{cccccccccccc}-1&-1&0&0&0&1&0&0&0&0&0&0\\\
-2&-1&1&0&1&0&0&0&0&0&0&0\\\ 0&0&0&0&0&0&-1&-1&0&0&0&1\\\
0&0&0&0&0&0&-2&-1&1&0&1&0\\\ 0&0&-1&1&0&0&0&0&-5&5&0&0\end{array}\right].$
(83)

As a summary, the constraint (22) is satisfied by the interference alignment-
like construction, while satisfying this constraint leads to the successful
encoding of each user.

Then we check the decodability. Note that $F_{6}$ and $F_{12}$ have been
recovered by the server from the first round. Recall that ${\mathbf{e}}_{n,i}$
represents the vertical $n$-dimensional standard unit vector whose
$i^{\text{th}}$ element is $1$. For any set of two users
${\mathcal{U}}_{2}=\\{u_{1},u_{2}\\}\subseteq[{\mathsf{K}}]$ where
$|{\mathcal{U}}_{2}|=2$, one can check that from (59)-(83) that the matrix

$\displaystyle\left[\begin{array}[]{c}{\bf S}_{u_{1}}\\\ {\bf S}_{u_{2}}\\\
{\mathbf{e}}_{12,6}^{\text{\rm T}}\\\ {\mathbf{e}}_{12,12}^{\text{\rm
T}}\end{array}\right]$ (88)

whose dimension is $12\times 12$, is full rank; thus the server can recover
$F_{1},\ldots,F_{12}$ and then recover $W_{1}+\cdots+W_{5}$.

For the security, from the first round the server cannot obtain any
information about $W_{1},\ldots,W_{5}$. In the second round, all the
transmissions by all users are linear combinations of $F_{1},\ldots,F_{12}$,
where $F_{6}$ and $F_{12}$ can be recovered from the first round. Since each
$F_{i}$, where $i\in[12]\setminus\\{6,12\\}$ contains ${\mathsf{L}}/10$
symbols, by [17] the server can only obtain additional
$10{\mathsf{L}}/10={\mathsf{L}}$ symbols about $W_{1},\ldots,W_{5}$ from the
second round, which are exactly the symbols in $W_{1}+\cdots+W_{5}$. Hence,
the proposed secure aggregation scheme is secure.

The above scheme could be directly extended to other
${\mathcal{U}}_{1}\subseteq[5]$ where ${\mathcal{U}}_{1}\geq 2$. For example,
consider ${\mathcal{U}}_{1}=[4]$. After the first round, the server can
recover

$\displaystyle\sum_{k_{1}\in[4]}X_{k_{1},j}=\sum_{k_{2}\in[4]}W_{k_{2},j}+\sum_{{\mathcal{V}}\in\binom{[5]}{3}}a_{{\mathcal{V}},j}\underbrace{\sum_{k_{3}\in{\mathcal{V}}\cap[4]}Z_{{\mathcal{V}},k_{3}}}_{:=Z_{{\mathcal{V}}}^{[4]}}$
(89)

for each $j\in[5]$, and recover

$\displaystyle\sum_{k_{1}\in[4]}X_{k_{1},6}=\sum_{{\mathcal{V}}\in\binom{[5]}{3}}a_{{\mathcal{V}},6}Z_{{\mathcal{V}}}^{[4]}.$
(90)

Hence, the server should further recover in the second round

$\displaystyle\left[\begin{array}[]{c}F_{1}\\\ \vdots\\\
F_{12}\end{array}\right]={\bf
F}\left[\begin{array}[]{c}Z_{\\{1,2,3\\},1}^{[4]}\\\
Z_{\\{1,2,4\\},1}^{[4]}\\\ \vdots\\\ Z_{\\{3,4,5\\},1}^{[4]}\\\
Z_{\\{1,2,3\\},2}^{[4]}\\\ Z_{\\{1,2,4\\},2}^{[4]}\\\ \vdots\\\
Z_{\\{3,4,5\\},2}^{[4]}\end{array}\right],$ (102)

where ${\bf F}$ is given in (52), and $F_{6},F_{12}$ have been recovered from
the first round. By choosing ${\bf S}_{1},{\bf S}_{2},{\bf S}_{3},{\bf S}_{4}$
as in (59)-(77), we let each user $k\in[4]$ transmit ${\bf S}_{k}{\bf F}$ in
the second round. For any set of two users
${\mathcal{U}}_{2}=\\{u_{1},u_{2}\\}\subseteq[4]$ where
$|{\mathcal{U}}_{2}|=2$, the matrix in (88) is full rank; thus the
decodability was proved. By the same reason as the case
${\mathcal{U}}_{1}=[5]$, we can also prove that the proposed scheme is secure
for the case ${\mathcal{U}}_{1}=[4]$.

As a result, the proposed secure aggregation scheme achieves
${\mathsf{R}}_{1}=6/5$ and ${\mathsf{R}}_{2}=1/2$, coinciding with the
converse bound in Section IV. $\square$

We are now ready to generalize Example 1 and describe the two-round secure
aggregation scheme for the case ${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$.
Note that to design achievable schemes, as explained in [10], we can assume
that ${\mathsf{q}}$ is large enough without loss of generality.

First round. To achieve
${\mathsf{R}}_{1}=\frac{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}$
coinciding with the converse bound in Section IV, in the first round we divide
each input vector $W_{i}$ where $i\in[{\mathsf{K}}]$ into
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
non-overlapping and equal-length pieces,
$W_{i}=\left\\{W_{i,j}:j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right]\right\\}$.
Hence, each piece contains
$\frac{{\mathsf{L}}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}$
symbols. In addition, for each
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ we generate a key
$Z_{{\mathcal{V}}}$ with
$\frac{{\mathsf{S}}{\mathsf{L}}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}$
symbols uniformly i.i.d. over $\mathbb{F}_{{\mathsf{q}}}$, shared by the users
in ${\mathcal{V}}$. We further divide each key $Z_{{\mathcal{V}}}$ into
${\mathsf{S}}$ non-overlapping and equal-length sub-keys,
$Z_{{\mathcal{V}}}=\\{Z_{{\mathcal{V}},k}:k\in{\mathcal{V}}\\}$, where each
sub-key $Z_{{\mathcal{V}},k}$ contains
$\frac{{\mathsf{L}}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}$
symbols uniformly i.i.d. over $\mathbb{F}_{{\mathsf{q}}}$.

Note that, by the converse bound of Theorem (4), each user
$k\in[{\mathsf{K}}]$ transmits $\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$ linear
combinations of pieces and keys in the first round, while $W_{k}$ only
contains
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
pieces.555This is the main step to deal with the chanllenge arised in the case
${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$ compared to the secure aggregation
scheme in [21] for the case ${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$. More
precisely, when ${\mathsf{S}}\leq{\mathsf{K}}-{\mathsf{U}}$, there may exist
some key for which the whole group of users knowing that key all drop after
the second round. Thus we need to transmit more than one (normalized) linear
combinations in the first round to deal with this event, such that even if all
the knowing users drop during the transmissions, we can still remove
“interference” of this key to recover the task. Hence, in the first round of
the proposed secure aggregation scheme, the first-round transmission by user
$k$,
$X_{k}=\left\\{X_{k,j}:j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]\right\\}$,
contains two parts:

  * •

for
$j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right]$,
we construct

$\displaystyle
X_{k,j}=W_{k,j}+\sum_{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:k\in{\mathcal{V}}}a_{{\mathcal{V}},j}Z_{{\mathcal{V}},k};$
(103)

  * •

for
$j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+1:\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]$,
we construct

$\displaystyle
X_{k,j}=\sum_{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:k\in{\mathcal{V}}}a_{{\mathcal{V}},j}Z_{{\mathcal{V}},k}.$
(104)

For each ${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$, define
${\mathbf{a}}_{{\mathcal{V}}}=\left[a_{{\mathcal{V}},1},a_{{\mathcal{V}},2},\ldots,a_{{\mathcal{V}},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\right]^{\text{\rm
T}}$, where each $a_{{\mathcal{V}},j}\in\mathbb{F}_{{\mathsf{q}}}$ is a
coefficient to be clarified later. By the security constraint, from $X_{k}$,
the server cannot get any information about $W_{k}$; thus by denoting the sets
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ where
$k\in{\mathcal{V}}$ by
${\mathcal{S}}_{k,1},\ldots,{\mathcal{S}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}$,
we aim to have that the coefficients matrix (whose dimension is
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$)

$\displaystyle\left[{\mathbf{a}}_{{\mathcal{S}}_{k,1}},\ldots,{\mathbf{a}}_{{\mathcal{S}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}}\right]\
\text{ has rank equal to $\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$},\ \forall
k\in[{\mathsf{K}}].$ (105)

The choice of ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ is the most non-trivial
design in the proposed secure aggregation scheme, which should satisfy the
security constraint (105) and guarantee the encodability and decodability of
the second-round transmission. Our selection contains two steps:

  * •

First step. For each ${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$
where $1\in{\mathcal{V}}$, we let ${\mathbf{a}}_{{\mathcal{V}}}$ be uniform
and i.i.d. over
$\mathbb{F}^{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}_{{\mathsf{q}}}$. Thus we
have fixed $\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$ coefficient vectors in
random.

  * •

Second step. For each
${\mathcal{V}}\in\binom{[2:{\mathsf{K}}]}{{\mathsf{S}}}$, we let
${\mathbf{a}}_{{\mathcal{V}}}$ be a linear combination of some vectors fixed
in the first step. More precisely, we let

$\displaystyle{\mathbf{a}}_{{\mathcal{V}}}=\sum_{i\in[{\mathsf{S}}]}(-1)^{i-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}.$
(106)

The above choice leads to the following lemma, which is crucial for the
second-round transmissions based on interference alignment.

######  Lemma 1.

By the above choice of coefficient vectors, for each
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and each
$k\in[{\mathsf{K}}]\setminus{\mathcal{V}}$, denoting the number of elements in
${\mathcal{V}}$ smaller than $k$ by $n_{{\mathcal{V}},k}$, we have

$\displaystyle{\mathbf{a}}_{{\mathcal{V}}}=\sum_{i_{1}\in[n_{{\mathcal{V}},k}+1:{\mathsf{S}}]}(-1)^{i_{1}-n_{{\mathcal{V}},k}-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{1})\\}\cup\\{k\\}}+\sum_{i_{2}\in[n_{{\mathcal{V}},k}]}(-1)^{n_{{\mathcal{V}},k}+i_{2}}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{2})\\}\cup\\{k\\}}.$
(107)

$\square$

The proof of Lemma 1 could be found in Appendix A. By Lemma 1, it can be
directly seen that for each $k\in[{\mathsf{K}}]$, from the coefficient vectors
${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
$k\in{\mathcal{V}}$, we can re-construct all
$\binom{{\mathsf{K}}}{{\mathsf{S}}}$ coefficient vectors; thus the constraint
(105) is satisfied with high probability.666We generate
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$ coefficient vectors
${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
$1\in{\mathcal{V}}$, and each vector contains
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$ elements uniformly i.i.d. over a
large enough finite field. Hence, these
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$ coefficient vectors are linearly
independent with high probability.

Due to the user dropouts, the server only receives
$\\{X_{k}:k\in{\mathcal{U}}_{1}\\}$. Hence, for each
$j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right]$,
the server recovers

$\displaystyle\sum_{k_{1}\in{\mathcal{U}}_{1}}X_{k_{1},j}$
$\displaystyle=\sum_{k_{2}\in{\mathcal{U}}_{1}}W_{k_{2},j}+\sum_{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:{\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset}a_{{\mathcal{V}},j}\underbrace{\sum_{k_{3}\in{\mathcal{V}}\cap{\mathcal{U}}_{1}}Z_{{\mathcal{V}},k_{3}}}_{:=Z_{{\mathcal{V}}}^{{\mathcal{U}}_{1}}};$
(108)

for each
$j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+1:\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]$,
the server recovers

$\displaystyle\sum_{k_{1}\in{\mathcal{U}}_{1}}X_{k_{1},j}=\sum_{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:{\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset}a_{{\mathcal{V}},j}Z_{{\mathcal{V}}}^{{\mathcal{U}}_{1}}.$
(109)

Second round. The task of the second round transmission is to let each user
$k\in{\mathcal{U}}_{1}$ transmit $Y^{{\mathcal{U}}_{1}}_{k}$ such that from
any subset of users ${\mathcal{U}}_{2}\subseteq{\mathcal{U}}_{1}$ where
$|{\mathcal{U}}_{1}|\geq|{\mathcal{U}}_{2}|\geq{\mathsf{U}}$, the server can
recover

$\displaystyle\sum_{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:{\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset}a_{{\mathcal{V}},j_{1}}Z_{{\mathcal{V}}}^{{\mathcal{U}}_{1}},\
\forall
j_{1}\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right],$
(110)

from $\\{Y^{{\mathcal{U}}_{1}}_{k_{1}}:k_{1}\in{\mathcal{U}}_{2}\\}$ and
$\left\\{\sum_{k_{1}\in{\mathcal{U}}_{1}}X_{k_{1},j}:j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+1:\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]\right\\}$
in (109). In other words, from
$\\{Y^{{\mathcal{U}}_{1}}_{k_{1}}:k_{1}\in{\mathcal{U}}_{2}\\}$ and the linear
combinations in (109), the server should recover

$\displaystyle\sum_{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:{\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset}a_{{\mathcal{V}},j}Z_{{\mathcal{V}}}^{{\mathcal{U}}_{1}},\
\forall j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right].$ (111)

To achieve ${\mathsf{R}}_{2}=1/{\mathsf{U}}$, we further divide each
$Z_{{\mathcal{V}}}^{{\mathcal{U}}_{1}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
${\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset$, into ${\mathsf{U}}$ non-
overlapping and equal-length coded keys,
$Z_{{\mathcal{V}}}^{{\mathcal{U}}_{1}}=\left\\{Z_{{\mathcal{V}},i}^{{\mathcal{U}}_{1}}:i\in[{\mathsf{U}}]\right\\}$,
where each coded key contains
$\frac{{\mathsf{L}}}{{\mathsf{U}}\left(\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right)}$
symbols. We denote the sets in the collection
$\left\\{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:{\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset\right\\}$,
by
${\mathcal{V}}_{{\mathcal{U}}_{1},1},{\mathcal{V}}_{{\mathcal{U}}_{1},2},\ldots,{\mathcal{V}}_{{\mathcal{U}}_{1},P}$,
where with a slight abuse of notation $P$ represents the number of sets in the
above collection. Thus the recovery task in (111) could be expressed in the
matrix form

$\displaystyle{\bf
F}\left[\begin{array}[]{c}Z_{{\mathcal{V}}_{{\mathcal{U}}_{1},1},1}^{{\mathcal{U}}_{1}}\\\
Z_{{\mathcal{V}}_{{\mathcal{U}}_{1},2},1}^{{\mathcal{U}}_{1}}\\\ \vdots\\\
Z_{{\mathcal{V}}_{{\mathcal{U}}_{1},P},1}^{{\mathcal{U}}_{1}}\\\
Z_{{\mathcal{V}}_{{\mathcal{U}}_{1},1},2}^{{\mathcal{U}}_{1}}\\\ \vdots\\\
Z_{{\mathcal{V}}_{{\mathcal{U}}_{1},P},{\mathsf{U}}}^{{\mathcal{U}}_{1}}\end{array}\right]=\left[\begin{array}[]{c}F_{1}\\\
\vdots\\\
F_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{array}\right]$
(122)

where (recall that $(\mathbf{M})_{m\times n}$ represents the dimension of
matrix $\mathbf{M}$ is $m\times n$)

$\displaystyle{\bf F}=\left[\begin{array}[]{c:c:c:c}({\bf
A})_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}&{\bf
0}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}&\cdots&{\bf
0}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}\\\ \hdashline{\bf
0}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}&({\bf
A})_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}&\cdots&{\bf
0}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}\\\
\hdashline\vdots&\vdots&\ddots&\vdots\\\ \hdashline{\bf
0}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}&{\bf
0}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}&\cdots&({\bf
A})_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times P}\end{array}\right],$ (127)

and

$\displaystyle({\bf A})_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times
P}=\left[\begin{array}[]{c:c:c:c}a_{{\mathcal{V}}_{{\mathcal{U}}_{1},1},1}&a_{{\mathcal{V}}_{{\mathcal{U}}_{1},2},1}&\cdots&a_{{\mathcal{V}}_{{\mathcal{U}}_{1},P},1}\\\
a_{{\mathcal{V}}_{{\mathcal{U}}_{1},1},2}&a_{{\mathcal{V}}_{{\mathcal{U}}_{1},2},2}&\cdots&a_{{\mathcal{V}}_{{\mathcal{U}}_{1},P},2}\\\
\vdots&\vdots&\ddots&\vdots\\\
a_{{\mathcal{V}}_{{\mathcal{U}}_{1},1},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}&a_{{\mathcal{V}}_{{\mathcal{U}}_{1},2},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}&\cdots&a_{{\mathcal{V}}_{{\mathcal{U}}_{1},P},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{array}\right].$
(132)

Note that

$\left\\{F_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}(i-1)+j}:i\in[{\mathsf{U}}],j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+1:\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\right]\right\\}$

is the set of linear combinations in (109), which have already been recovered
by the server in the first round.

Thus we can let each user $k\in{\mathcal{U}}_{1}$ transmit

$\displaystyle Y^{{\mathcal{U}}_{1}}_{k}={\bf S}_{k}\begin{bmatrix}F_{1}\\\
\vdots\\\
F_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{bmatrix},$ (133)

where ${\bf S}_{k}$ with
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
rows represents the matrix of second-round transmission by user $k$. The next
step is to determine ${\bf S}_{k}$ satisfying that

  * •

(c1) in the transmission by each user $k\in{\mathcal{U}}_{1}$, the
coefficients of $Z^{{\mathcal{U}}_{1}}_{{\mathcal{V}},i}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$ and
$i\in[{\mathsf{U}}]$ are $0$, since user $k$ cannot compute such coded keys;

  * •

(c2) for any set ${\mathcal{U}}_{2}\subseteq{\mathcal{U}}_{1}$ where
$|{\mathcal{U}}_{2}|={\mathsf{U}}$, the matrix

$\displaystyle\begin{bmatrix}{\bf S}_{{\mathcal{U}}_{2,1}}\\\ \vdots\\\ {\bf
S}_{{\mathcal{U}}_{2,{\mathsf{U}}}}\\\
{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+1}\\\
{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+2}\\\
\vdots\\\
{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\
{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}+\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+1}\\\
\vdots\\\
{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}+\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\
\vdots\\\
{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{bmatrix}$
(134)

with dimension
${\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$
is full rank.

Note that (c1) guarantees in $Y^{{\mathcal{U}}_{1}}_{k}$, the transmitted
linear combinations of the coded keys do not contain the coded keys which user
$k$ cannot compute; (c2) guarantees that from the second-round transmissions
by any ${\mathsf{U}}$ users in ${\mathcal{U}}_{1}$, the server can recover
(122) and then the computation task
$\sum_{k^{\prime}\in{\mathcal{U}}_{1}}W_{k^{\prime},j}$ for each
$j\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right]$.

Let us focus on one user $k\in[{\mathsf{K}}]$ and construct ${\bf S}_{k}$;
note that, our construction on ${\bf S}_{k}$ is independent of the value of
${\mathcal{U}}_{1}$. Denote the sets in
$\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$ by
$\overline{{\mathcal{S}}}_{k,1},\ldots,\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}$.
By the choice of the coefficient vectors, we have the following lemma, whose
proof could be found in Appendix B.

######  Lemma 2.

The matrix

$\displaystyle\left[{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,1}},{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,2}},\ldots,{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}}\right]$
(135)

with dimension
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}}$,
has rank equal to $\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}$ with high
probability. $\square$

It can be seen from Lemma 2 that, by the choice of the coefficient vectors,
the “interferences” to user $k$ (i.e., the coded keys which user $k$ cannot
compute) are aligned. Thus with high probability the left null space of the
matrix in (135) contains
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}=\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}$
linearly independent vectors, denoted by
${\mathbf{s}}_{k,1},\ldots,{\mathbf{s}}_{k,\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}}$,
each with dimension $1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$.

Then considering the division of keys in the second-round transmission, we
construct the following matrix with dimension
${\mathsf{U}}\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}\times{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$,

$\displaystyle{\bf
S}^{\prime}_{k}=\left[\begin{array}[]{c:c:c:c}\begin{matrix}{\mathbf{s}}_{k,1}\\\
\vdots\\\
{\mathbf{s}}_{k,\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}}\end{matrix}&\begin{matrix}{\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\ \vdots\\\ {\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{matrix}&\begin{matrix}\cdots\\\
\ddots\\\ \cdots\end{matrix}&\begin{matrix}{\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\ \vdots\\\ {\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{matrix}\\\
\hdashline\begin{matrix}{\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\ \vdots\\\ {\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{matrix}&\begin{matrix}{\mathbf{s}}_{k,1}\\\
\vdots\\\
{\mathbf{s}}_{k,\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}}\end{matrix}&\begin{matrix}\cdots\\\
\ddots\\\ \cdots\end{matrix}&\begin{matrix}{\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\ \vdots\\\ {\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{matrix}\\\
\hdashline\vdots&\vdots&\ddots&\vdots\\\ \hdashline\begin{matrix}{\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\ \vdots\\\ {\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{matrix}&\begin{matrix}{\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\\\ \vdots\\\ {\bf
0}_{1\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}\end{matrix}&\begin{matrix}\cdots\\\
\ddots\\\ \cdots\end{matrix}&\begin{matrix}{\mathbf{s}}_{k,1}\\\ \vdots\\\
{\mathbf{s}}_{k,\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}}\end{matrix}\end{array}\right].$
(140)

Finally, we let ${\bf S}_{k}$ be
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
random linear combinations of the rows in ${\bf S}^{\prime}_{k}$, where each
coefficient in each linear combination is uniformly i.i.d. over
$\mathbb{F}_{{\mathsf{q}}}$. This is possible since

$\displaystyle{\mathsf{U}}\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}\geq\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1},$
(141)

whose proof could be found in Appendix C. Note that it will be also proved in
Appendix C that the equality in (141) holds when ${\mathsf{K}}={\mathsf{S}}$.

By construction, the columns in ${\bf S}^{\prime}_{k}{\bf A}$ corresponding to
the coded keys $Z^{{\mathcal{U}}_{1}}_{{\mathcal{V}},j}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$,
${\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset$, and $j\in[{\mathsf{U}}]$,
are all ${\bf 0}_{{\mathsf{U}}\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}\times
1}$. Since the rows of ${\bf S}_{k}$ are linear combinations of the rows in
${\bf S}^{\prime}_{k}$, the columns in ${\bf S}_{k}{\bf A}$ corresponding to
the coded keys $Z^{{\mathcal{U}}_{1}}_{{\mathcal{V}},j}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$,
${\mathcal{V}}\cap{\mathcal{U}}_{1}\neq\emptyset$, and $j\in[{\mathsf{U}}]$,
are all ${\bf
0}_{\left(\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right)\times
1}$. Thus (c1) is satisfied.

In Appendix D, by using the Schwartz-Zippel lemma [29, 30, 31], we have the
following lemma, which shows that (c2) is satisfied by the proposed second-
round transmission.

######  Lemma 3.

For any set ${\mathcal{U}}_{2}\subseteq[{\mathsf{K}}]$ where
$|{\mathcal{U}}_{2}|={\mathsf{U}}$, the matrix in (134) is full rank with high
probability. $\square$

As a result, the decodability of the proposed scheme is proved.777Lemma 3
shows that by randomly selecting some coefficients, the proposed secure
aggregation is decodable with high probability; thus there must exist one
choice of those coefficients such that the proposed scheme is decodable.

For the security of the proposed scheme, we first provide an intuitive
explanation. By (105), the server cannot get any information about
$W_{1},\ldots,W_{{\mathsf{K}}}$ from the first-round transmissions
$X_{1},\ldots X_{{\mathsf{K}}}$. In the second round, all the transmissions
are in the linear space spanned by $F_{1},\ldots
F_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}$, totally
${\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\frac{{\mathsf{L}}}{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}={\mathsf{L}}$
symbols. Hence, by [17], from the second round the server can get at most
${\mathsf{L}}$ symbols information about $W_{1},\ldots,W_{{\mathsf{K}}}$,
which are exactly the ${\mathsf{L}}$ symbols in the computation task
$\sum_{k\in{\mathcal{U}}_{1}}W_{k,j}$ by the decodability proof. Hence, the
server cannot get any information about $W_{1},\ldots,W_{{\mathsf{K}}}$ except
the computation task. Following the above intuitive explanation, the
information theoretic security proof could be directly obtained as in [21,
Appendix C].

######  Remark 1.

The proposed secure aggregation scheme in this section can also work for the
case ${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$. In this case,
${\mathsf{R}}_{1}=\frac{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}=1$
and each input vector is divided into
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$
non-overlapping and equal-length pieces. In the first round transmission, we
only transmit the coded messages in (103), while the coded messages in (104)
does not exist since $\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=0$.
In other words, since the number of users knowing each key is larger than the
maximal number of dropped users, in the first round we do not need to transmit
coded messages in (104) which are only composed of keys. In addition, in the
second round transmission, the proposed scheme also works with the optimal
communication rate ${\mathsf{R}}_{2}=1/{\mathsf{U}}$, while the decodability
and security constraints are both satisfied.

For the case ${\mathsf{S}}>{\mathsf{K}}-{\mathsf{U}}$, compared to the secure
aggregation scheme in [21] with the optimal communication rates, the proposed
secure aggregation scheme in this paper achieves the same optimal
communication rates. However, the proposed scheme requires all the
$\binom{{\mathsf{K}}}{{\mathsf{S}}}$ keys each of which is shared by a
different set of ${\mathsf{S}}$ users and has
$\frac{{\mathsf{S}}}{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}$ symbols; the
number of keys required by the scheme in [21] is at most
${\mathcal{O}}({\mathsf{K}}^{2})$, where each key is shared by ${\mathsf{S}}$
users and has $({\mathsf{K}}-{\mathsf{U}}+1){\mathsf{L}}/{\mathsf{U}}$
symbols. $\square$

##  VI Experimental Results

We implement our proposed secure aggregation scheme in Python3.11 by using the
MPI4py library over the Tencent Cloud, which is then compared to the original
secure aggregation scheme in [6] (referred to as SecAgg). Our comparison
focuses on the model aggregation times of the proposed protocol and SecAgg, by
assuming the offline keys have been already shared.

Figure 2: Model aggregation time of the proposed scheme and SecAgg for
${\mathsf{U}}=\left\lfloor({\mathsf{K}}+1)/2\right\rfloor$ and
${\mathsf{S}}={\mathsf{K}}-{\mathsf{U}}$.

Tencent Cloud Setup. We choose Tencent Cloud instances, specifically
`S6.LARGE16` and `S6.MEDIUM2`. Of these, one `S6.LARGE16` instance plays the
role of the server and all the users. These Tencent Cloud instances are
equipped with Intel Xeon Ice Lake processors running at a base clock speed of
2.7 GHz with a turbo frequency of 3.3 GHz. All instances used in our
experiment are identical in terms of computing power, memory and network
resources. The communication speed between the server and the users is a fast
100MB/s. To generate our input vectors, we set the field size ${\mathsf{q}}$
to $7$ and generate vectors that are uniformly and independently distributed
over $\mathbb{F}_{7}$. We also consider three different sizes for each input
vector: 100KB, 200KB, and 300KB, following the suggestions in [6]. In the
system configuration represented by
$({\mathsf{K}},{\mathsf{U}},{\mathsf{S}})$, we use Monte Carlo methods with
$100$ samples and then average the resulting times over these $100$ samples.

Proposed scheme v.s. SecAgg. We compare the model aggregation times (including
encryption, transmission, decryption times) of our proposed scheme and SecAgg,
for ${\mathsf{U}}=\left\lfloor({\mathsf{K}}+1)/2\right\rfloor$ and
${\mathsf{S}}={\mathsf{K}}-{\mathsf{U}}$, as shown in Fig. 2. We can see that
the proposed scheme outperforms SecAgg by reducing model aggregation time,
where the reduction percent ranges from $29.7\%$ to $67.2\%$. This improvement
coincides with the theoretical perspective that the proposed scheme achieves
the optimal communication cost during the model aggregation phase, while
SecAgg does not.

##  VII Conclusions

In this paper, we aimed to minimize the communication rates in the two-round
transmission of the model aggregation phase, for the information theoretic
secure aggregation problem with uncoded groupwise keys. While preserving the
security on the users’ local data, the secure aggregation scheme should also
be able to tolerate user dropouts. By proposing a new and tight converse bound
coinciding with the achievable rates by the new secure aggregation scheme
based on interference alignment, we fully characterized the region of all
possible rates tuples for the considered problem. Ongoing work includes
further reducing the requirement on the size of keys and extending the secure
aggregation scheme with uncoded groupwise keys to the scenario of clustered
federated learning.

##  Appendix A Proof of Lemma 1

Consider one set ${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
one $k\in[{\mathsf{K}}]\setminus{\mathcal{V}}$. Recall that
$n_{{\mathcal{V}},k}$ represents the number of elements in ${\mathcal{V}}$
which are smaller than $k$.

When $k=1$, we have $n_{{\mathcal{V}},1}=0$ and thus the equation to be
proved, (107), becomes

$\displaystyle{\mathbf{a}}_{{\mathcal{V}}}=\sum_{i_{1}\in[{\mathsf{S}}]}(-1)^{i_{1}-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{1})\\}\cup\\{1\\}},$
(142)

which is exactly (106) and thus is proved.

When $1\in{\mathcal{V}}$ and $k\neq 1$, assume that
${\mathcal{V}}\setminus\\{1\\}={\mathcal{V}}^{\prime}$ where
$|{\mathcal{V}}^{\prime}|={\mathsf{S}}-1$. Hence, (107) becomes

$\displaystyle{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{1\\}}=\sum_{i_{1}\in[n_{{\mathcal{V}},k}+1:{\mathsf{S}}]}(-1)^{i_{1}-n_{{\mathcal{V}},k}-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{1})\\}\cup\\{k\\}}+(-1)^{n_{{\mathcal{V}},k}+1}{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{k\\}}+\sum_{i_{2}\in[2:n_{{\mathcal{V}},k}]}(-1)^{n_{{\mathcal{V}},k}+i_{2}}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{2})\\}\cup\\{k\\}},$
(143a)
$\displaystyle\Longleftrightarrow(-1)^{n_{{\mathcal{V}},k}}{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{k\\}}=\sum_{i_{1}\in[n_{{\mathcal{V}},k}+1:{\mathsf{S}}]}(-1)^{i_{1}-n_{{\mathcal{V}},k}-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{1})\\}\cup\\{k\\}}+\sum_{i_{2}\in[2:n_{{\mathcal{V}},k}]}(-1)^{n_{{\mathcal{V}},k}+i_{2}}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{2})\\}\cup\\{k\\}}-{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{1\\}},$
(143b)
$\displaystyle\Longleftrightarrow{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{k\\}}=\sum_{i_{2}\in[2:n_{{\mathcal{V}},k}]}(-1)^{i_{2}}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{2})\\}\cup\\{k\\}}+(-1)^{n_{{\mathcal{V}},k}+1}{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{1\\}}+\sum_{i_{1}\in[n_{{\mathcal{V}},k}+1:{\mathsf{S}}]}(-1)^{i_{1}-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i_{1})\\}\cup\\{k\\}},$
(143c)
$\displaystyle\Longleftrightarrow{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{k\\}}=\sum_{i_{4}\in[1:n_{{\mathcal{V}},k}-1]}(-1)^{i_{4}-1}{\mathbf{a}}_{{\mathcal{V}}\cup\\{k\\}\setminus\\{{\mathcal{V}}^{\prime}(i_{4})\\}}+(-1)^{n_{{\mathcal{V}},k}-1}{\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{1\\}}+\sum_{i_{3}\in[n_{{\mathcal{V}},k}:{\mathsf{S}}-1]}(-1)^{i_{3}}{\mathbf{a}}_{{\mathcal{V}}\cup\\{k\\}\setminus\\{{\mathcal{V}}^{\prime}(i_{3})\\}},$
(143d)

where (143a) follows since ${\mathcal{V}}(1)=1$ and (143d) follows since we
let $i_{3}=i_{1}-1$ and $i_{4}=i_{2}-1$. It can be seen that (143d) can be
derived by directly expanding
${\mathbf{a}}_{{\mathcal{V}}^{\prime}\cup\\{k\\}}$ according to (106).

Finally, we consider the most involved case where $k\neq 1$ and
$1\notin{\mathcal{V}}$. We first expand the LHS of (107) as in (106); that is,

$\displaystyle{\mathbf{a}}_{{\mathcal{V}}}=\sum_{i\in[{\mathsf{S}}]}(-1)^{i-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}.$
(144)

Then for each $i\in[{\mathsf{S}}]$, we will show in the following that the RHS
of (107) also contains the term
$(-1)^{i-1}{\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}$.
We also expand each term on the RHS of (107) by using (106). Note that
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}$ can
only appear in
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$. We
consider two cases:

  * •

${\mathcal{V}}(i)>k$. The coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$ on
the RHS of (107) is $(-1)^{i-n_{{\mathcal{V}},k}-1}$. We expand
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$ by
using (106). Since the number of elements in ${\mathcal{V}}$ smaller than $k$
is $n_{{\mathcal{V}},k}$ and ${\mathcal{V}}(i)>k$, the number of elements in
${\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}$ smaller than $k$ is
also $n_{{\mathcal{V}},k}$; thus by using (106), the coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}$ in
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$ is
$(-1)^{n_{{\mathcal{V}},k}}.$ Hence, the coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}$ on
the RHS of (107) is
$(-1)^{i-n_{{\mathcal{V}},k}-1}(-1)^{n_{{\mathcal{V}},k}}=(-1)^{i-1}$.

  * •

${\mathcal{V}}(i)<k$. The coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$ on
the RHS of (107) is $(-1)^{n_{{\mathcal{V}},k}+i}$. We expand
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$ by
using (106). Since the number of elements in ${\mathcal{V}}$ smaller than $k$
is $n_{{\mathcal{V}},k}$ and ${\mathcal{V}}(i)<k$, the number of elements in
${\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}$ smaller than $k$ is
$n_{{\mathcal{V}},k}-1$; thus by using (106), the coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}$ in
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$ is
$(-1)^{n_{{\mathcal{V}},k}-1}.$ Hence, the coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}$ on
the RHS of (107) is
$(-1)^{n_{{\mathcal{V}},k}+i}(-1)^{n_{{\mathcal{V}},k}-1}=(-1)^{i-1}$.

After expanding each
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{k\\}}$ where
$i\in[{\mathsf{S}}]$ on the RHS of (107) by using (106), the RHS of (107) may
only contain
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i)\\}\cup\\{1\\}}$ where
$i\in[{\mathsf{S}}]$ and
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
where $1\leq i^{\prime}<i^{\prime\prime}\leq{\mathsf{S}}$. Next we will prove
that the coefficient of each term
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
where $1\leq i^{\prime}<i^{\prime\prime}\leq{\mathsf{S}}$, is $0$.

${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
appears in the expansions of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}}$
and
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}}$.
We consider three cases:

  * •

${\mathcal{V}}(i^{\prime})<{\mathcal{V}}(i^{\prime\prime})<k$. The coefficient
of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}}$
on the RHS of (107) is $(-1)^{n_{{\mathcal{V}},k}+i^{\prime}}$; the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
in the expansion of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}}$
is $(-1)^{i^{\prime\prime}-1-1}=(-1)^{i^{\prime\prime}}$, since the number of
elements in ${\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}$
smaller than ${\mathcal{V}}(i^{\prime\prime})$ is $i^{\prime\prime}-1-1$.
Similarly, the coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}}$
on the RHS of (107) is $(-1)^{n_{{\mathcal{V}},k}+i^{\prime\prime}}$; the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
in the expansion of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}}$
is $(-1)^{i^{\prime}-1}$, since the number of elements in
${\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}$
smaller than ${\mathcal{V}}(i^{\prime})$ is $i^{\prime}-1$. Hence, the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
on the RHS of (107) is

$(-1)^{n_{{\mathcal{V}},k}+i^{\prime}}(-1)^{i^{\prime\prime}}+(-1)^{n_{{\mathcal{V}},k}+i^{\prime\prime}}(-1)^{i^{\prime}-1}=0.$

  * •

$k<{\mathcal{V}}(i^{\prime})<{\mathcal{V}}(i^{\prime\prime})$. The coefficient
of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}}$
on the RHS of (107) is $(-1)^{i^{\prime}-n_{{\mathcal{V}},k}-1}$; the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
in the expansion of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}}$
is $(-1)^{i^{\prime\prime}-1}$, since the number of elements in
${\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}$ smaller
than ${\mathcal{V}}(i^{\prime\prime})$ is $i^{\prime\prime}-1$. Similarly, the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}}$
on the RHS of (107) is $(-1)^{i^{\prime\prime}-n_{{\mathcal{V}},k}-1}$; the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
in the expansion of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}}$
is $(-1)^{i^{\prime}}$, since the number of elements in
${\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}$
smaller than ${\mathcal{V}}(i^{\prime})$ is $i^{\prime}$. Hence, the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
on the RHS of (107) is

$(-1)^{i^{\prime}-n_{{\mathcal{V}},k}-1}(-1)^{i^{\prime\prime}-1}+(-1)^{i^{\prime\prime}-n_{{\mathcal{V}},k}-1}(-1)^{i^{\prime}}=0.$

  * •

${\mathcal{V}}(i^{\prime})<k<{\mathcal{V}}(i^{\prime\prime})$. The coefficient
of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}}$
on the RHS of (107) is $(-1)^{n_{{\mathcal{V}},k}+i^{\prime}}$; the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
in the expansion of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}}$
is $(-1)^{i^{\prime\prime}-1}$, since the number of elements in
${\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime})\\}\cup\\{k\\}$ smaller
than ${\mathcal{V}}(i^{\prime\prime})$ is $i^{\prime\prime}-1$. In addition,
the coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}}$
on the RHS of (107) is $(-1)^{i^{\prime\prime}-n_{{\mathcal{V}},k}-1}$; the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
in the expansion of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}}$
is $(-1)^{i^{\prime}-1}$, since the number of elements in
${\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{k\\}$
smaller than ${\mathcal{V}}(i^{\prime})$ is $i^{\prime}-1$. Hence, the
coefficient of
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{{\mathcal{V}}(i^{\prime}),{\mathcal{V}}(i^{\prime\prime})\\}\cup\\{1,k\\}}$
on the RHS of (107) is

$(-1)^{n_{{\mathcal{V}},k}+i^{\prime}}(-1)^{i^{\prime\prime}-1}+(-1)^{i^{\prime\prime}-n_{{\mathcal{V}},k}-1}(-1)^{i^{\prime}-1}=0.$

As a result, we proved (107).

##  Appendix B Proof of Lemma 2

For each $k\in[{\mathsf{K}}]$, we want to prove that the matrix in (135),
which is

$\displaystyle\left[{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,1}},{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,2}},\ldots,{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}}\right],$
(145)

has rank $\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}$ with high probability, where
${\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,1}},{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,2}},\ldots,{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}}$
denote the vectors
${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$.

We select one user $k^{\prime}\in[{\mathsf{K}}]\setminus\\{k\\}$. Denote the
sets ${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$
where $k^{\prime}\in{\mathcal{V}}$ by
$\overline{{\mathcal{S}}}_{k,k^{\prime},1},\ldots,\overline{{\mathcal{S}}}_{k,k^{\prime},\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}}$.
It can be seen from (106) that, for each
${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{k,k^{\prime}\\}}{{\mathsf{S}}}$
we can re-construct the vector ${\mathbf{a}}_{{\mathcal{V}}}$ by a linear
combination of the vectors
${\mathbf{a}}_{{\mathcal{V}}\setminus\\{k^{\prime\prime}\\}\cup\\{k^{\prime}\\}}$
where $k^{\prime\prime}\in{\mathcal{V}}$. Hence, all the vectors
${\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,1}},{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,2}},\ldots,{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}}$
are linear combinations of
$\overline{{\mathcal{S}}}_{k,k^{\prime},1},\ldots,\overline{{\mathcal{S}}}_{k,k^{\prime},\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}}$.
Hence, the rank of the matrix in (145) is equal to the rank of

$\displaystyle\left[\overline{{\mathcal{S}}}_{k,k^{\prime},1},\ldots,\overline{{\mathcal{S}}}_{k,k^{\prime},\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}}\right].$
(146)

By construction, all the vectors ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ are located in the
linear space spanned by ${\mathbf{a}}_{{\mathcal{V}}_{1}}$ where
${\mathcal{V}}_{1}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
$1\in{\mathcal{V}}_{1}$. Since each vector ${\mathbf{a}}_{{\mathcal{V}}_{1}}$
where ${\mathcal{V}}_{1}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
$1\in{\mathcal{V}}_{1}$, is uniform and i.i.d. over
$\mathbb{F}^{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}}_{{\mathsf{q}}}$ with
large enough ${\mathsf{q}}$, the above linear space has dimension
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$ with high probability. In addition by
(106), the vectors ${\mathbf{a}}_{{\mathcal{V}}_{2}}$ where
${\mathcal{V}}_{2}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
$k^{\prime}\in{\mathcal{V}}_{2}$ can re-construct each vector in this linear
space. Hence, the $\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$ vectors
${\mathcal{V}}_{2}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
$k^{\prime}\in{\mathcal{V}}_{2}$ are linearly independent with high
probability. Hence, we proved that the matrix in (146) is full rank with high
probability, with rank $\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}$. As a result,
we proved that the rank of the matrix in (145) is
$\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}$ with high probability.

##  Appendix C Proof of (141)

We prove (141) by induction.

First consider the case ${\mathsf{U}}=1$. We need to prove

$\displaystyle\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}\geq\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1},$
(147)

which directly holds from Pascal’s triangle
$\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}=\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}$.

Then for any ${\mathsf{U}}\in[i]$, we assume that

$\displaystyle
i\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}\geq\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-i}{{\mathsf{S}}-1}$
(148)

holds, and will prove

$\displaystyle(i+1)\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}\geq\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-i-2}{{\mathsf{S}}-1}.$
(149)

Note that

$\displaystyle\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}>\binom{{\mathsf{K}}-i-2}{{\mathsf{S}}-2}=\binom{{\mathsf{K}}-i-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-i-2}{{\mathsf{S}}-1}.$
(150)

By summing (148) and (150), we can prove (149).

##  Appendix D Proof of Lemma 3

Consider one set ${\mathcal{U}}_{2}\subseteq[{\mathsf{K}}]$ where
$|{\mathcal{U}}_{2}|={\mathsf{U}}$. We want to prove that the matrix in (134)
with dimension
${\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$
is full rank with high probability; i.e., the determinant of the matrix in
(134) is not zero with high probability. Note that the determinant could be
written as $D_{{\mathcal{A}}}=\frac{P_{{\mathcal{A}}}}{Q_{{\mathcal{A}}}}$,
where $P_{{\mathcal{A}}}$ and $Q_{{\mathcal{A}}}$ are multivariate polynomials
whose variables are the elements in ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}}$ and
the coefficients in the
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
random linear combinations of the rows in ${\bf S}^{\prime}_{k}$ for each
$k\in{\mathcal{U}}_{2}$. Since the matrix in (134) exists with high
probability by Lemma 2 and (141), $Q_{{\mathcal{A}}}$ is not zero with high
probability. Hence, it remains to prove that $P_{{\mathcal{A}}}$ is not zero
with high probability neither. Since the variables in $P_{{\mathcal{A}}}$ are
uniform and i.i.d. over $\mathbb{F}_{{\mathsf{q}}}$ where ${\mathsf{q}}$ is
large enough, by the Schwartz-Zippel Lemma [29, 30, 31], if the multivariate
polynomial $P_{{\mathcal{A}}}$ is non-zero (i.e., a multivariate polynomial
whose coefficients are not all $0$), the probability that $P_{{\mathcal{A}}}$
is equal to $0$ over all possible realizations of variables goes to $0$ when
${\mathsf{q}}$ goes to infinity, and thus the matrix in (134) is full rank
with high probability. So in the following, we need to show that
$P_{{\mathcal{A}}}$ is a non-zero polynomial; i.e., we want to find out one
realization of the variables in $P_{{\mathcal{A}}}$, such that the matrix in
(134) exists and is full rank (in this way,
$P_{{\mathcal{A}}}=D_{{\mathcal{A}}}Q_{{\mathcal{A}}}$ is not zero).

We pick one integer $u\in[{\mathsf{K}}]\setminus{\mathcal{U}}_{2}$. We first
select the elements in ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}}$. Note
that the dimension of ${\mathbf{a}}_{{\mathcal{V}}}$ is
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$. We want to let
$[{\mathbf{a}}_{{\mathcal{V}}}:{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},u\in{\mathcal{V}}]$
be an identity matrix with dimension
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}$.
More precisely, we define a collection of sets
${\mathcal{C}}_{1}=\left\\{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:u\in{\mathcal{V}},{\mathcal{V}}\cap{\mathcal{U}}_{2}\neq\emptyset\right\\}$
and sort its sets as
${\mathcal{C}}_{1,1},\ldots,{\mathcal{C}}_{1,\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}$.
Let

$\displaystyle{\mathbf{a}}_{{\mathcal{C}}_{1,i}}={\mathbf{e}}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},i},\
\forall
i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right].$
(151)

In addition, we also define a collection of sets
${\mathcal{C}}_{2}=\left\\{{\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}:u\in{\mathcal{V}},{\mathcal{V}}\cap{\mathcal{U}}_{2}=\emptyset\right\\}$
and sort its sets as
${\mathcal{C}}_{2,1},\ldots,{\mathcal{C}}_{2,\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}}$.
Let

$\displaystyle{\mathbf{a}}_{{\mathcal{C}}_{2,i}}={\mathbf{e}}_{\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}+i},\
\forall i\in\left[\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right].$
(152)

There must exist a choice of ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}}$ which
leads (151) and (152). This is because by Lemma 1, we can obtain
${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}}$ from
the vectors ${\mathbf{a}}_{{\mathcal{V}}^{\prime}}$ where
${\mathcal{V}}^{\prime}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},u\in{\mathcal{V}}$.
Hence, those resulting vectors ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}},1\in{\mathcal{V}}$ can
in turn lead (151) and (152).

Focus on each user $k\in{\mathcal{U}}_{2}$. Recall that the sets in
$\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$ are denoted by
$\overline{{\mathcal{S}}}_{k,1},\ldots,\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}$.
By Lemma 1,
${\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,1}},{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,2}},\ldots,{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}}$
are in the linear space spanned by ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{k\\}}{{\mathsf{S}}}$ and
$u\in{\mathcal{V}}$. Hence, the rank of the matrix
$[{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,1}},{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,2}},\ldots,{\mathbf{a}}_{\overline{{\mathcal{S}}}_{k,\binom{{\mathsf{K}}-1}{{\mathsf{S}}}}}]$
is $\binom{{\mathsf{K}}-2}{{\mathsf{S}}-1}$; thus this matrix with dimension
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}\times\binom{{\mathsf{K}}-1}{{\mathsf{S}}}$
contains $\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}$ linearly independent left
null vectors, which are ${\mathbf{a}}_{{\mathcal{V}}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ and
$\\{u,k\\}\subseteq{\mathcal{V}}$. Let ${\bf s}_{k,1},\ldots,{\bf
s}_{k,\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}}$ be these
$\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}$ vectors, we can obtain ${\bf
S}^{\prime}_{k}$ in (140). Since ${\bf S}^{\prime}_{k}$ exists, ${\bf S}_{k}$,
which are
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
random linear combinations of the rows in ${\bf S}^{\prime}_{k}$, also exists
and thus the matrix in (134) exists.

Let us then select the coefficients in the
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
random linear combinations of the
${\mathsf{U}}\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}$ rows in ${\bf
S}^{\prime}_{k}$ for each $k\in{\mathcal{U}}_{2}$. More precisely, we directly
select
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
rows from ${\bf S}^{\prime}_{k}$ to compose ${\bf S}_{k}$; i.e., in each
linear combination, the coefficient vector contains
${\mathsf{U}}\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}-1$ zeros and $1$ one.
Hence, ${\bf S}_{k}$ contains
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
unit vectors, where these vectors are selected from

$\displaystyle{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},j\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}+i},\
\forall
j\in[0:{\mathsf{U}}-1],i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right],k\in{\mathcal{C}}_{1,i},$

totally ${\mathsf{U}}\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}$ unit vectors.
Recall that the users in ${\mathcal{U}}_{2}$ are denoted by
${\mathcal{U}}_{2}(1),\ldots,{\mathcal{U}}_{2}({\mathsf{U}})$, where
${\mathcal{U}}_{2}(1)<\cdots<{\mathcal{U}}_{2}({\mathsf{U}})$. Our objective
on the selection is that the
${\mathsf{U}}\left(\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right)$
rows in $\begin{bmatrix}{\bf S}_{{\mathcal{U}}_{2}(1)}\\\ \vdots\\\ {\bf
S}_{{\mathcal{U}}_{2}({\mathsf{U}})}\end{bmatrix}$ are exactly

$\displaystyle{\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},j\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}+i},\
\forall
j\in[0:{\mathsf{U}}-1],i\in\left[\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}\right];$

thus the matrix in (134) is an identity matrix (with some row permutation) and
is full rank.

The existence of the above selection is equivalent to the following
combinatorial problem:
(p1). There are
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
urns, where each urn is with the index
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ where
${\mathcal{U}}_{2}\cap{\mathcal{V}}\neq\emptyset$ and $u\in{\mathcal{V}}$.
There are ${\mathsf{U}}$ colors of balls, where the number of balls for each
color with index $k\in{\mathcal{U}}_{2}$ is
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$.
A ball with color $k$ can be only put into an urn with index ${\mathcal{V}}$
where $k\in{\mathcal{V}}$. We want to put the balls into the urns such that
each urn contains ${\mathsf{U}}$ balls (not necessarily with the different
colors).
If there exists a solution for Problem (p1), we can treat each color as one
user in our problem and each urn as a set in
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ where
${\mathcal{U}}_{2}\cap{\mathcal{V}}\neq\emptyset$ and $u\in{\mathcal{V}}$.
Assume the urn with index ${\mathcal{V}}$ contains $x_{1}$ balls with color
$k_{1}$, $x_{2}$ balls with color $k_{2}$, etc. Then for user $k_{1}$, we
select
${\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},j\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}+i}$
where $j\in[k_{1}]$ and ${\mathcal{C}}_{1,i}={\mathcal{V}}$ and put them into
${\bf S}_{k_{1}}$; for user $k_{2}$, we select
${\mathbf{e}}_{{\mathsf{U}}\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1},j\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}+i}$
where $j\in[k_{1}+1:k_{2}]$ and ${\mathcal{C}}_{1,i}={\mathcal{V}}$ and put
them into ${\bf S}_{k_{2}}$, etc. Thus we can see that from the solution for
Problem (p1), we can design the selection of the coefficients satisfying the
matrix in (134) is full rank.

At the end of this section, we provide one solution for Problem (p1), which is
based the Pascal’s triangle

$\displaystyle\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}=\binom{{\mathsf{K}}-2}{{\mathsf{S}}-2}+\binom{{\mathsf{K}}-3}{{\mathsf{S}}-2}+\cdots+\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-2}.$
(153)

Let us focus on the
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
balls in color $k\in{\mathcal{U}}_{2}$, and put these balls into urns by the
following ${\mathsf{U}}$ step:
Step $t\in[{\mathsf{U}}]$. We put one ball in color $k$ into each urn with
index ${\mathcal{V}}$ where
${\mathcal{V}}\in\binom{[{\mathsf{K}}]\setminus\\{{\mathcal{U}}_{2}(<k+1>_{{\mathsf{U}}}),{\mathcal{U}}_{2}(<k+2>_{{\mathsf{U}}}),\ldots,{\mathcal{U}}_{2}(<k+t-1>_{{\mathsf{U}}})\\}}{{\mathsf{S}}}$,
${\mathcal{U}}_{2}\cap{\mathcal{V}}\neq\emptyset$, and
$\\{u,k\\}\subseteq{\mathcal{V}}$. Thus in this step, we have put
$\binom{{\mathsf{K}}-1-t}{{\mathsf{S}}-2}$ balls in color $k$ into urns.
Hence, by the Pascal’s triangle in (153), consider all the ${\mathsf{U}}$
steps for the balls in color $k$, we have put all the
$\binom{{\mathsf{K}}-1}{{\mathsf{S}}-1}-\binom{{\mathsf{K}}-1-{\mathsf{U}}}{{\mathsf{S}}-1}$
balls in color $k$ into urns.

Let us then show that after considering the balls in all colors, each urn has
exactly ${\mathsf{U}}$ balls. Consider an urn with index
${\mathcal{V}}\in\binom{[{\mathsf{K}}]}{{\mathsf{S}}}$ where
${\mathcal{U}}_{2}\cap{\mathcal{V}}\neq\emptyset$ and $u\in{\mathcal{V}}$.
Assume that
${\mathcal{U}}_{2}\cap{\mathcal{V}}={\mathcal{B}}=\\{{\mathcal{U}}_{2}(i_{1}),{\mathcal{U}}_{2}(i_{2}),\ldots,{\mathcal{U}}_{2}(i_{|{\mathcal{B}}|})\\}$,
where $i_{1}<i_{2}<\cdots<i_{|{\mathcal{B}}|}$. We consider two cases:

  * •

$|{\mathcal{B}}|=1$. By construction, in each of the ${\mathsf{U}}$ steps for
color ${\mathcal{B}}(1)$, we put one ball in color ${\mathcal{B}}(1)$ into the
urn with index ${\mathcal{V}}$. Hence, this urn totally contains
${\mathsf{U}}$ balls.

  * •

$|{\mathcal{B}}|>1$. By construction, for each $s\in[|{\mathcal{B}}|]$, in
each of the first $<i_{<s+1>_{|{\mathcal{B}}|}}-i_{s}>_{{\mathsf{U}}}$ steps
for color ${\mathcal{U}}_{2}(s)$, we put one ball in color
${\mathcal{U}}_{2}(s)$ into the urn with index ${\mathcal{V}}$. Hence,
considering all $s\in[|{\mathcal{B}}|]$, the number of balls in this urn is

$\displaystyle<i_{2}-i_{1}>_{{\mathsf{U}}}+<i_{3}-i_{2}>_{{\mathsf{U}}}+\cdots+<i_{|{\mathcal{B}}|}-i_{|{\mathcal{B}}|-1}>_{{\mathsf{U}}}+<i_{1}-i_{|{\mathcal{B}}|}>_{{\mathsf{U}}}=i_{|{\mathcal{B}}|}-i_{1}+<i_{1}-i_{|{\mathcal{B}}|}>_{{\mathsf{U}}}$
$\displaystyle={\mathsf{U}}.$

As a result, we proved that each urn has exactly ${\mathsf{U}}$ balls. Thus
the proposed solution is indeed a solution for Problem (p1). Hence, we showed
that $P({\mathcal{A}})$ is a non-zero polynomial and proved Lemma 3.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [2] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, p. 12, 2019.
  * [3] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 50–60.
  * [4] H. B. McMahan _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1, 2021.
  * [5] J. Geiping, H. Bauermeister, H. Dröge, and M. Moeller, “Inverting gradients - how easy is it to break privacy in federated learning?” _in Advances in Neural Information Processing Systems (NeuIPS)_ , vol. 33, pp. 16 937–16 947, 2020.
  * [6] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in _2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1175–1191.
  * [7] A. Shamir, “How to share a secret,” _Commun. ACM_ , vol. 22, no. 11, pp. 612–613, 1979.
  * [8] Z. Liu, J. Guo, K. Y. Lam, and J. Zhao, “Efficient dropout-resilient aggregation for privacy-preserving machine learning,” _IEEE Trans. on Information Forensics and Security_ , vol. 18, pp. 1839–1854, 2023.
  * [9] A. R. Elkordy and A. S. Avestimehr, “Heterosag: Secure aggregation with heterogeneous quantization in federated learning,” _IEEE Transactions on Communications_ , vol. 70, no. 4, pp. 2372–2386, 2022.
  * [10] Y. Zhao and H. Sun, “Information theoretic secure aggregation with user dropouts,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 11, pp. 7471–7484, Nov. 2022.
  * [11] J. So, B. Güler, and A. S. Avestimehr, “Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning,” _IEEE Journal on Selected Areas in Info. Theory_ , vol. 2, no. 1, pp. 479–489, 2021\.
  * [12] S. Kadhe, N. Rajaraman, O. O. Koyluoglu, and K. Ramchandran, “FastSecAgg: Scalable secure aggregation for privacy-preserving federated learning,” _arXiv:2009.11248_ , Sep. 2020.
  * [13] T. Jahani-Nezhad, M. A. Maddah-Ali, S. Li, and G. Caire, “SwiftAgg+: Achieving asymptotically optimal communication load in secure aggregation for federated learning,” _IEEE Journal on Selected Areas in Communications_ , vol. 41, no. 4, pp. 977–989, Apr. 2023.
  * [14] X. Yang, Z. Liu, X. Tang, R. Lu, and B. Liu, “An efficient and multi-private key secure aggregation for federated learning,” _arXiv:2306.08970_ , Jun. 2023.
  * [15] Z. Liu, J. Guo, W. Yang, J. Fan, K. Y. Lam, and J. Zhao, “Privacy-preserving aggregation in federated learning: A survey,” _IEEE Transactions on Big Data_ , 2022.
  * [16] A. R. Elkordy, Y. H. Ezzeldin, S. Han, S. Sharma, C. He, S. Mehrotra, and S. Avestimehr, “Federated analytics: A survey,” _APSIPA Transactions on Signal and Information Processing_ , 2023.
  * [17] C. E. Shannon, “Communication theory of secrecy systems,” _in The Bell System Technical Journal_ , vol. 28, no. 4, pp. 656–715, Oct. 1949.
  * [18] J. So, C. He, C.-S. Yang, S. Li, Q. Yu, R. E. Ali, B. Guler, and S. Avestimehr, “LightSecAgg: a lightweight and versatile design for secure aggregation in federated learning,” _arXiv:2109.14236_ , Feb. 2022.
  * [19] Z. Li, Y. Zhao, and H. Sun, “Weakly secure summation with colluding users,” _arXiv:2304.09771_ , Apr. 2023.
  * [20] H. U. Sami and B. Güler, “Secure aggregation for clustered federated learning,” _in IEEE Int. Symp. Inf. Theory (ISIT)_ , pp. 186–191, Jul. 2023\.
  * [21] K. Wan, H. Sun, M. Ji, and G. Caire, “On the information theoretic secure aggregation with uncoded groupwise keys,” _arXiv:2204.11364_ , App. 2022\.
  * [22] W. Diffie and M. Hellman, “New directions in cryptography,” _IEEE Trans. Infor. Theory_ , vol. 22, no. 6, pp. 644–654, Nov. 1976.
  * [23] U. M. Maurer, “Secret key agreement by public discussion from common information,” _IEEE Trans. Infor. Theory_ , vol. 39, no. 3, pp. 733–742, May 1993.
  * [24] R. Ahlswede and I. Csiszar, “Common randomness in information theory and cryptography. I. secret sharing,” _IEEE Trans. Infor. Theory_ , vol. 39, no. 4, pp. 1121–1132, Jul. 1993.
  * [25] I. Csiszar and P. Narayan, “Secrecy capacities for multiple terminals,” _IEEE Trans. Infor. Theory_ , vol. 50, no. 12, pp. 3047–3061, Dec. 2004.
  * [26] A. A. Gohari and V. Anantharam, “Information-theoretic key agreement of multiple terminals—part I,” _IEEE Trans. Infor. Theory_ , vol. 56, no. 8, pp. 3973–3996, Aug. 2010.
  * [27] H. Sun, “Secure groupcast with shared keys,” _IEEE Trans. Infor. Theory_ , vol. 68, no. 7, pp. 4681–4699, Mar. 2022.
  * [28] ——, “Compound secure groupcast: Key assignment for selected broadcasting,” _arXiv:2004.14986_ , Apr. 2020.
  * [29] J. T. Schwartz, “Fast probabilistic algorithms for verification of polynomial identities,” _Journal of the ACM (JACM)_ , vol. 27, no. 4, pp. 701–717, 1980\.
  * [30] R. Zippel, “Probabilistic algorithms for sparse polynomials,” in _International symposium on symbolic and algebraic manipulation_. Springer, 1979, pp. 216–226.
  * [31] R. A. Demillo and R. J. Lipton, “A probabilistic remark on algebraic program testing,” _Information Processing Letters_ , vol. 7, no. 4, pp. 193–195, 1978.