On the Information Theoretic Secure Aggregation with Uncoded Groupwise Keys

Kai Wan, Member, IEEE,
Xin Yao,
Hua Sun, Member, IEEE,
Mingyue Ji, Member, IEEE,
and Giuseppe Caire, Fellow, IEEE

K. Wan and G. Caire are with the Electrical Engineering and Computer Science Department, Technische Universität Berlin, 10587 Berlin, Germany (e-mail<EMAIL_ADDRESS>caire@tu-berlin.de). The work of K. Wan and G. Caire was partially funded by the European Research Council under the ERC Advanced Grant N. 789190, CARENET.

X. Yao and M. Ji are with the Electrical and Computer Engineering Department, University of Utah, Salt Lake City, UT 84112, USA (e-mail<EMAIL_ADDRESS>mingyue.ji@utah.edu). The work of X. Yao and M. Ji was supported in part by NSF Awards 1817154 and 1824558.

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.

Secure aggregation, which is a core component of federated learning,
aggregates locally trained models from distributed users at a central server. The “secure” nature of such aggregation consists of the fact that no information about the local users' data must be leaked to the server except the aggregated local models.

In order to guarantee   security, some keys may be shared among the users (this is referred to as the key sharing phase). After the key sharing phase, each user masks its trained model  which is then sent to the  server (this is referred to as the model aggregation phase).
This paper follows the information theoretic secure aggregation problem originally formulated by Zhao and Sun,  with the objective to characterize the minimum communication cost from the $\Ksf$ users in the  model aggregation phase. Due to   user dropouts, which are    common   in real systems,
the server may not receive all messages from the users. A secure aggregation scheme   should tolerate the dropouts  of  at most $\Ksf-\Usf$  users, where $\Usf$ is a system parameter.
The optimal communication cost is characterized by Zhao and Sun, but with the assumption that the keys stored by the users could be any random variables with  arbitrary dependency.
On the motivation that uncoded groupwise keys are more convenient to be shared and could be used in large range of applications besides federated learning, in this paper we add one constraint into the above problem,
namely, that the key variables are mutually independent and each key is shared by a group of  $\Ssf$ users, where $\Ssf$ is another system parameter.

To the best of our knowledge, all existing secure aggregation schemes (with information theoretic security or computational security) assign coded keys to the users.
We show that if  $\Ssf>\Ksf-\Usf$, a new secure aggregation scheme with uncoded groupwise keys can achieve the same
optimal communication cost as the best scheme with coded keys;
if $\Ssf\leq \Ksf-\Usf$, uncoded groupwise key sharing is strictly sub-optimal.
Finally, we also implement our proposed secure aggregation scheme into  Amazon EC2, which are then compared with the
existing secure aggregation schemes with offline key sharing.

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

§ INTRODUCTION

Federated learning is essentially a distributed machine learning framework, where  a central server  aims to solve a machine learning problem by the help of distributed users with local data <cit.>.  A notable advantage  of federated learning compared to other distributed learning scenarios, is the security protection on the users' raw local data against the server. Instead of asking the users to directly upload the raw data,
federated learning lets each user compute the model updates using its local data and securely aggregates these updates at the  server (secure aggregation).
In this paper, we use information theoretic tools to focus on two core challenges  of the secure aggregation process in federated learning, namely the effect of user   dropouts  and the communication efficiency <cit.>. First, in a real environment some users may drop or reply   slowly  during the training process due to the network connectivity or computational capability.
It is non-trivial to let the server  recover the aggregated updated models of the surviving users securely
while mitigating the effect of potential user   dropouts. Second,  additional communication among the users and server
may be needed to guarantee the perfect  security and   mitigate the effect of the user dropouts, for example,   additional communications on exchanging the keys among the users may be taken. Since a  federated learning system   usually contains of a massive number of devices, the minimization of the communication cost is crucial.

The secure aggregation problem with   user dropouts   was originally considered in <cit.>,   and generally contains two phases: offline key   sharing   and model aggregation, where the user dropouts may happen in either phase or both phases.
In the first phase, the users generate  random seeds, and secretly  share their private random seeds such that some keys are shared among the users.
The offline key sharing phase   is independent of the users' local training data,  and thus can take place   during off-peak traffic times when the network is not busy.
For example, the secure aggregation schemes in <cit.> all make use of offline key sharing protocols.[Online key sharing protocols (for example the ones proposed  in <cit.>) which are beyond the scope of this paper,   allow
users to communicate some information about the updated models and keys among each other,  while in offline protocols  users can only share keys.]
If there is no private link among users,
the communication among users should go through the central server,  and some  key agreement protocol  such as <cit.>    is needed,    whereby two or more parties can agree on a key
by communicating some local information through a public link, such that even if some eavesdropper  can observe the communication in the public link, it cannot   determine   the shared key.
Once the keys are shared among the users, the users mask the updated models by the keys and send
masked   models to the server, such that the server could recover   the aggregated   models of the  surviving users without getting any other information about the users' local data.

Recently, the authors in <cit.> proposed an information theoretic formulation of the secure aggregation problem with   user dropouts originally considered in <cit.>,  whose objective  is to characterize  the fundamental limits of the communication cost while preserving the  information theoretic security of the users' local data.[Among the existing secure aggregation schemes with     user dropouts,  the ones in <cit.> considered the   information theoretic security constraint <cit.>, while the others considered the computational security.]
Due to the difficulty to characterize  the fundamental limits of the communication rates in both two phases,  with the assumption    that  the  key sharing phase  has been already performed during network off-traffic times and any keys with arbitrary dependency could be used in the model aggregation phase (i.e.,  we only consider the model aggregation phase and ignore the cost of the key sharing phase),
the authors   in <cit.>   formulated a $(\Ksf,\Usf )$ two-round information theoretic  secure aggregation problem for the server-users communication model, where  $\Ksf$ represents the number of users, $\Usf$ represents the minimum number of surviving users.[The problem  in <cit.> only considers one epoch of the       learning process.]

Each user can communicate with the server while the communication  among users is not allowed.
The server aims to compute the element-wise sum of the vector inputs  (i.e., updated models) of $\Ksf$ users, where the input vector of  user $k$ is denoted by $W_k$ and contains $\Lsf$ uniform and i.i.d. symbols over a    finite field $\mathbb{F}_{\qsf}$.
Each user $k$ has stored a key $Z_k$, which can be any random variable    independent of  $W_1,\ldots,W_{\Ksf}$.  The transmissions (in the   model aggregation phase) contains two rounds.[It was shown in <cit.> that for the sake of security under user dropouts, at least two rounds communications must be taken.]
In the first round of transmission, each user $k \in \{1,\ldots,\Ksf\}$ sends a coded message $X_k$ as a function of $W_k$ and $Z_k$ to the server. Since some users may drop during its transmission, the server only receives the messages from the users in $\Uc_1$ where $|\Uc_1|\geq \Usf$.
Then the server informs the users    in the subset $\Uc_1$ of non-dropped users.
In the second round of transmission, after knowing the set $\Uc_1$, each user $k\in \Uc_1$ transmits another coded message $Y^{\Uc_1}_k$ as a function of $(W_k,Z_k,\Uc_1)$ to the server. Due to the user dropouts in the second round, letting $\Uc_2$ denote the set of surviving users in the second round with $\Uc_2 \subseteq \Uc_1$ and  $|\Uc_2| \geq  \Usf$,   the server receives $Y^{\Uc_1}_k$ where $k\in \Uc_2$.
By receiving $(X_k:k\in \Uc_1)$ and $(Y^{\Uc_1}_k: k\in \Uc_2)$, the server should recover  the element-wise sum $\sum_{k\in \Uc_1}W_k$ without getting any other information about $W_1,\ldots,W_{\Ksf}$ even if the server can receive $(X_k:k\in  [\Ksf]\setminus \Uc_1)$, $ (Y^{\Uc_1}_k: k\in \Uc_1 \setminus\Uc_2) $ (e.g., the users are not really dropped but too slow in the transmission).
Since  the identity of the dropped users in each round is not known  a priori by the users unless they receive the list of surviving users from the server,
we should design $(X_k:k\in \{1,\ldots,\Ksf\})$ and $(Y^{\Uc_1}_{k}:k\in \Uc_1)$ for any sets $\Uc_1, \Uc_2$ where $\Uc_2 \subseteq \Uc_1\subseteq \{1,\ldots,\Ksf\}$ and $|\Uc_1|\geq |\Uc_2|\geq \Usf$, while minimizing the communication rates by the users in two rounds.
It was shown in <cit.> that
the minimum numbers of symbols that each user needs to send are $\Lsf$   over
the first round, and $\Lsf/\Usf$   over the second round,  which can be  achieved simultaneously by   a novel secure aggregation scheme.
Another secure aggregation scheme was proposed in <cit.> for the above problem, which needs a less amount of generated keys  in the system than that of <cit.>.

To the best of our knowledge, all existing secure aggregation schemes with offline key sharing let the users share and store coded keys, through secret sharing    (such as <cit.>) or Minimum Distance Separable (MDS) codes (such as <cit.>).[The key sharing protocols in <cit.> are designed for the network where  no private links exist among  users, under the constraint of computational security. The key sharing protocols in <cit.> lead to information theoretic privacy, but under the constraint  that there are private links among users for the key sharing phase.]
In this paper, we  follow the information theoretic secure aggregation problem with   user dropouts in <cit.>, while adding the additional constraint of uncoded groupwise keys as illustrated in Fig. <ref>.[The constraint of uncoded groupwise keys means that, the keys are independent among each other and each key is stored by a set of users.]
By defining a system parameter $\Ssf\in \{1,\ldots,\Ksf\}$, for each $\Vc \subseteq \{1,\ldots,\Ksf\}$ where $|\Vc|= \Ssf$, there exists a   key   $Z_{\Vc}$ shared by the users in $\Vc$,  which is independent of other keys.[Note that all existing secure aggregation schemes fail to satisfy this constraint  when $\Ssf<\Ksf$, due to the coded keys shared among users.]
The uncoded groupwise keys could be directly generated and shared among users by some key agreement protocol  such as <cit.>, even if there do  not exist private links among users.[To generate an uncoded groupwise key shared among $\Ssf$ users, we need $\Ssf-1$ pairwise key agreement communications, each of which is between two users.] In addition, uncoded groupwise keys may be preferred   in   practice
since  they can be generated    with low complexity and shared conveniently, and find a wide range of applications besides secure aggregation in federated learning.[For example, the uncoded pairwise key shared among each two users are independent of the other keys and thus can guarantee the information theoretic secure communication between these two users, while the other users (who may collude) are eavesdropper  listening to the communication <cit.>.   However, the pairwise coded keys used in the scheme <cit.> cannot guarantee secure communication between any two users, because the coded key shared by these two users are correlated to other keys stored by the other users.]
Our objective is to characterize the capacity  region of the
numbers of transmissions  by the users in two rounds of the  model  aggregation phase (i.e., the rates region).

First round.

Second round.

$(\Ksf,\Usf,\Ssf)=(4,2,3)$ information theoretic secure aggregation problem with uncoded groupwise keys.

§.§ Main Contributions

In this paper, we first formulate  the new information theoretic   secure aggregation problem with uncoded groupwise keys. Then our main contributions on this new model   are as follows:

* When $\Ssf >\Ksf-\Usf$, we propose a new secure aggregation scheme which achieves exactly the same capacity region as in <cit.>; this means that, when $\Ssf >\Ksf-\Usf$, secure aggregation with uncoded groupwise key sharing  has no loss on the communication efficiency.

It is also interesting to see that by increasing $\Ssf$ above $\Ksf - \Usf+1$ yields no reduction in the transmission cost; i.e.,  $\Ssf = \Ksf - \Usf + 1$ is sufficient and no larger value of  $\Ssf$ provide improvements.

The main technical challenge  of the proposed scheme  based on linear coding is to   determine    the coefficients of the keys in the two round transmissions, satisfying the encodability (i.e., the keys cannot appear in the transmitted linear combinations by   the users who do not know them), decodability, and security constraints.  We overcome these challenges by designing new interference alignment strategies.[Interference alignment was originally proposed in <cit.> for the wireless interference channel, which aligns the undesired packets (i.e., interference) by each user such that their linear space dimension is reduced.]
Note that, to achieve the optimal   rates region by our proposed scheme, not all the keys $Z_{\Vc}$ where $\Vc \subseteq \{1,\ldots,\Ksf\}$ and $|\Vc|= \Ssf$ are needed during the transmission.
The number of   needed keys is       either $\Oc(\Ksf)$ or  $\Oc(\Ksf^2)$, where each key has $(\Ksf-\Usf+1)\Lsf/\Usf$ symbols.

* When $\Ssf \leq \Ksf-\Usf$, we derive a new converse bound  to show that the optimal rates region of the considered problem is   a  strict subset of that in <cit.> (which is without any constraint on the keys). This implies that in this regime using uncoded keys strictly hurts.

* Experimental results  over the Amazon EC2 cloud  show that the proposed secure aggregation scheme
reduces the communication time in the model aggregation  by up to $53\%$ compared to the original secure aggregation scheme in <cit.>, and reduces    the key sharing time up to $31.7\%$ compared to the best existing information theoretic secure aggregation scheme with offline key sharing in <cit.>.

§.§ Paper Organization

The rest of this paper is organized as follows. Section <ref> formulates the considered secure aggregation problem with uncoded groupwise keys. Section <ref> lists the main results of this paper. The proposed secure aggregation scheme is introduced in Section <ref>. Experimental results are provided in Section <ref>.  Section <ref> concludes the paper, while some proofs can be found in the Appendices.

§.§ 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}_{\qsf}$ represents a  finite field with order $\qsf$;
$\ev_{n,i}$ represents the vertical $n$-dimensional unit vector  whose entry in the  $i^{\text{th}} $ position is 1 and 0 elsewhere;
$\mathbf{1}_{n}$  and $\mathbf{0}_{n}$ represent  the vertical $n$-dimensional   vector  whose elements are all $1$ and all $0$, respectively;
$\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{\Xc}{y}=\{\Sc \subseteq \Xc: |\Sc|=y \}$ where $|\Xc|\geq y>0$.

In the rest of the paper entropies will be in base $\qsf$, where $\qsf$ represents the field size.

§ SYSTEM MODEL

We formulate a $(\Ksf,\Usf, \Ssf)$ information theoretic secure aggregation problem with uncoded groupwise keys as illustrated in Fig <ref>,
which contains one   epoch of the learning process among
$\Ksf$ users and one server. For each $k\in [\Ksf]$,  user $k$ holds one input vector (i.e., updated model) $W_k$ composed of  $\Lsf$ uniform and i.i.d. symbols over a  finite field $\mathbb{F}_{\qsf}$. As in <cit.>, we assume that $\Lsf$ is large enough. Ideally, the server aims to compute the element-wise sum of input vectors of all users.
However, due to the user  dropouts,  the server may not be able to recover the sum of all input vectors. Hence, we let the server compute the sum of the input vectors from the surviving users, where the number of surviving users is at least $\Usf$. In this paper, we mainly deal with   the user dropouts and thus we assume that $\Usf\in [\Ksf-1]$.[When $\Usf=\Ksf$, it was shown in <cit.>  (by taking $\Nsf_{\rm r}=\Nsf$ in <cit.>) that one round transmission is enough and that the minimum number of transmitted symbols by each user is $\Lsf$.]
In addition, by the secure aggregation constraint, the server must not retrieve any other information except the task from the received symbols. In order to guarantee the security, the users must share some secrets (i.e., keys) which are independent of the input vectors. Different from the  secure aggregation problem
in <cit.> which   assumes that the keys could be any random variables shared among   users, in this paper we consider uncoded groupwise keys, where  the keys are independent of each other and each key is shared among   $\Ssf$ users where $\Ssf\in [\Ksf]$, which is shared through private link between each two users or  by the key agreement  protocols such as <cit.>.
For each set $\Vc \in \binom{[\Ksf]}{\Ssf}$,  there exists a key $Z_{\Vc}$ independent of other keys.

\begin{align}
H\left( \big(Z_{\Vc}:  \Vc \in \binom{[\Ksf]}{\Ssf}), (W_1,\ldots,W_{\Ksf}\big)  \right) = \sum_{ \Vc \in \binom{[\Ksf]}{\Ssf} } H(Z_{\Vc}) +\sum_{k\in[\Ksf]} H(W_k). \label{eq:key constraint}
\end{align}

We define
Z_k := \left(Z_{\Vc}: \Vc \in \binom{[\Ksf]}{\Ssf}, k \in \Vc \right),
as  the keys accessible by the user $k\in [\Ksf]$.
The whole secure aggregation procedure contains the following two rounds.

First round.
In the first round, each user $k\in [\Ksf]$ generates a message $X_k$ as a function of $W_k$ and $Z_k$,  without knowing the identity of the dropped users.
The communication rate of the first round $\Rsf_1$ is defined as the largest transmission load among all users normalized by $\Lsf$, i.e.,

\begin{align}
\Rsf_1:= \max_{k\in [\Ksf]} \frac{|X_k|}{\Lsf}. \label{eq:def of R1}
\end{align}

User $k$ then sends $X_k$ to the server.

Some users may drop in the first round transmission,  and the set of surviving users after the first round is denoted as $\Uc_1$,  where $\Uc_1 \subseteq [\Ksf]$ and $|\Uc_1|\geq \Usf$. Thus  the server receives  $X_k$ where $k\in \Uc_1$.

Second round.
In the second round, the server first sends the list of the surviving users (i.e., the set $\Uc_1$) to each user in $\Uc_1$. Then each user $k\in \Uc_1$ participates in the second round transmission by generating and sending a message $Y^{\Uc_1}_{k}$ as a function of $W_k$, $Z_k$, and $\Uc_1$.
The communication rate of the second round $\Rsf_2$ is defined as the largest transmission load among all $\Uc_1$ and all users in $\Uc_1$ normalized by $\Lsf$, i.e.,

\begin{align}
\Rsf_2 := \max_{\Uc_1 \subseteq [\Ksf]:|\Uc_1|\geq \Usf} \ \max_{k\in \Uc_1}  \frac{|Y^{\Uc_1}_{k}|}{\Lsf}. \label{eq:def of R2}
\end{align}

Some users may also drop in the second round transmission,  and the set of surviving users after the second round is denoted as $\Uc_2$,  where $\Uc_2 \subseteq \Uc_1$ and $|\Uc_2|\geq \Usf$. Thus  the server receives  $Y^{\Uc_1}_{k}$  where $k\in \Uc_2$.

The server should recover $\sum_{k\in \Uc_1} W_k$ from $( X_{k_1} : k_1 \in \Uc_1 )$ and $( Y^{\Uc_1}_{k_2}: k_2 \in \Uc_2 )$, i.e.,

\begin{align}
H\left( \sum_{k\in \Uc_1} W_k \Big|  ( X_{k_1} : k_1 \in \Uc_1 ), ( Y^{\Uc_1}_{k_2}: k_2 \in \Uc_2 ) \right)=0, \ \forall \Uc_1 \subseteq [\Ksf], \Uc_{2} \subseteq \Uc_1 : |\Uc_1| \geq  |\Uc_2|\geq \Usf. \label{eq:decodability}
\end{align}

Meanwhile, the security constraint imposes that after receiving all messages sent by the users  including   the  dropped  users (e.g., the users are not really dropped but too slow in the transmission), the server cannot get any other information about the input vectors except  $\sum_{k\in \Uc_1} W_k$, i.e.,

\begin{align}
I\left(   W_1,\ldots,W_{\Ksf} ; X_1,\ldots, X_{\Ksf}, ( Y^{\Uc_1}_{k}: k \in \Uc_1 )   \Big|  \sum_{k\in \Uc_1} W_k \right)=0 , \ \forall \Uc_1 \subseteq [\Ksf] : |\Uc_1|\geq \Usf. \label{eq:security constraint}
\end{align}

A rate tuple $(\Rsf_1,\Rsf_2)$ is achievable if there exist keys $\left(Z_{\Vc}:  \Vc \in \binom{[\Ksf]}{\Ssf} \right) $ satisfying (<ref>) and a secure aggregation scheme satisfying the decodability and security constraints in (<ref>) and (<ref>). Our objective is to determine the capacity region (i.e., the closure of all achievable rate tuples) of the considered problem, denoted by $\Rc^{\star}$.

A converse bound from <cit.>.
By removing the uncoded groupwise constraint on the keys in our considered problem, we obtain the information theoretic aggregation problem in <cit.>. Hence, the converse bound  on the capacity region in <cit.>  is also a converse bound for our considered problem, which leads to the following lemma.

For the $(\Ksf,\Usf, \Ssf)$ information theoretic secure aggregation problem with uncoded groupwise keys, any achievable rate tuple $(\Rsf_1,\Rsf_2)$ satisfies

\begin{align}
\Rsf_1 \geq 1, \ \Rsf_2 \geq \frac{1}{\Usf}. \label{eq:converse from litterature}
\end{align}

However,  the achievable secure aggregation schemes in <cit.> cannot work in our considered problem with $\Ssf<\Ksf$, since
the schemes in <cit.> assign correlated coded keys to   users, while in our considered problem
the keys are uncoded, groupwise-sharing and independent.

Another observation is that the capacity region of the $(\Ksf,\Usf, \Ssf_1)$ information theoretic secure aggregation problem with uncoded groupwise keys covers that of the   $(\Ksf,\Usf, \Ssf_2)$ information theoretic secure aggregation problem with uncoded groupwise keys, where $\Ssf_1>\Ssf_2$. This is because, without collusion between the server and the users, having more users knowing the same key will not hurt. So any key $Z_{\Vc_2}$ could be generated by  extracting some symbols from
$Z_{\Vc_1}$  where $\Vc_2 \subseteq \Vc_1$.

§ MAIN RESULTS

We first present the main result of our paper.

For the $(\Ksf,\Usf, \Ssf)$ information theoretic secure aggregation problem with uncoded groupwise keys, when $\Ssf > \Ksf-\Usf$, we have

\begin{align}
\Rc^{\star} = \left\{(\Rsf_1,\Rsf_2): \Rsf_1 \geq 1, \Rsf_2\geq \frac{1}{\Usf} \right\}. \label{eq:main result thm}
\end{align}

The converse bound for Theorem <ref> is directly from Lemma <ref>.
For the achievability, we propose a    new secure aggregation  scheme based on linear coding and interference alignment, which is described in
Section <ref>.

When $\Ssf > \Ksf-\Usf$, the proposed scheme for Theorem <ref> achieves the same capacity region as the optimal secure aggregation scheme without any constraint on the keys in <cit.>. It is also interesting to see that
increasing $\Ssf$ above $\Ksf-\Usf+1$ will not reduce the communication cost.

There are totally $ \binom{\Ksf}{\Ssf}$ subsets of $[\Ksf]$ with cardinality   $\Ssf$.
By the problem setting,   we can   use at most $ \binom{\Ksf}{\Ssf}$ keys each of which is shared by  $\Ssf$ users.
However, we do not need to use  generate all these $ \binom{\Ksf}{\Ssf}$ keys in our proposed secure scheme for Theorem <ref>.
It will be clarified in Section <ref> that,  the number of needed keys by the proposed secure aggregation scheme for Theorem <ref>  is  $\Ksf$ when $\Usf\leq \Ksf-\Usf+1$ and is $\Oc(\Ksf^2)$   when $\Usf> \Ksf-\Usf+1$, where each   key has $(\Ksf-\Usf+1)\Lsf/\Usf$ symbols.
Note that if coded key assignment is allowed,
the secure aggregation scheme in <cit.> needs to generate  $\Usf$ coded keys with $\Lsf/\Usf$ symbols  for  each group of users $\Vc\subseteq [\Ksf]$ where $|\Vc|\in [\Usf:\Ksf]$, where  each user in the group stores a linear combination of these $\Usf$ coded keys;
for each pair of users $\Vc\subseteq [\Ksf]$ where $|\Vc|=2$,
the secure aggregation scheme in <cit.>  lets each user in the pair generate  a coded    key  with $\Lsf/\Usf$ symbols and
share it to the other user in the pair.

More precisely,
the proposed   scheme  divides the case $\Ssf>\Ksf-\Usf$ into three sub-cases,

* $\Usf\leq \Ksf-\Usf+1$, where the number of needed keys is $\Ksf$, and each key is shared by $\Ksf-\Usf+1$ users and has $\Ssf\Lsf/\Usf$ symbols;

* $\Usf> \Ksf-\Usf+1$ and $\Usf=\Ksf-1$, where the number of needed keys is $\frac{\Ksf(\Ksf-1)}{2}$, and each key is shared by $\Ksf-\Usf+1$ users and has $\Ssf\Lsf/\Usf$ symbols;

* $\Usf> \Ksf-\Usf+1$ and $\Usf<\Ksf-1$, where the number of needed keys is $\Usf+  \frac{\Ksf(2\Usf-\Ksf+1)}{2}$, and each key is shared by $\Ksf-\Usf+1$ users and has $\Ssf\Lsf/\Usf$ symbols.

To summarize, the number of   needed keys is  no more than $\Oc(\Ksf^2)$, where each key has $\Ssf\Lsf/\Usf$ symbols.

For the case $\Ssf \leq \Ksf-\Usf$, the following theorem shows that the communication rate of the optimal
secure aggregation scheme without any constraint on the keys in <cit.> cannot be achieved; i.e., the capacity region of the considered problem is a strict subset of the one in <cit.>.

For the $(\Ksf,\Usf, \Ssf)$ information theoretic secure aggregation problem with uncoded groupwise keys, when $1=\Ssf \leq  \Ksf-\Usf$, secure aggregation is not possible; when  $2\leq \Ssf \leq  \Ksf-\Usf$,  the communication rate of the first round must satisfy

\begin{align}
\Rsf_1\geq  1+\frac{1}{  \binom{\Ksf-1}{\Ssf-1}-1} .\label{eq:converse of R1}
\end{align}

The proof of Theorem <ref> can be found in Appendix <ref>. From  Theorem <ref>, when  $2\leq \Ssf \leq  \Ksf-\Usf$,  it is not enough for each user  to transmit one (normalized) linear combination of the input vector and keys. Intuitively, this is  because  the total number of  dropped users after the second round could be
larger than or equal to $\Ssf$, which is the number of users sharing each key;
thus some key(s) appearing in the transmission of the first round, may not be received in the received packets of the second round due to the user dropouts. Hence, we need to transmit more than one   (normalized) linear combination in the first round.
It is one of our on-going works to design tight achievable schemes and converse bounds for the case  $2\leq \Ssf \leq \Ksf-\Usf$.

§ PROOF OF THEOREM <REF>: NEW SECURE AGGREGATION SCHEME

When $\Usf=\Ksf$ (i.e., there is no user dropout), the solution is simple. For each $k\in [\Ksf]$, let $Z_{\{k\}}$ contain $\Lsf$ uniform and i.i.d. symbols known by user $k$. In the first round,  user $k$ transmits $X_k=W_k+Z_{\{k\}}$. In the second round, user $k$ transmits $Y^{[\Ksf]}_{k}=Z_{\{k\}}$. Obviously, the scheme is decodable and secure.

In the rest of this section, we consider the case   $\Usf<\Ksf$.

To present the proposed scheme,   we only need to focus on the case where $\Ssf=\Ksf-\Usf+1$.
As we explained at the end of Section <ref>, this is because
if $\Ssf>\Ksf-\Usf+1$,
we can generate any key $Z_{\Vc}$ where $\Vc\in \binom{[\Ksf]}{\Ksf-\Usf+1}$ by extracting some symbols from   $Z_{\Vc_1}$ where $\Vc_1 \in\binom{[\Ksf]}{\Ssf}$ and $\Vc \subseteq \Vc_1 $, while the users in $\Vc_1\setminus \Vc$ will not use $Z_{\Vc }$ even they know it. Thus
a  secure aggregation scheme for the case $\Ssf=\Ksf-\Usf+1$ could also work for the case $\Ssf >\Ksf-\Usf+1$.

The construction structure of the achievable scheme  is as follows.

* Since the length of each input vector  $W_i$ where $i\in [\Ksf]$ is large enough,  as explained in <cit.>,
we can consider blocks of symbols of $W_i$ as an element of a suitably large field extension  and consider operations such as element wise sum as operations over the field extension.
Hence, without loss of generality, in the scheme proposed in this paper we can assume    that $\qsf$ is large enough.
We then divide each input vector $W_i$ where $i\in [\Ksf]$ into $\Usf$ non-overlapping and equal-length pieces, where the $j^{\text{th}}$ piece denoted by $W_{i,j}$ contains $\Lsf/\Usf$ symbols on $\mathbb{F}_{\qsf}$.
In addition, for each $\Vc\in \binom{[\Ksf]}{\Ssf}$ and each $k\in\Vc$,[Recall that $\binom{\Xc}{y}=\{\Sc \subseteq \Xc: |\Sc|=y \}$ where $|\Xc|\geq y>0$.]
we let $Z_{\Vc,k}$ denote a vector of $\Lsf/\Usf$ uniform i.i.d. symbols on $\mathbb{F}_{\qsf}$. Then, we define a key  $Z_{\Vc}= (Z_{\Vc,k}: k\in \Vc)$ and let $Z_{\Vc}$  be shared by all users in $\Vc$.

* In the first  round,  each user $k\in [\Ksf]$ sends

\begin{align}
X_{k,j} = W_{k,j} + \sum_{\Vc\in\binom{[\Ksf]}{\Ssf}: k \in \Vc} a_{\Vc, j} Z_{\Vc,k}  , \ \forall j \in [\Usf],
\label{eq:transmission of X_k,j}
\end{align}

where $a_{\Vc, j} \in \mathbb{F}_{\qsf}$ is a coefficient to be designed.[In this paper, the product $a \bv$  where $a$ is a scalar and $\bv$ is a vector or a matrix, represents multiplying each element in $\bv$ by $a$.]  Note that each $X_{k,j}$ contains $\Lsf/\Usf$ symbols, and thus
$X_{k}=(X_{k,1},\ldots,X_{k,\Usf})$ contains $\Lsf$ symbols, which leads to $\Rsf_1=1$.

We let   $\av_{\Vc} :=[a_{\Vc,1},\ldots,a_{\Vc,\Usf}]^{\text{\rm T}}$.
By the security constraint,
$W_{k}$ should be perfectly protected by the keys in $X_{k}=(X_{k,1},\ldots,X_{k,\Usf})$. Thus, by denoting  the sets $\Vc\in \binom{[\Ksf]}{\Ssf}$ where   $k \in \Vc$  by  $\Sc_{k}(1),\ldots,\Sc_{k}\left(\binom{\Ksf-1}{\Ssf-1}\right)$, we   aim to have that    the coefficients matrix  (whose dimension is   $\Usf \times \binom{\Ksf-1}{\Ssf-1}$)

\begin{align}
\left[\av_{\Sc_{k}(1)},\ldots, \av_{\Sc_{k}\left(\binom{\Ksf-1}{\Ssf-1}\right)} \right] \ \text{ has rank equal to $\Usf$}, \ \forall k\in[\Ksf]. \label{eq:full rank constraint}
\end{align}

If the constraints  in (<ref>) are satisfied, with the fact that   the keys are independent of the input vectors,    the server cannot
get any information about $W_1,\ldots,W_{\Ksf}$ even if the server receives all $X_1,\ldots,X_{\Ksf}$ (the formal proof is given in (<ref>) in Appendix <ref>).

Since the set of surviving users after the first round is $\Uc_1$, the server receives $X_k$ where $k\in \Uc_1$, and thus can recover

\begin{align}
\sum_{k\in \Uc_1} X_{k,j} &= \sum_{k\in \Uc_1} W_{k ,j} +   \sum_{\Vc\in \binom{[\Ksf]}{\Ssf}:  \Vc \cap \Uc_1 \neq \emptyset} \left( a_{\Vc, j} \sum_{k_1\in \Vc \cap \Uc_1}  Z_{\Vc,k_1} \right) \\
&= \sum_{k\in \Uc_1} W_{k ,j} +   \sum_{\Vc\in \binom{[\Ksf]}{\Ssf} } \left( a_{\Vc, j} \sum_{k_1\in \Vc \cap \Uc_1}  Z_{\Vc,k_1} \right),
\ \forall j \in [\Usf],
\label{eq:received packets after 1st round}
\end{align}

where (<ref>) follows since $\Ssf=\Ksf-\Usf+1>\Ksf-|\Uc_1|$.
Hence, the server still needs to recover $\sum_{\Vc\in \binom{[\Ksf]}{\Ssf}  } \left( a_{\Vc, j} \sum_{k_1\in \Vc \cap \Uc_1}  Z_{\Vc,k_1} \right)$ for each $j \in [\Usf]$ in the next   round.  We can treat

\begin{align}
Z^{\Uc_1}_{\Vc}:= \sum_{k_1\in \Vc \cap \Uc_1}  Z_{\Vc,k_1} , \ \forall \Vc\in \binom{[\Ksf]}{\Ssf}, \label{eq:def of coded key}
\end{align}

as one coded key, which can be encoded by all users in $ \Vc \cap \Uc_1$ and  contains $\Lsf/\Usf$ uniform and i.i.d. symbols.
Thus  by the construction of the first round transmission, we only need to transmit linear combinations of coded keys in the second round, such that the server can recover $\sum_{\Vc\in \binom{[\Ksf]}{\Ssf}}   a_{\Vc, j}   Z^{\Uc_1}_{\Vc} $ for each $j \in [\Usf]$.

* In the second  round, we denote    the sets in $\binom{[\Ksf]}{\Ssf}$   by $\Sc(1),\ldots,\Sc\left(\binom{\Ksf}{\Ssf}\right)$, and for each $k\in[\Ksf]$ denote   the sets  in $\binom{[\Ksf]\setminus\{k\}}{\Ssf}$   by
Thus the server should recover

\begin{align}
\begin{bmatrix}
F_1  \\
\vdots\\
\end{bmatrix}
= \left[ \av_{\Sc(1)}, \ldots, \av_{\Sc\left(\binom{\Ksf}{\Ssf}\right)} \right]
\begin{bmatrix}
Z^{\Uc_1}_{\Sc(1)} \\
\vdots\\
\end{bmatrix}, \label{eq:second round recover}
\end{align}

where each $F_{j}$, $j\in [\Usf]$, contains $\Lsf/\Usf$ symbols.

Note that each user $k\in \Uc_1$ cannot encode $Z^{\Uc_1}_{\Vc}$ where $\Vc\in \binom{[\Ksf]\setminus\{k\}}{\Ssf}$.
If the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc\in \binom{[\Ksf]}{\Ssf}$ satisfy the constraints that

\begin{align}
\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right] \ \text{ has rank equal to $\Usf-1$}, \ \forall k\in[\Ksf],
\label{eq:constraint of a for null space}
\end{align}

then the matrix $\left[ \av_{\overline{\Sc}_{k}(1)},  \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right] $ contains exactly one linearly independent left null space vector.  To achieve (<ref>), we will propose some interference alignment techniques to align the $\Usf$-dimensional  vectors of
the $\binom{\Ksf-1}{\Ssf}$  unknown keys   to a linear space spanned by    $\Usf-1$ linearly independent vectors.

we can let each user $k\in \Uc_1$ transmit

\begin{align}
Y^{\Uc_1}_{k} =    \sv_{k}    \begin{bmatrix}
F_1  \\
\vdots\\
\end{bmatrix}   ,
\label{eq:transmission of Y_k}
\end{align}

where $\sv_{k}$  represents the left null space vector of $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$. By construction,  in $Y^{\Uc_1}_{k} $ the coefficients of the coded keys which cannot be encoded by user $k$ are $0$.
Note that   $Y^{\Uc_1}_{k}$ contains $\Lsf/\Usf$ symbols,  which leads to $\Rsf_2=1/\Usf$.

For the decodability, from any set of surviving users after the second round  $\Uc_2 \subseteq \Uc_1$ where $|\Uc_2| \geq \Usf$,  we should recover

from the second round transmission; i.e.,
we   aim to have

\begin{align}
H\left(     \sum_{\Vc\in \binom{[\Ksf]}{\Ssf}}   a_{\Vc, j} Z^{\Uc_1}_{\Vc}  \Big|  \left( Y^{\Uc_1}_{k}: k\in \Uc_2 \right)  \right) =0, \ \forall j\in [\Usf]. \label{eq:decodability constraint}
\end{align}

\begin{align}
\text{any $\Usf$ vectors in $\{ \sv_{k}: k\in \Uc_1\} $ are linearly independent}. \label{eq:decodability constraint}
\end{align}

Thus from (<ref>) and (<ref>), the server can recover $F_1,\ldots,F_{\Usf}$ and then recover $ \sum_{k\in \Uc_1} W_{k ,j} $ for all $j \in [\Usf]$; thus it can recover $ \sum_{k\in \Uc_1} W_{k } $.

In addition, for the security constraint,  by construction we have

\begin{align}
H\left(     Y^{\Uc_1}_{k}: k\in \Uc_1  \right) = \Lsf,
\label{eq:constraint on Yk}
\end{align}

which follows since each $Y^{\Uc_1}_{k}$  where $k\in \Uc_1$ is  in the linear space spanned by $F_{1},\ldots,F_{\Usf}$, where each $F_{j}$, $j\in[\Usf]$, contains $\Lsf/\Usf$ symbols.
Intuitively, from $(X_k:k\in [\Ksf])$, the server cannot get any information about $W_1,\ldots,W_{\Ksf}$. Together with $ (Y^{\Uc_1}_{k}: k\in \Uc_1 )$ whose entropy is $\Lsf$, the server can at most get $\Lsf$ symbols information about  $W_1,\ldots,W_{\Ksf}$, which are exactly the symbols in $ \sum_{k\in \Uc_1} W_{k } $.  Hence, the proposed scheme is secure. The rigorous  proof on the security constraint in (<ref>) can be found in Appendix <ref>.

We conclude that the achieved rates are $(\Rsf_1,\Rsf_2)=( 1, 1/\Usf)$, coinciding with Theorem <ref>.

For what said above, it is apparent that the key challenge  in the proposed scheme is to design  the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc\in \binom{[\Ksf]}{\Ssf}$, such that the constraints in (<ref>), (<ref>), and (<ref>) are satisfied. As showed above, if such constraints are satisfied, the proposed scheme is decodable and secure.

Another important observation is that, the   constraints in (<ref>), (<ref>) are not related to   $\Uc_1$; in addition, if  the constraint in (<ref>) is satisfied for the case $\Uc_1=[\Ksf]$, this constraint also holds for any other    $\Uc_1$. Hence, we only need to consider the case  $\Uc_1=[\Ksf]$ to design the   $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc\in \binom{[\Ksf]}{\Ssf}$.

In the following,
we will further divide the considered  case $\Usf<\Ksf$ into three regimes:
a) $\Usf\leq  \Ksf-\Usf+1$; b) $\Usf> \Ksf-\Usf+1$ and $\Usf=\Ksf-1$; c) $\Usf> \Ksf-\Usf+1$ and $\Usf<\Ksf-1$.  We  will propose our scheme  for each regime which achieves the capacity region in Theorem <ref>.
In each regime, we propose a different selection on the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc\in \binom{[\Ksf]}{\Ssf}$, such that the constraints in (<ref>), (<ref>), and (<ref>) are satisfied.

§.§ Case $\Usf\leq \Ksf-\Usf+1$

We first illustrate the proposed scheme for this case through an example.
[$(\Ksf,\Usf, \Ssf))=(3,2,2)$]

Consider  the  $(\Ksf,\Usf,\Ssf)=(3,2,2)$ information theoretic secure aggregation problem with uncoded groupwise keys. While illustrating the proposed
scheme through examples, we  perform a field extension  on the input vectors to a large
enough prime field $\mathbb{F}_{\qsf}$.  In general this assumption on prime field
size is not necessary in our proposed scheme.

For each $\Vc\in \binom{[3]}{2}$,  we generate a key $Z_{\Vc}=(Z_{\Vc,k}:k\in \Vc)$ shared by users in $\Vc$, where each $Z_{\Vc,k}$ contains $\Lsf/2$  uniform and i.i.d. symbols over $\mathbb{F}_{\qsf}$.

We also divide each input vector $W_k$ where $k\in [3]$ into two pieces, $W_{k}=(W_{k,1},W_{k,2})$, where each piece contains $\Lsf/2$ uniform and i.i.d. symbols over $\mathbb{F}_{\qsf}$.

First round.
In the first round, user $1$ transmits $X_1=(X_{1,1},X_{1,2})$, where

\begin{align*}
&X_{1,1}=W_{1,1}+Z_{\{1,2\},1} +Z_{\{1,3\},1};\\
&X_{1,2}=W_{1,2}+Z_{\{1,2\},1}+2 Z_{\{1,3\},1}.
\end{align*}

User $2$ transmits $X_2=(X_{2,1},X_{2,2})$, where

\begin{align*}
&X_{2,2}=W_{2,2}+Z_{\{1,2\},2}+3 Z_{\{2,3\},2}.
\end{align*}

User $3$ transmits  $X_3=(X_{3,1},X_{3,2})$, where

\begin{align*}
\end{align*}

In other words, we let

\begin{align}
\av_{\{1,2\}}=[1,1]^{\text{T}}, \ \av_{\{1,3\}}=[1,2]^{\text{T}}, \ \av_{\{2,3\}}=[1,3]^{\text{T}}.
\label{eq:choice of a for example 1}
\end{align}

In $X_1$, the coefficient matrix of the keys $(Z_{\{1,2\},1},Z_{\{1,3\},1})$ is $\begin{bmatrix}
1&1  \\
\end{bmatrix}$, which
has rank equal to $2$ (recall that the field size is large enough), i.e., the constraint in (<ref>) is satisfied for user $1$. Thus  $W_1$ is perfectly protected by $(Z_{\{1,2\},1},Z_{\{1,3\},1})$ from $X_1$.
Similarly, the constraints in (<ref>) are satisfied for user $2,3$.

Second round.
In the second round, we only need to consider the   case where $\Uc_1=[3]$, as explained before.
Since $\Uc_1=[3]$, the server should recover $W_1+W_2+W_3$.
By the definition of coded key in (<ref>), we define  the coded keys

\begin{align*}
\end{align*}

each of which contains $\Lsf/2$ uniform and i.i.d. symbols.
From the transmission of the first round, the server can recover

\begin{align*}
&X_{1,1}+X_{2,1}+X_{3,1}= W_{1,1}+W_{2,1}+W_{3,1} +Z^{[3]}_{\{1,2\}}+ Z^{[3]}_{\{1,3\}}+Z^{[3]}_{\{2,3\}};\\
\end{align*}

Hence, the server should further recover

\begin{align}
\begin{bmatrix}
F_1  \\
\end{bmatrix}  =
\av_{\{1,2\}} , \av_{\{1,3\}}, \av_{\{2,3\}}
\begin{bmatrix}
Z^{[3]}_{\{1,2\}}  \\
\end{bmatrix} =
\begin{bmatrix}
1&1&1  \\
\end{bmatrix}
\begin{bmatrix}
Z^{[3]}_{\{1,2\}}  \\
\end{bmatrix}
\label{eq:ex1 second round task}
\end{align}

totally $\Lsf$ symbols
in the second round. Since $|\Uc_2|\geq \Ssf=2$, the second round transmission should be designed such that from any   two of $Y^{[3]}_1, Y^{[3]}_2, Y^{[3]}_3$, we can recover (<ref>).

For user $1$ who   cannot encode $Z^{[3]}_{\{2,3\}} $,  the   sub-matrix $[\av_{\{2,3\}}]$   has rank equal to $1$; thus the constraint in (<ref>) is
satisfied for user $1$. The left
null space of $[\av_{\{2,3\}}]$ contains exactly one linearly independent $2$-dimensional vector, which
could be $[3,-1]$. Thus we let user $1$ transmit

\begin{align}
Y^{[3]}_1= [3, -1]     \begin{bmatrix}
F_1  \\
\end{bmatrix} =3F_1-F_2,
\end{align}

in which the coefficient of  $Z^{[3]}_{\{2,3\}}$ is $0$.
Similarly, we  let user $2$ transmit

\begin{align}
Y^{[3]}_2= [2, -1]     \begin{bmatrix}
F_1  \\
\end{bmatrix}=2F_1-F_2 ,
\end{align}

in which the coefficient of  $Z^{[3]}_{\{1,3\}}$ is $0$,
and let user $3$ transmit

\begin{align}
Y^{[3]}_3= [1, -1]     \begin{bmatrix}
F_1  \\
\end{bmatrix} =F_1-F_2,
\end{align}

in which the coefficient of  $Z^{[3]}_{\{1,2\}}$ is $0$.
The constraints in (<ref>)  are also satisfied for users $2,3$.

By construction,  any two of $Y^{[3]}_1,Y^{[3]}_2,Y^{[3]}_3$ are linearly independent. Hence, for any $\Uc_2\subseteq [3]$ where $|\Uc_2|\geq 2$, the server can recover $F_1$ and $F_2$;  thus the constraint in (<ref>) is satisfied.
Hence,  from the two round transmissions, the server can  recover $W_1+W_2+W_3$.

Since the constraints   in (<ref>), (<ref>), and (<ref>) are satisfied,
by the security proof in Appendix <ref>, the scheme is secure  for the case $\Uc_1=[3]$.

Let us then   consider the   case where $\Uc_1=[2]$.
Since $\Uc_1=[2]$, the server should recover $W_1+W_2$. By the definition of coded key in (<ref>), we define  the coded keys

\begin{align*}
\end{align*}

each of which contains $\Lsf/2$ uniform and i.i.d. symbols.
From the transmission of the first round, the server can recover

\begin{align*}
&X_{1,1}+X_{2,1}= W_{1,1}+W_{2,1}+W_{3,1} +Z^{[3]}_{\{1,2\}}+ Z^{[3]}_{\{1,3\}}+Z^{[3]}_{\{2,3\}};\\
\end{align*}

Hence, the server should further recover

\begin{align}
\begin{bmatrix}
F_1  \\
\end{bmatrix}  =
\begin{bmatrix}
1&1 &1  \\
1&2  &3
\end{bmatrix}
\begin{bmatrix}
Z^{[2]}_{\{1,2\}}  \\
\end{bmatrix}   :=  \mathbf{F}
\begin{bmatrix}
Z^{[2]}_{\{1,2\}}  \\
\end{bmatrix},
\label{eq:ex1 second round task U1[2]}
\end{align}

totally $\Lsf$ symbols.
After the above definition, the construction of the second round transmissions of users $1,2$ is exactly the same as that in the case where $\Uc_1=[3]$. More precisely,
user $1$ transmits
\begin{align}Y^{[2]}_1= [3, -1]     \begin{bmatrix}
F_1  \\
\end{bmatrix},
\end{align}

and user $2$ transmits
\begin{align}
Y^{[2]}_2= [2, -1]     \begin{bmatrix}
F_1  \\
\end{bmatrix}.
\end{align}

Since $Y^{[2]}_1$ and $Y^{[2]}_2$ are linearly independent, the server can recover $F_1$ and $F_2$ from any two of  $Y^{[2]}_1,Y^{[2]}_2$. Thus the constraint in (<ref>) is satisfied.  Since  we have already showed that the constraints   in (<ref>), (<ref>) are satisfied,

the   proposed scheme is decodable and secure for this case.

The other cases where $\Uc_1\in \binom{[3]}{2}$ are similar to the case $\Uc_1=[2]$.
In conclusion, in the first round, each user transmits $\Lsf$ symbols. In the second round, each user in $\Uc_1$ transmits $\Lsf/2$ symbols. Hence,
the achieved rates are $(\Rsf_1,\Rsf_2)=( 1, 1/2)$, coinciding with Theorem <ref>.

We are now ready to generalize the proposed scheme in Example <ref> to the case where $\Usf\leq   \Ksf-\Usf+1$.
For the sake of simplicity, we directly describe the choice of the $\Usf$-dimensional vectors  and show that such choice satisfies the constraints in (<ref>), (<ref>), and (<ref>).

We use a cyclic key assignment, by
defining a collection of cyclic sets

\begin{align}
\Cc:= \big\{ \{i,<i+1>_{\Ksf}, \ldots, <i+\Ksf-\Usf>_{\Ksf} \} : i\in [\Ksf]  \big\}.
\label{eq:cyclic key set}
\end{align}

For the ease of notation, we sort the sets in $\Cc$   in an order  where the $i^{\text{th}}$ set denoted by $\Cc(i)$ is $\{i,<i+1>_{\Ksf}, \ldots, <i+\Ksf-\Usf>_{\Ksf} \}$, for each $i\in [\Ksf]$.[For example, when $\Ksf=4$ and $\Usf=2$, we have $\Cc(1)=\{1,2,3\}$, $\Cc(2)=\{2,3,4\}$, $\Cc(3)=\{1,3,4\}$, and $\Cc(4)=\{1,2,4\}$.]
It can be seen that each of the sets $\Cc(k), \Cc(<k-1>_{\Ksf}), \ldots, \Cc(<k-\Ksf+\Usf>_{\Ksf})$ contains  $k$, for each $k\in [\Ksf]$.

We select the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc \in \binom{[\Ksf]}{\Ssf}$ as follows:

* if $\Vc \in \Cc$, we let $\av_{\Vc}$ be uniform and i.i.d. over $\mathbb{F}^{\Usf}_{\qsf}$;

* otherwise, we    let each element in $\av_{\Vc}$ be $0$.

Next we will show that the above choice of these   $\Usf$-dimensional vectors  satisfies the constraints in (<ref>), (<ref>), and (<ref>), with high probability.

we generate a key  $Z_{\Vc}=(Z_{\Vc,k}:k\in \Vc)$, where each $Z_{\Vc,k}$ contains $\Lsf/\Usf$ uniform and i.i.d. symbols on $\mathbb{F}_{\qsf}$.
For the ease of notation, we sort the sets in $\Cc$   in a lexicographic order, where the $i^{\text{th}}$ set denoted by $\Cc(i)$ is $\{i,<i+1>_{\Ksf}, \ldots, <i+\Ksf-\Usf>_{\Ksf} \}$, for each $i\in [\Ksf]$.
It can be seen that each of the sets $\Cc(k), \Cc(<k-1>_{[\Ksf]}), \ldots, \Cc(<k-\Ksf+\Usf>_{[\Ksf]})$ contains  $k$.
We also divide each input vector $W_k$ where $k\in [\Ksf]$ into $\Usf$ pieces, $W_{k}=(W_{k,j}:j\in [\Usf])$, where each piece contains $\Lsf/\Usf$ uniform and i.i.d.  symbols on $\mathbb{F}_{\qsf}$.

First round.
In the first round,   we let each user $k\in [\Ksf]$  transmit   $X_k=(X_{k,j}:j\in [\Usf])$, where

\begin{align}
X_{k,j} = W_{k,j} + \sum_{i\in \{k,<k-1>_{[\Ksf]},\ldots,<k-\Ksf+\Usf>_{[\Ksf]}\}} a_{\Cc(i), j} Z_{\Cc(i),k}  , \ \forall j \in [\Usf],
\label{eq:Xkj first case}
\end{align}

and we choose each $a_{\Cc(i), j}$ uniformly and i.i.d. over $\mathbb{F}_{\qsf}$. Recall that $\av_{\Vc}:= [a_{\Vc, 1},\ldots,a_{\Vc, \Usf}]^{\text{\rm T}}$.[In other words, we select the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc \in \binom{[\Ksf]}{\Ssf}$ as follows:
if $\Vc \in \Cc$, we let $\av_{\Vc}$ be uniformly and i.i.d. over $\mathbb{F}^{\Usf}_{\qsf}$; otherwise, we    let each element in $\av_{\Vc}$ be $0$.

*Constraints in (<ref>)
Since $\qsf$ is large enough and $\Usf\leq  \Ksf-\Usf+1$, for each $k\in [\Ksf]$ the   matrix

$$\left[\av_{\Cc(k)},\av_{\Cc(<k-1>_{\Ksf})}, \ldots, \av_{\Cc(<k-\Ksf+\Usf>_{\Ksf})} \right]$$
whose dimension is   $\Usf \times (\Ksf-\Usf+1)$,
has rank equal to $\Usf$ with high probability;	thus the constraints in (<ref>) are satisfied with high probability.

*Constraints in (<ref>)

Among the sets in $\Cc$,
each of the sets $ \Cc(<k+1>_{\Ksf}) , \Cc(<k+2>_{\Ksf}) ,  \ldots,  \Cc(<k+\Usf-1>_{\Ksf}) $ does not contain  $k$, where $k\in [\Ksf]$.
It can be seen that
$ [\av_{\Cc(<k+1>_{\Ksf})},\av_{\Cc(<k+2>_{\Ksf})},  \ldots, \av_{\Cc(<k+\Usf-1>_{\Ksf})}]$ has    dimension equal to $\Usf \times (\Usf-1)$, and that its elements are  uniformly and i.i.d. over $\mathbb{F}_{\qsf}$. So the left null space contains
$\Usf-(\Usf-1)=1$ linearly independent  $\Usf$-dimensional vector with high probability, and we let $\sv_k$ be this vector.
Hence, the constraints in (<ref>) are satisfied with high probability.

*Constraint in (<ref>)

Recall that we only need to consider the case where  $\Uc_1=[\Ksf]$.
In the  second round transmission, the server should  recover  $\Usf$ linear combinations of coded keys,

\begin{bmatrix}
F_1  \\
\vdots\\
\end{bmatrix}
= \left[ \av_{\Cc(1)}, \ldots, \av_{\Cc(\Ksf)} \right]
\begin{bmatrix}
Z^{[\Ksf]}_{\Cc(1)} \\
\vdots\\
\end{bmatrix},

from the answers of any $\Usf$ of the $\Ksf$ users, each of whom knows $\Ksf-\Usf+1$ coded keys in a cyclic way.
This problem is   equivalent to    the distributed linearly separable computation problem in <cit.>, where we aim to compute $\Usf$ linear combinations of $\Ksf$ messages (whose coefficients are uniformly and i.i.d. over $\mathbb{F}_{\qsf}$) through $\Ksf$ distributed computing nodes, each of which can stores $\Ksf-\Usf+1$ messages, such that from the answers of any $\Usf$ nodes we can recover the computing task.
From <cit.>, we have the following lemma.

For any set $\Ac\in \binom{[\Ksf]}{\Usf}$, the vectors
\sv_{n} , n\in \Ac,
are linearly independent with high probability.

Thus by Lemma <ref>,  the   constraint in (<ref>) is satisfied with high probability.

From the first round,  the server obtains

\begin{align}
\sum_{k\in \Uc_1} X_{k,j} &= \sum_{k\in \Uc_1} W_{k ,j} +   \sum_{\Vc \in \Cc:   \Vc \cap \Uc_1 \neq \emptyset}
\left( a_{\Vc, j} \underbrace{ \sum_{k_1\in \Vc \cap \Uc_1}  Z_{\Vc,k_1}}_{\text{$:=Z^{\Uc_1}_{\Vc}$ is a coded key known by users in $\Vc$}}
\right) \\
&= \sum_{k\in \Uc_1} W_{k ,j} +   \sum_{\Vc \in \Cc }
a_{\Vc, j} Z^{\Uc_1}_{\Vc} ,   \ \forall j\in [\Usf],
\label{eq:case 1 sum of Xkj}
\end{align}

where (<ref>) follows since  $\Ssf=\Ksf-\Usf+1>\Ksf-|\Uc_1|$.
Hence, it should further recover $  \sum_{\Vc \in \Cc}  a_{\Vc, j} Z^{\Uc_1}_{\Vc} $ for  $j \in [\Usf]$ from the second round; i.e., the server should recover

\begin{align}
\begin{bmatrix}
F_1  \\
\vdots \\
\end{bmatrix} =
\av_{\Cc(1)}, \ldots, \av_{\Cc(\Ksf)}
\begin{bmatrix}
Z^{\Uc_1}_{\Cc(1)}  \\
\vdots \\
\end{bmatrix}.
\label{eq:first case second round task}
\end{align}

Note that each user $k\in \Uc_1$ cannot encode $Z^{\Uc_1}_{\Cc(<k+1>_{\Ksf})}, Z^{\Uc_1}_{\Cc(<k+2>_{\Ksf})}, \ldots, Z^{\Uc_1}_{\Cc(<k+\Usf-1>_{\Ksf})}$, totally $\Usf-1$ coded keys.
We then use   the distributed  linearly separable computation scheme with cyclic assignment in <cit.> to generate the second round transmissions on $
Z^{\Uc_1}_{\Cc(1)}, \ldots,Z^{\Uc_1}_{\Cc(\Ksf)}$. More precisely, each user $k\in \Uc_1$ transmits

\begin{align}
Y^{\Uc_1}_{k}= \sv_{k} \begin{bmatrix}
F_1  \\
\vdots \\
\end{bmatrix},
\end{align}

where $\sv_k$ is a left  null space vector   of   $ [\av_{\Cc(<k+1>_{\Ksf})},\av_{\Cc(<k+2>_{\Ksf})}, \ldots, \av_{\Cc(<k+\Usf-1>_{\Ksf})}]$,  which  corresponds to the $\Usf-1$ coded keys which cannot be encoded by user $k$. Note that  $ [\av_{\Cc(<k+1>_{\Ksf})},\av_{\Cc(<k+2>_{\Ksf})},$ $ \ldots, \av_{\Cc(<k+\Usf-1>_{\Ksf})}]$ has    dimension equal to $\Usf \times (\Usf-1)$, and that its elements are uniformly and i.i.d. over $\mathbb{F}_{\qsf}$. So the left null space contains
$\Usf-(\Usf-1)=1$ linearly independent  $\Usf$-dimensional vector, and we let $\sv_k$ be this vector.
Hence, the constraints in (<ref>) are satisfied.

It was proved in <cit.>  that  for any set $\Ac\in \binom{[\Ksf]}{\Usf}$, the vectors
\sv_{n} , n\in \Ac,
are linearly independent with high probability. Hence,
from the answers of any $\Usf$ users, the server can recover $F_1,\ldots, F_{\Usf}$.
Thus the constraints in (<ref>) are satisfied.

In conclusion, all constraints in (<ref>), (<ref>), and (<ref>) are satisfied with high probability.  Hence, there must exist a choice of $\left[\av_{\Cc(1)},  \ldots, \av_{\Cc(\Ksf)} \right]$ satisfying those constraints.
the proposed scheme is decodable and secure.
In this case, we need the keys   $Z_{\Vc}$ where $\Vc \in \Cc$, totally $\Ksf$ keys each of which is shared by $\Ssf$ users.

§.§ Case $\Usf> \Ksf-\Usf+1$ and $\Usf=\Ksf-1$

When $\Usf>\Ssf$, the proposed secure aggregation scheme with cyclic assignment does not work. This is because,
among $\Cc$, the number of sets containing each $k\in [\Ksf]$ is $\Ksf-\Usf+1<\Usf$, which are  $\Cc(k), \Cc(<k-1>_{\Ksf})  ,\ldots,  \Cc(<k-\Ksf+\Usf>_{\Ksf})  $.

Hence,  the    coefficient matrix of keys in $X_k$,
$\left[\av_{\Cc(k)},\av_{\Cc(<k-1>_{\Ksf})}, \ldots, \av_{\Cc(<k-\Ksf+\Usf>_{\Ksf})} \right]$, is with dimension $\Usf\times (\Ksf-\Usf+1)$ and with rank strictly less than $\Usf$. Thus the constraint in (<ref>) is not satisfied. In other words,   $W_k$ is not perfectly protected from $X_{k}$.

In this subsection, we present our proposed secure aggregation scheme for the case where $\Usf> \Ksf-\Usf+1$ and $\Usf=\Ksf-1$. We first illustrate the main idea through the following example.
[$(\Ksf,\Usf, \Ssf))=(4,3,2)$]

Consider  the  $(\Ksf,\Usf,\Ssf)=(4,3,2)$ information theoretic secure aggregation problem with uncoded groupwise keys.
For each $\Vc\in \binom{[4]}{2}$,  we generate a key $Z_{\Vc}=(Z_{\Vc,k}:k\in \Vc)$ shared by users in $\Vc$, where each $Z_{\Vc,k}$ contains $\Lsf/3$ uniform and i.i.d. symbols over $\mathbb{F}_{\qsf}$.

We also divide each input vector $W_k$ where $k\in [4]$ into three pieces, $W_{k}=(W_{k,1},W_{k,2},W_{k,3})$, where each piece contains $\Lsf/3$ uniform and i.i.d.  symbols over $\mathbb{F}_{\qsf}$.

In the first round, each user $k\in [4]$ transmits

\begin{align}
X_{k,j} = W_{k,j} + \sum_{\Vc\in \binom{[4]}{2}: k \in \Vc} a_{\Vc, j} Z_{\Vc,k}  , \ \forall j \in [3].
\end{align}

Now we select the $3$-dimensional vectors $\av_{\{1,2\}}$, $\av_{\{1,3\}}$, $\av_{\{1,4\}}$, $\av_{\{2,3\}}$, $\av_{\{2,4\}}$, and $\av_{\{3,4\}}$ as follows,

\begin{align}
&\av_{\{1,2\}} = [1,0,0]^{\text{T}}, \ \av_{\{1,3\}} = [0,1,0]^{\text{T}},  \ \av_{\{1,4\}} = [0,0,1]^{\text{T}},\\
&\av_{\{2,3\}}=\av_{\{1,2\}}-\av_{\{1,3\}}=[1,-1,0]^{\text{T}}, \ \av_{\{2,4\}}=\av_{\{1,2\}}-\av_{\{1,4\}}=[1,0,-1]^{\text{T}}, \\
\end{align}

We next show that by the above choice the constraints in (<ref>), (<ref>), and (<ref>) are satisfied.

For user $1$, the   matrix $[\av_{\{1,2\}},\av_{\{1,3\}},\av_{\{1,4\}}]=\mathbf{I}_3$ has rank $3$, where we recall that $\mathbf{I}_3$ represents the identity matrix with dimension $3\times 3$. Hence, the constraint in (<ref>) is satisfied for user $1$. Thus $W_1$ is perfectly protected by $(Z_{\{1,2\},1},  , Z_{\{1,3\},1}, Z_{\{1,4\},1} )$ from $X_1$.
For user $2$, the     matrix $[\av_{\{1,2\}},\av_{\{2,3\}},\av_{\{2,4\}}]=\begin{bmatrix}
1&1&1 \\
0&-1&0 \\
\end{bmatrix}$ has rank $3$. Hence, the constraint in (<ref>) is satisfied for user $2$. Thus $W_2$ is perfectly protected by $(Z_{\{1,2\},2},  , Z_{\{2,3\},2}, Z_{\{2,4\},2} )$ from $X_2$.
the   constraints in (<ref>)  are also satisfied for users $3,4$.

In the second round,  we only need to consider the case $\Uc_1=[4]$, where the server should recover $W_{1}+\cdots+W_{4}$.
By defining   the coded keys  as in (<ref>),
the server needs to further recover

\begin{align}
\begin{bmatrix}
F_1 \\
F_2 \\
\end{bmatrix}=[\av_{\{1,2\}}, \av_{\{1,3\}}, \av_{\{1,4\}}, \av_{\{2,3\}},\av_{\{2,4\}},\av_{\{3,4\}}] \begin{bmatrix}
Z^{[4]}_{\{1,2\}} \\
Z^{[4]}_{\{1,3\}} \\
Z^{[4]}_{\{2,3\}} \\
Z^{[4]}_{\{2,4\}} \\
\end{bmatrix}
\begin{bmatrix}
\end{bmatrix}
\begin{bmatrix}
Z^{[4]}_{\{1,2\}} \\
Z^{[4]}_{\{1,3\}} \\
Z^{[4]}_{\{2,3\}} \\
Z^{[4]}_{\{2,4\}} \\
\end{bmatrix}.
\end{align}

For user $1$ who cannot encode $Z^{[4]}_{\{2,3\}},Z^{[4]}_{\{2,4\}},Z^{[4]}_{\{3,4\}}$, it can be seen that the sub-matrix
$[\av_{\{2,3\}},\av_{\{2,4\}},\av_{\{3,4\}}]$ has rank $2$, equal to the rank of $ [\av_{\{2,3\}},\av_{\{2,4\}}]$,  since $\av_{\{2,3\}}-\av_{\{2,4\}}=-\av_{\{3,4\}}$;[In other words,
we align the three vectors $\av_{\{2,3\}},\av_{\{2,4\}},\av_{\{3,4\}}$ into the linear space spanned by $\av_{\{2,3\}}$ and $\av_{\{2,4\}}$.]
thus the constraint in (<ref>) is satisfied for user $1$.
Hence, the left null     space of $[\av_{\{2,3\}},\av_{\{2,4\}},\av_{\{3,4\}}]$ contains exactly one linearly independent $3$-dimensional vector, which could be $[1,1,1]$.
Thus we let user $1$ compute

\begin{align}
Y^{[4]}_{1} = [1,1,1]\begin{bmatrix}
F_1 \\
F_2 \\
\end{bmatrix}=F_1+F_2+F_3.
\end{align}

For user $2$,  who cannot encode $Z^{[4]}_{\{1,3\}},Z^{[4]}_{\{1,4\}},Z^{[4]}_{\{3,4\}}$, it can be seen that the sub-matrix
$[\av_{\{1,3\}},\av_{\{1,4\}},\av_{\{3,4\}}]$ has rank $2$, equal to the rank of $[\av_{\{1,3\}},\av_{\{1,4\}}]$,
$\av_{\{3,4\}}=\av_{\{1,3\}}-\av_{\{1,4\}}$; thus the constraint in (<ref>) is satisfied for user $2$.
Hence, the left null     space of $[\av_{\{1,3\}},\av_{\{1,4\}},\av_{\{3,4\}}]$ contains exactly one linearly independent $3$-dimensional vector, which could be $[1,0,0]$.
Thus we let user $2$ compute

\begin{align}
Y^{[4]}_{2} = [1,0,0]\begin{bmatrix}
F_1 \\
F_2 \\
\end{bmatrix}=F_1.
\end{align}

the constraints in (<ref>) are satisfied for users $3,4$; thus
we let user $3$ compute

\begin{align}
Y^{[4]}_{3} = [0,1,0]\begin{bmatrix}
F_1 \\
F_2 \\
\end{bmatrix}=F_2,
\end{align}

and let user $4$ compute

\begin{align}
Y^{[4]}_{4} = [0,0,1]\begin{bmatrix}
F_1 \\
F_2 \\
\end{bmatrix}=F_3.
\end{align}

It can be seen that any $3$ of  $Y^{[4]}_{1},Y^{[4]}_{2},Y^{[4]}_{3},Y^{[4]}_{4}$ are linearly independent; thus the constraint  in (<ref>) is satisfied.
Hence, for any $\Uc_2\in \binom{[4]}{3}$, the server can recover $F_1,F_2,F_3$ from the second round. Thus from the two round transmissions, the server can recover $W_1+\cdots+W_4$.

In addition, all   $Y^{[4]}_{1},Y^{[4]}_{2},Y^{[4]}_{3},Y^{[4]}_{4}$  are in the linear space spanned by $F_1,F_2,F_3$.
As explained in Remark <ref>, the scheme is secure for the case $\Uc_1=[4]$.

Since the constraints   in (<ref>), (<ref>), and (<ref>) are satisfied,
by the security proof in Appendix <ref>, the scheme is secure  for the case $\Uc_1=[4]$.

When $\Uc_1=[3]$,  by defining

\begin{align}
\begin{bmatrix}
F_1 \\
F_2 \\
\end{bmatrix}=[\av_{\{1,2\}}, \av_{\{1,3\}}, \av_{\{1,4\}}, \av_{\{2,3\}},\av_{\{2,4\}},\av_{\{3,4\}}] \begin{bmatrix}
Z^{[3]}_{\{1,2\}} \\
Z^{[3]}_{\{1,3\}} \\
Z^{[3]}_{\{2,3\}} \\
Z^{[3]}_{\{2,4\}} \\
\end{bmatrix},
\end{align}

we let user $1$ compute  $F_1+F_2+F_3$, let user $2$ compute $F_1$, let user $3$ compute $F_2$. Hence, for any $\Uc_2\in \binom{[4]}{3}$, the server can recover $F_1,F_2,F_3$ from the second round. Thus from the two round transmissions, the server can recover $W_1+\cdots+W_3$, while the security constraint is satisfied.

The other cases where $\Uc_1 \in \binom{[4]}{3}$ are similar to the case $\Uc_1 = [3]$.
In conclusion, the
achieved rates of the proposed scheme are $(\Rsf_1 ,\Rsf_2 ) = (1,1/3)$, coinciding with Theorem <ref>.

We are now ready to generalize the proposed scheme in Example <ref> to the case where $\Usf> \Ksf-\Usf+1$ and $\Usf=\Ksf-1$. In this case, we have $\Ssf=2$.
As the previous case, we directly describe the choice of the $\Usf$-dimensional vectors  and show that such choice satisfies the constraints in (<ref>), (<ref>), and (<ref>).

Let us first consider the sets $\Vc \in \binom{[\Ksf]}{2}$ where $1\in \Vc$.  Each of such sets could be written as $\{1,j\}$, where $j\in [2:\Ksf-1]$.
We let

\begin{align}
\av_{\{1,j\}}=  \ev_{\Usf,j-1} , \ \forall j\in [2:\Ksf], \label{eq:a1j}
\end{align}

where   $\ev_{n,i}$ represents the vertical $n$-dimensional unit vector  whose entry in the  $i^{\text{th}} $ position is 1 and 0 elsewhere.
We then consider the sets $\Vc \in \binom{[2:\Ksf]}{2}$.  Each of such sets could be written as $\{i,j\}$, where $1<i<j\leq \Ksf$.
We let

\begin{align}
\av_{\{i,j\}}=  \av_{\{1,i\}}-  \av_{\{1,j\}}=\ev_{\Usf,i-1} -\ev_{\Usf,j-1} , \  \forall 1<i<j\leq \Ksf. \label{eq:aij}
\end{align}

Next we will show that the above choice of these   $\Usf$-dimensional vectors  satisfies the constraints in (<ref>), (<ref>), and (<ref>).

*Constraints in (<ref>)
For user $1$, the   matrix $\left[\av_{\{1,2\}},\av_{\{1,3\}}, \ldots, \av_{\{1,\Ksf\}} \right]$
is the identity matrix $\mathbf{I}_{\Ksf-1}=\mathbf{I}_{\Usf}$, whose rank is $\Usf$; thus the constraint  in (<ref>) is  satisfied for user $1$.
For each user $k\in [2:\Ksf]$, by a simple linear transform on the      matrix

\begin{align}
\left[\av_{\{1,k\}},\av_{\{2,k\}}, \ldots, \av_{\{k-1,k\}}, \av_{\{k,k+1\}},  \av_{\{k,k+2\}}, \ldots \av_{\{k,\Ksf\}} \right], \label{eq:coef matrix for k case 2}
\end{align}

we obtain the matrix

\begin{align*}
&   [\av_{\{1,k\}}+\av_{\{2,k\}}, \av_{\{1,k\}}+\av_{\{3,k\}},  \ldots, \av_{\{1,k\}}+\av_{\{k-1,k\}}, \av_{\{1,k\}},  \av_{\{1,k\}}-\av_{\{k,k+1\}},\av_{\{1,k\}}-\av_{\{k,k+2\}}, \nonumber\\& \ldots, \av_{\{1,k\}}-  \av_{\{k,\Ksf\}}   ] \\
& =  [\ev_{\Usf,1},\ev_{\Usf,2}, \ldots, \ev_{\Usf,k-2}, \ev_{\Usf,k-1},  \ev_{\Usf,k}, \ev_{\Usf,k+1}, \ldots, \ev_{\Usf,\Ksf-1}] ,
\end{align*}

is the identity matrix $\mathbf{I}_{\Ksf-1}=\mathbf{I}_{\Usf}$ with rank equal to $\Usf$, which is also full rank. Hence, the   matrix in (<ref>) is full rank, with   rank equal to $\Usf$; thus the constraint  in (<ref>) is  satisfied for user $k$.

*Constraints in (<ref>)
For user $1$, among the sets in $\Vc\in \binom{[\Ksf]}{2}$, the sets $\{2,3\},\{2,4\},\ldots,\{2,\Ksf\},$ $\{3,4\},\ldots,  \{\Ksf-1,\Ksf\}$ do not contain $1$. It can be seen that the following $\Ksf-2$ vectors,

\begin{align}
\av_{\{2,3\}}=\ev_{\Usf,1} -\ev_{\Usf,2}, \ \av_{\{2,4\}}=\ev_{\Usf,1} -\ev_{\Usf,3}, \ \ldots, \  \av_{\{2,\Ksf\}}=\ev_{\Usf,1} -\ev_{\Usf,\Ksf-1}, \label{eq:case 2 user 1 U-1 vec}
\end{align}

are linearly independent. In addition, for each set $\{i,j\}$ where $2<i<j\leq \Ksf$, we have
\av_{\{i,j\}} = \av_{\{2,j\}} - \av_{\{2,i\}}.
Hence, the matrix  $\left[ \av_{\overline{\Sc}_{1}(1)}, \ldots, \av_{\overline{\Sc}_{1}\left(\binom{\Ksf-1}{2}\right)}  \right]$

\begin{align}
[\av_{\{2,3\}},\av_{\{2,4\}},\ldots, \av_{\{2,\Ksf\}}, \av_{\{3,4\}},\ldots, \av_{\{\Ksf-1,\Ksf\}} ] \label{eq:case 2 unknown matrix user 1}
\end{align}

has rank equal to $\Ksf-2=\Usf-1$,[Recall that for each $k\in[\Ksf]$, the sets $\Vc\in \binom{[\Ksf]\setminus \{k\}}{\Ssf}$   are
$\overline{\Sc}_{k}(1),\ldots,\overline{\Sc}_k\left(\binom{\Ksf-1}{\Ssf}\right)$.] satisfying the constraint in (<ref>).

For each user $k\in [2:\Ksf]$, among the sets in $\Vc\in \binom{[\Ksf]}{2}$, the sets $\{1,2\},\{1,3\},\ldots,\{1,k-1\},\{1,k+1\},\ldots, \{1,\Ksf\}$ and the sets $\{i,j\}$ where $1<i<j\leq \Ksf$ and $i,j \neq k$,  do not contain $k$. It can be seen that the following  $\Ksf-2$ vectors,

\begin{align}
\av_{\{1,2\}}=\ev_{\Usf,1}  ,   \av_{\{1,3\}}=\ev_{\Usf,2} ,   \ldots,   \av_{\{1,k-1\}}=\ev_{\Usf,k-2} ,   \av_{\{1,k+1\}}=\ev_{\Usf,k}, \ldots ,\av_{\{1,\Ksf\}}=\ev_{\Usf,\Ksf-1},
\label{eq:case 2 user k U-1 vec}
\end{align}

are linearly independent. In addition, for each set $\{i,j\}$ where $1<i<j\leq \Ksf$ and $i,j \neq k$, we have
\av_{\{i,j\}} = \av_{\{1,i\}} - \av_{\{1,j\}}.
Hence, the matrix  $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{2}\right)}  \right]$
has rank equal to $\Ksf-2=\Usf-1$, satisfying the constraint in (<ref>).

*Constraint in (<ref>)
For user $1$, recall that $\sv_1$ is a  left null space vector of the matrix
$\left[ \av_{\overline{\Sc}_{1}(1)}, \ldots, \av_{\overline{\Sc}_{1}\left(\binom{\Ksf-1}{2}\right)}  \right]$, whose    rank is $\Usf-1$. The left null space of $\left[ \av_{\overline{\Sc}_{1}(1)}, \ldots, \av_{\overline{\Sc}_{1}\left(\binom{\Ksf-1}{2}\right)}  \right]$ is the same as that of
its column-wise sub-matrix $\left[ \av_{\{2,3\}},\av_{\{2,4\}},\ldots, \av_{\{2,\Ksf\}}  \right]$, whose rank is also $\Usf-1$ and dimension is $\Usf \times (\Usf-1)$.

\left[ \av_{\{2,3\}},\av_{\{2,4\}},\ldots, \av_{\{2,\Ksf\}}  \right]=\left[ \av_{\{2,3\}},\av_{\{2,4\}},\ldots, \av_{\{2,\Ksf\}}  \right]
=[\ev_{\Usf,1} -\ev_{\Usf,2}, \ev_{\Usf,1} -\ev_{\Usf,3}, \ldots,\ev_{\Usf,1} -\ev_{\Usf,\Ksf-1}]

contains exactly one linearly independent left null space vector, which could be (recall that  ${\bf 1}_{n}$    represents  the vertical $n$-dimensional   vector  whose elements are all $1$)

\begin{align}
\mathbf{1}_{\Usf}
=\sv_{1}.\label{eq:case 2 s1}
\end{align}

For each user $k\in [2:\Ksf]$, $\sv_k$ is a  left null space vector of the matrix
$\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{2}\right)}  \right]$, whose    rank is $\Usf-1$. The left null space of $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{2}\right)}  \right]$ is the same as that of
its column-wise sub-matrix $\left[ \av_{\{1,2\}}, \av_{\{1,3\}},\ldots, \av_{\{1,k-1\}} , \av_{\{1,k+1\}}, \ldots ,\av_{\{1,\Ksf\}}\right]$, whose rank is also $\Usf-1$ and dimension is $\Usf \times (\Usf-1)$. Since

\left[ \av_{\{1,2\}}, \av_{\{1,3\}},\ldots, \av_{\{1,k-1\}} , \av_{\{1,k+1\}}, \ldots ,\av_{\{1,\Ksf\}}\right]
=[\ev_{\Usf,1}  , \ev_{\Usf,2} , \ldots,\ev_{\Usf,k-2}, \ev_{\Usf,k},\ldots, \ev_{\Usf,\Ksf-1} ]

contains exactly one linearly independent left null space vector, which could be

\begin{align}
\ev_{\Usf,k-1}
=\sv_{k}.\label{eq:case 2 sk}
\end{align}

From (<ref>) and (<ref>), it can be seen that any $\Usf$ vectors of $\sv_1,\ldots,\sv_{\Ksf}$ are linearly independent; thus the constraint in (<ref>) is satisfied.

In conclusion, all constraints in (<ref>), (<ref>), and (<ref>) are satisfied; thus
the proposed scheme is decodable and secure.
In this case, we need the keys   $Z_{\Vc}$ where $\Vc \in \binom{[\Ksf]}{2}$, totally $\Ksf(\Ksf-1)/2$ keys each of which is shared by $2$ users.

§.§ Case $\Usf> \Ksf-\Usf+1$ and $\Usf<\Ksf-1$

Finally, we focus on the most  involved case where  $\Usf> \Ksf-\Usf+1$ and $\Usf<\Ksf-1$. In this case, we have $\Ssf >2$ and $2\Usf>\Ksf+1$.  Recall that
our objective is to  determine  the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc\in \binom{[\Ksf]}{\Ssf}$, such that  the constraints in (<ref>), (<ref>), and (<ref>) are satisfied.
We start by illustrating the main idea through an example.
[$(\Ksf,\Usf, \Ssf))=(6,4,3)$]

Consider  the  $(\Ksf,\Usf,\Ssf)=(6,4,3)$ information theoretic secure aggregation problem with uncoded groupwise keys.
We determine the $4$-dimensional vectors $\av_{\Vc}$ where $\Vc\in \binom{[6]}{3}$  as follows.

We first consider each $\av_{\Vc}$ where $[2] \subseteq \Vc$ and let  $\av_{\Vc}$ be a distinct vertical unit vector; i.e.,  we  let

\begin{align}
& \av_{[3]}= \ev_{4,1}, \  \av_{\{1,2,4\}}= \ev_{4,2}, \  \av_{\{1,2,5\}}= \ev_{4,3}, \  \av_{\{1,2,6\}}= \ev_{4,4}.\label{eq:ex 3 a[2]}
\end{align}

Define that $\Gc_1=\{[3],\{1,2,4\},\{1,2,5\},\{1,2,6\}\}$.

Then for each  $\av_{\Vc}$ where  $\Vc\in \binom{[6]}{3}\setminus \Gc_1$, we search for the   minimum   subset   of $\Gc_1$ the union of whose elements  is a super-set of $\Vc$; we denote this minimum   subset by $\Mc_{\Vc}$. For example, if $\Vc=\{1,3,4\}$, the   minimum   subset  of  $\Gc_1$ the union of whose elements  is a super-set of $\{1,3,4\}$,  is $\Mc_{\{1,3,4\}}=\{[3],\{1,2,4\}\}$, since $[3] \cup \{1,2,4\}=[4] \supseteq \{1,3,4\}$.  Then we let
$\av_{\Vc}$ be a linear combination of $\av_{\Vc_1}$ where $\Vc_1 \in \Mc_{\Vc}$; i.e., (assume that the sets in $\Mc_{\Vc}$ are $\Mc_{\Vc}(1),\ldots,\Mc_{\Vc}(|\Mc_{\Vc}|)$)

\begin{align}
\av_{\Vc} = b_{\Vc,1}\  \av_{\Mc_{\Vc}(1)} +\cdots + b_{\Vc,|\Mc_{\Vc}|} \ \av_{\Mc_{\Vc}(|\Mc_{\Vc}|)} ,\label{eq:ex3 form of a}
\end{align}

where $\bv_{\Vc}:=(b_{\Vc,1},\ldots,b_{\Vc,|\Mc_{\Vc}|})$ is an $|\Mc_{\Vc}|$-dimensional vector to be designed.

By this rule, we   determine the composition  of each  $\av_{\Vc}$  (i.e., the base vertical unit vectors which compose $\av_{\Vc}$) where  $ \Vc\in \binom{[\Ksf]}{\Ssf}$, as illustrated in Table <ref>.

Choice of $4$-dimensional vectors $\av_{\Vc}$ in the  $(\Ksf,\Usf,\Ssf)=(6,4,3)$ information theoretic secure aggregation problem.

$\av_{\Vc}$       Composition     Value     $\av_{\Vc}$       Composition     Value

$\av_{[3]} $       $\ev_{4,1}$      $\ev_{4,1}$       $\av_{\{2,3,4\}} $       $\ev_{4,1},\ev_{4,2}$      $\ev_{4,1}+8 \ev_{4,2}$ $\av_{\{1,2,4\}} $       $\ev_{4,2}$      $\ev_{4,2}$        $\av_{\{2,3,5\}} $       $\ev_{4,1},\ev_{4,3}$      $7\ev_{4,1}+8\ev_{4,3}$  $\av_{\{1,2,5\}} $       $\ev_{4,3}$      $\ev_{4,3}$           $\av_{\{2,3,6\}} $       $\ev_{4,1},\ev_{4,4}$        $3 \ev_{4,1}+4\ev_{4,4}$   $\av_{\{1,2,6\}} $       $\ev_{4,4}$      $\ev_{4,4}$        $\av_{\{2,4,5\}} $       $\ev_{4,2},\ev_{4,3}$      $\mathbf{0}_{4}$ $\av_{\{1,3,4\}} $       $\ev_{4,1},\ev_{4,2}$      $\ev_{4,1}+4\ev_{4,2}$        $\av_{\{2,4,6\}} $       $\ev_{4,2},\ev_{4,4}$      $\mathbf{0}_{4}$ $\av_{\{1,3,5\}} $       $\ev_{4,1},\ev_{4,3}$      $3\ev_{4,1} +4\ev_{4,3}$        $\av_{\{2,5,6\}} $       $\ev_{4,3},\ev_{4,4}$      $\mathbf{0}_{4}$ $\av_{\{1,3,6\}} $      $\ev_{4,1},\ev_{4,4}$     $ \ev_{4,1}+2\ev_{4,4}$         $ \av_{\{3,4,5\}} $       $\ev_{4,1},\ev_{4,2}, \ev_{4,3}$     $\ev_{4,1}+\ev_{4,2}+ \ev_{4,3}$  $\av_{\{1,4,5\}} $       $\ev_{4,2},\ev_{4,3}$     $\mathbf{0}_{4}$        $\av_{\{3,4,6\}} $       $\ev_{4,1},\ev_{4,2}, \ev_{4,4}$     $\ev_{4,1}+2\ev_{4,2}+ \ev_{4,4}$   $\av_{\{1,4,6\}} $      $\ev_{4,2},\ev_{4,4}$      $\mathbf{0}_{4}$       $\av_{\{3,5,6\}} $       $\ev_{4,1},\ev_{4,3}, \ev_{4,4}$       $\ev_{4,1}+2\ev_{4,3}-\ev_{4,4}$ $\av_{\{1,5,6\}} $      $\ev_{4,3},\ev_{4,4}$     $\mathbf{0}_{4}$        $\av_{\{4,5,6\}} $       $\ev_{4,2},\ev_{4,3}, \ev_{4,4}$      $\mathbf{0}_{4}$

Next we need to determine the coefficient vector   of the vertical base unit vectors    $\bv_{\Vc}$
for each $\Vc \in \binom{[6]}{3} \setminus \Gc_1$.

For each set     $\av_{\Vc}$ where $\{3,4\} \subseteq \Vc$, we choose each element of $\bv_{\Vc}$ uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.
For example, by choosing $\bv_{\{1,3,4\}}=[1,4]$, we have

\begin{align}
\av_{\{1,3,4\}}=\av_{[3]}+4\av_{\{1,2,4\}}= \ev_{4,1}+4\ev_{4,2}.\label{eq:ex3 a134}
\end{align}

Similarly, by choosing  $\bv_{\{2,3,4\}}=[1,8]$, $\bv_{\{3,4,5\}}=[1,1,1]$, and $\bv_{\{3,4,6\}}=[1,2,1]$, we have

\begin{align}
&\av_{\{2,3,4\}}=\av_{[3]}+8\av_{\{1,2,4\}}= \ev_{4,1}+8\ev_{4,2},\label{eq:ex3 a234} \\
& \av_{\{3,4,5\}}=\av_{[3]}+ \av_{\{1,2,4\}}+ \av_{\{1,2,5\}}= \ev_{4,1}+\ev_{4,2}+\ev_{4,3},\label{eq:ex3 a345} \\
& \av_{\{3,4,6\}}=\av_{[3]}+ 2\av_{\{1,2,4\}}+ \av_{\{1,2,6\}}= \ev_{4,1}+2\ev_{4,2}+\ev_{4,4}.\label{eq:ex3 a346}
\end{align}

Define that $\Gc_2=\{\{1,3,4\},\{2,3,4\},\{3,4,5\},\{3,4,6\}\}$.

We then need to choose $\bv_{\Vc}$ where

\Vc\in \binom{[6]}{3} \setminus (\Gc_1\cup \Gc_2)=\{\{1,3,5\},\{1,3,6\},\{1,4,5\},\{1,4,6\},\{1,5,6\}, \{2,3,5\},\{2,3,6\},\{2,4,5\},\{2,4,6\},\{2,5,6\},\{3,5,6\},\{4,5,6\}\}.

For each set $\Vc \in \binom{[6]}{3} \setminus (\Gc_1\cup \Gc_2)$ where $3\in \Vc$, we search for the   minimum   subset   of $\Gc_2$ the union of whose elements  is a super-set of $\Vc$; we denote this minimum   subset by $\Mc^{\prime}_{\Vc}$.
We let $\av_{\Vc}$ be a linear combination of $\av_{\Vc_2}$ where $\Vc_2 \in \Mc^{\prime}_{\Vc}$.
For example, if $\Vc=\{1,3,5\}$, the   minimum   subset  of  $\Gc_2$ the union of whose elements  is a super-set of $\{1,3,5\}$, is $\Mc^{\prime}_{\{1,3,5\}}=\{\{1,3,4\},\{3,4,5\}\}$.   We let $\av_{\{1,3,5\}}$ be a linear combination of $\av_{\{1,3,4\}}=\ev_{4,1}+4\ev_{4,2}$ and $\av_{\{3,4,5\}}=\ev_{4,1}+\ev_{4,2}+\ev_{4,3}$. Recall  from (<ref>) that,  the base vertical unit vectors of $\av_{\{1,3,5\}}$ are $\ev_{4,1}$ and $\ev_{4,3}$, which do not contain $\ev_{4,2}$.  Hence, we let

\begin{align}
\av_{\{1,3,5\}}= 4\av_{\{3,4,5\}} - \av_{\{1,3,4\}}=3\ev_{4,1} +4\ev_{4,3},\label{eq:ex3 a135}
\end{align}

to `zero-force' the term $\ev_{4,2}$.
Similarly, we let

\begin{align}
&\av_{\{1,3,6\}} =  2\av_{\{3,4,6\}}-  \av_{\{1,3,4\}}=       \ev_{4,1}+2\ev_{4,4}, \label{eq:ex3 a136}\\
&\av_{\{2,3,5\}} = 8 \av_{\{3,4,5\}}- \av_{\{2,3,4\}}= 7\ev_{4,1}+8\ev_{4,3}, \label{eq:ex3 235}\\
&\av_{\{2,3,6\}}=  4 \av_{\{3,4,6\}}-\av_{\{2,3,4\}}=3 \ev_{4,1}+4\ev_{4,4}, \label{eq:ex3 236}\\
&\av_{\{3,5,6\}}= 2\av_{\{3,4,5\}}- \av_{\{3,4,6\}}=  \ev_{4,1}+2\ev_{4,3}-\ev_{4,4},\label{eq:ex3 356}
\end{align}

to `zero-force' the term $\ev_{4,2}$.

Finally, each set $\Vc \in \binom{[6]}{3} \setminus (\Gc_1\cup \Gc_2)$ where $3\notin \Vc$, we let $\av_{\Vc}=\mathbf{0}_4$, where   $\mathbf{0}_{n}$ represents  the vertical $n$-dimensional   vector  whose elements are  all $0$.

As a result, we have determined $\av_{\Vc}$ for each $\Vc \in \binom{[6]}{3}$ as illustrated in Table <ref>. We then show the such choice satisfies
the constraints   in (<ref>), (<ref>), and (<ref>).

*Constraints in (<ref>)
For  users  $1,2$, the   matrix $\left[\av_{[3]},\av_{\{1,2,4\}},  \av_{\{1,2,5\}} ,\av_{\{1,2,6\}} \right]$
is the identity matrix $\mathbf{I}_{4}$ whose rank is $4$.
For users  $3,4$,  the   matrix $\left[\av_{\{1,3,4\}},\av_{\{2,3,4\}},  \av_{\{3,4,5\}} ,\av_{\{3,4,6\}} \right]$ has rank equal to $4$.
For  user $5$,  the   matrix $\left[\av_{\{1,3,5\}},\av_{\{2,3,5\}},  \av_{\{3,4,5\}} ,\av_{\{3,5,6\}} \right]$ has rank equal to $4$.
For user $6$,  the   matrix $\left[\av_{\{1,3,6\}},\av_{\{2,3,6\}},  \av_{\{3,4,6\}} ,\av_{\{3,5,6\}} \right]$ has rank equal to $4$.
Hence, the constraints  in (<ref>) are  satisfied.

*Constraints in (<ref>)
For user $1$, we first remove the columns of $0$'s from the   matrix  $\left[ \av_{\overline{\Sc}_{1}(1)}, \ldots, \av_{\overline{\Sc}_{1}\left(\binom{\Ksf-1}{3}\right)}  \right]$, to obtain

\begin{align}
\left[ \av_{\{2,3,4\}}, \av_{\{2,3,5\}}, \av_{\{2,3,6\}}, \av_{\{3,4,5\}},\av_{\{3,4,6\}}, \av_{\{3,5,6\}}  \right].\label{eq:ex3 user 1 constraint 2}
\end{align}

By construction, we have $\av_{\{2,3,5\}},\av_{\{2,3,6\}},\av_{\{3,5,6\}}$ are linear combinations of $ \av_{\{2,3,4\}},\av_{\{3,4,5\}},\av_{\{3,4,6\}}$. In addition,
$ \av_{\{2,3,4\}},\av_{\{3,4,5\}},\av_{\{3,4,6\}}$ are linearly independent. Hence, the rank of the matrix in (<ref>) is $3$, equal to the rank of $[\av_{\{2,3,4\}},\av_{\{3,4,5\}},\av_{\{3,4,6\}}]$.
Hence, the constraint  in (<ref>) is satisfied for user $1$. Similarly, this constraint is also satisfied for user $2$.

For user $3$, by construction, in each $\av_{\Vc}$ where $\Vc\in \binom{[6]\setminus \{3\}}{3}$, the coefficient of $\ev_{4,1}$ is $0$.  In addition,
$   \av_{\{1,2,4\}},\av_{\{1,2,5\}},\av_{\{1,2,6\}}$ are linearly independent.  Thus the   matrix
$\left[ \av_{\overline{\Sc}_{3}(1)}, \ldots, \av_{\overline{\Sc}_{3}\left(\binom{\Ksf-1}{3}\right)}  \right]$  has rank equal to $3$, equal to the rank of $[\av_{\{1,2,4\}},\av_{\{1,2,5\}},\av_{\{1,2,6\}}]$.
Hence, the constraint  in (<ref>) is satisfied for user $3$.
Similarly, this constraint is also satisfied for each user in $\{4,5,6\}$.

*Constraint in (<ref>)
For user $1$, recall that $\sv_1$ is a  left null space vector of the matrix
$\left[ \av_{\overline{\Sc}_{1}(1)}, \ldots, \av_{\overline{\Sc}_{1}\left(\binom{\Ksf-1}{3}\right)}  \right]$, whose    rank is $3$.
As explained before, its column-wise submatrix
$[  \av_{\{2,3,4\}},\av_{\{3,4,5\}},\av_{\{3,4,6\}}]$ has the same rank. Hence,
the left null space  of $[ \av_{\{2,3,4\}},\av_{\{3,4,5\}},\av_{\{3,4,6\}}]$ is the same as that of $\left[ \av_{\overline{\Sc}_{1}(1)}, \ldots, \av_{\overline{\Sc}_{1}\left(\binom{\Ksf-1}{3}\right)}  \right]$.
So we let  $\sv_1$ be a  left null space vector of $[  \av_{\{2,3,4\}},\av_{\{3,4,5\}},\av_{\{3,4,6\}}]$, which could be $\sv_1=[-8, 1, 7, 6]^{\text{T}}$.
Similarly, we let  $\sv_2$ be a  left null space vector of $[  \av_{\{1,3,4\}},\av_{\{3,4,5\}},\av_{\{3,4,6\}}]$, which could be $\sv_2=[-4, 1, 3, 2]^{\text{T}}$;
we let  $\sv_3$ be a  left null space vector of $[  \av_{\{1,2,4\}},\av_{\{1,2,5\}},\av_{\{1,2,6\}}]$, which could be $\sv_3=\ev_{4,1}$;
we let  $\sv_4$ be a  left null space vector of $[  \av_{\{1,2,3\}},\av_{\{1,2,5\}},\av_{\{1,2,6\}}]$, which could be $\sv_4=\ev_{4,2}$;
we let  $\sv_5$ be a  left null space vector of $[  \av_{\{1,2,3\}},\av_{\{1,2,4\}},\av_{\{1,2,6\}}]$, which could be $\sv_5=\ev_{4,3}$;
we let  $\sv_6$ be a  left null space vector of $[  \av_{\{1,2,3\}},\av_{\{1,2,4\}},\av_{\{1,2,5\}}]$, which could be $\sv_6=\ev_{4,4}$.

Since any two rows of $[\sv_1,\sv_2]$ are linearly independent and $[\sv_3,\sv_4,\sv_5,\sv_6]=\mathbf{I}_{4}$, we can see that any $4$ vectors of $\sv_1,\sv_2,\sv_3,\sv_4,\sv_5,\sv_6$ are linearly independent. Hence, the  constraint in (<ref>) is satisfied.

In conclusion, all constraints in (<ref>), (<ref>), and (<ref>) are satisfied; thus
the proposed scheme is decodable and secure.

* We first consider each $\av_{\Vc}$ where $[2] \subseteq \Vc$ and let  $\av_{\Vc}$ be a distinct vertical unit vector; i.e.,  we  let

\begin{align}
& \av_{[3]}= \ev_{4,1}, \  \av_{\{1,2,4\}}= \ev_{4,2}, \  \av_{\{1,2,5\}}= \ev_{4,3}, \  \av_{\{1,2,6\}}= \ev_{4,4}.\label{eq:ex 3 a[2]}
\end{align}

* We then consider each  $\av_{\Vc}$ where $\{3,4\} \subseteq \Vc$. We search for the   minimum   subset   of $\{[3],\{1,2,4\},\{1,2,5\},\{1,2,6\}\}$ the union of whose elements  is a super-set of $\Vc$; we denote this minimum   subset by $\Mc_{\Vc}$.
For example, if $\Vc=\{1,3,4\}$, the   minimum   subsets of
$\{[3],\{1,2,4\},\{1,2,5\},\{1,2,6\}\}$ the union of whose elements  is a super-set of $\{1,3,4\}$ is $\Mc_{\{1,3,4\}}=\{[3],\{1,2,4\}\}$, since $[3] \cup \{1,2,4\}=[4] \supseteq \{1,3,4\}$.  Then we let
$\av_{\Vc}$ be a linear combination of $\av_{\Vc_1}$ where $\Vc_1 \in \Mc_{\{1,3,4\}}$,  with uniform and i.i.d. coefficients.
For example, we let

\begin{align}
\av_{\{1,3,4\}}=\av_{[3]}+4\av_{\{1,2,4\}}= \ev_{4,1}+4\ev_{4,2}.\label{eq:ex3 a134}
\end{align}

Similarly, we let

\begin{align}
&\av_{\{2,3,4\}}=\av_{[3]}+8\av_{\{1,2,4\}}= \ev_{4,1}+8\ev_{4,2},\label{eq:ex3 a234} \\
& \av_{\{3,4,5\}}=\av_{[3]}+ \av_{\{1,2,4\}}+ \av_{\{1,2,5\}}= \ev_{4,1}+\ev_{4,2}+\ev_{4,3},\label{eq:ex3 a345} \\
& \av_{\{3,4,6\}}=\av_{[3]}+ 2\av_{\{1,2,4\}}+ \av_{\{1,2,6\}}= \ev_{4,1}+2\ev_{4,2}+\ev_{4,4}.\label{eq:ex3 a346}
\end{align}

To summarize Example <ref>, our selection on the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc \in \binom{[\Ksf]}{\Ssf} $,  contains the following steps from a high-level viewpoint:

* First step. Choose $\av_{\Vc}$ where $ [\Ksf-\Usf] \subseteq \Vc$ as  the base vertical unit vectors.

* Second step. Fix the composition  of each $\av_{\Vc}$ where $ [\Ksf-\Usf] \nsubseteq \Vc$.

* Third step. For   each $\av_{\Vc}$ where $ [\Ksf-\Usf] \nsubseteq \Vc$, determine the coefficients of the base vertical unit vectors which compose $\av_{\Vc}$.

In the following, we describe the  three-step vector selection for the general case where  $\Usf> \Ksf-\Usf+1$ and $\Usf<\Ksf-1$ in detail.

First step.
For each $j\in [\Ksf-\Usf+1: \Ksf]$, we let

\begin{align}
\av_{[\Ksf-\Usf]\cup\{j\}}=\ev_{\Usf,j-\Ksf+\Usf}.\label{eq:first class unit vector}
\end{align}

In other words, we let $[\av_{[\Ksf-\Usf]\cup\{\Ksf-\Usf+1\}}, \av_{[\Ksf-\Usf]\cup\{\Ksf-\Usf+2\}},\ldots, \av_{[\Ksf-\Usf]\cup \{\Ksf\}}]$ be the identity matrix $\mathbf{I}_{\Usf}$.

For the ease of   notation, we define that[For example, when $(\Ksf,\Usf, \Ssf)=(8,5,4)$, we have $\Gc_1=\{[4],\{1,2,3,5\},\{1,2,3,6\},\{1,2,3,7\},\{1,2,3,8\}\}.$ ]

$$\Gc_1:=\{ [\Ksf-\Usf]\cup\{j\}  : j\in [\Ksf-\Usf+1: \Ksf]\}.$$

It can be seen that

\begin{align}
|\Gc_1|= \Usf.\label{eq:length of G1}
\end{align}

Second step.
For each  $\av_{\Vc}$ where $\Vc \in \binom{[\Ksf]}{\Ssf} \setminus \Gc_1 $, we search for the   minimum   subset   of  $\Gc_1$,

the union of whose elements  is a super-set of $\Vc$; we denote this minimum   subset by $\Mc_{\Vc}$.
Then we determine the composition of  $\av_{\Vc}$,  by letting
$\av_{\Vc}$ be a linear combination of $\av_{\Vc_1}$ where $\Vc_1 \in \Mc_{\Vc}$;

\begin{align}
\av_{\Vc} =  b_{\Vc,1} \  \av_{\Mc_{\Vc}(1)} +\cdots + b_{\Vc,|\Mc_{\Vc}|} \ \av_{\Mc_{\Vc}(|\Mc_{\Vc}|)}, \label{eq:general case composition}
\end{align}

where $\bv_{\Vc}:=(b_{\Vc,1},\ldots,b_{\Vc,|\Mc_{\Vc}|})$ is a $|\Mc_{\Vc}|$-dimensional vector to be designed.

Third step.
We divide the sets in $\binom{[\Ksf]}{\Ssf}\setminus \Gc_1$ into three classes, which are then considered sequentially. In short, for each set $\Vc$ in the first class (denoted by $\Gc_2$ to be clarified later), we choose $\bv_{\Vc}$ uniformly and i.i.d. over $\mathbb{F}_{\qsf}^{|\Mc_{\Vc}|}$; for each set $\Vc$ in the second class (denoted by $\Gc_3$ to be clarified later), we choose $\bv_{\Vc}$ such that $\av_{\Vc}$ is also a linear combination of some
vectors $\av_{\Vc_1}$ where $\Vc_1\in \Gc_2$; for each set $\Vc$ in the third class (i.e., $\binom{[\Ksf]}{\Ssf}\setminus (\Gc_1 \cup \Gc_2 \cup \Gc_3)$), we let $\bv_{\Vc}$ be a all-zero vector. More precisely,

* We first consider the sets in[For example, when $(\Ksf,\Usf, \Ssf)=(8,5,4)$, we have $\Gc_2=\{\{1,4,5,6\},\{2,4,5,6\},\{3,4,5,6\},\{4,5,6,7\},\{4,5,6,8\}\}.$ ]

$$\Gc_2:=\left\{    [\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\} : j\in ([\Ksf-\Usf] \cup [2\Ksf-2\Usf+1: \Ksf])  \right\}.

Recall that $2\Usf>\Ksf+1$, thus  $\Ksf>2\Ksf-2\Usf+1$ and $[2\Ksf-2\Usf+1: \Ksf]$ is not empty.
Since $\Usf<\Ksf-1$, we have $\Ksf-\Usf \geq 2$ and thus $\Gc_1 \cap \Gc_2 =\emptyset$.
It can be seen that

\begin{align}
|\Gc_2|= \Ksf-\Usf+ (\Ksf-2\Ksf+2\Usf)=\Usf .\label{eq:length of G2}
\end{align}

For each $\Vc\in \Gc_2$, we choose $\bv_{\Vc}$   uniformly and i.i.d. over $\mathbb{F}^{|\Mc_{\Vc}|}_{\qsf}$.
More precisely,

* for each $j\in [\Ksf-\Usf]$, by assuming $\Vc=[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup\{j\}$,
it can be seen that

\Mc_{\Vc}=\big\{[\Ksf-\Usf]\cup \{\Ksf-\Usf+1\}, [\Ksf-\Usf]\cup \{\Ksf-\Usf+2\},\ldots, [\Ksf-\Usf]\cup \{2\Ksf-2\Usf\}  \big\},

and thus from (<ref>),  $\av_{\Vc}$ is with the form

\begin{align}
\av_{\Vc}= b_{\Vc,1}  \ \ev_{\Usf,1}+ \cdots+ b_{\Vc, \Ksf-\Usf} \  \ev_{\Usf,\Ksf-\Usf}. \label{eq:class 1,1}
\end{align}

We let each $ b_{\Vc,i}$, $i\in [\Ksf-\Usf]$, be chosen uniformly and i.i.d. over $\mathbb{F}_{\qsf}$;

* for each $j\in [2\Ksf-2\Usf+1: \Ksf]$, by assuming $\Vc=[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup\{j\}$,
it can be seen that

\begin{align*}
\Mc_{\Vc}&=\big\{[\Ksf-\Usf]\cup \{\Ksf-\Usf+1\}, [\Ksf-\Usf]\cup \{\Ksf-\Usf+2\},\ldots, [\Ksf-\Usf]\cup \{2\Ksf-2\Usf\} , \\& [\Ksf-\Usf]\cup \{j\}   \big\},
\end{align*}

and thus from (<ref>),  $\av_{\Vc}$ is with the form

\begin{align}
\av_{\Vc}= b_{\Vc,1} \  \ev_{\Usf,1}+ \cdots+ b_{\Vc, \Ksf-\Usf} \  \ev_{\Usf,\Ksf-\Usf}+  b_{\Vc, \Ksf-\Usf+1} \  \ev_{\Usf,j-\Ksf+\Usf}. \label{eq:class 1,2}
\end{align}

We let each $ b_{\Vc,i}$, $i\in [\Ksf-\Usf+1]$, be chosen uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.

* We then consider the sets  in[For example, when $(\Ksf,\Usf, \Ssf)=(8,5,4)$, we have $\Gc_3=\{\{1,4,5,7\},\{1,4,5,8\},\{2,4,5,7\},\{2,4,5,8\},\{3,4,5,7\},$ $\{3,4,5,8\}, \{4,5,7,8\}\}.$ ]

\begin{align*}
\Gc_3 &:= \Big\{\Tc \cup [\Ksf-\Usf+1:2\Ksf-2\Usf-1]: \Tc \in \binom{[\Ksf-\Usf]\cup [2\Ksf-2\Usf+1:\Ksf]}{2}, \\& \Tc \cap [2\Ksf-2\Usf+1:\Ksf]   \neq \emptyset \Big\}.
\end{align*}

Since $\Ksf-\Usf\geq 2$, we have $\Gc_3 \cap \Gc_1 =\emptyset$; since the integer $ 2\Ksf - 2\Usf$   appears in each set  in $\Gc_2$ and does not appear in any set in $\Gc_3$, we have $\Gc_3 \cap \Gc_2=\emptyset$. It can be seen that

\begin{align}
|\Gc_3|= \binom{\Ksf-(\Ksf-\Usf)}{2}-\binom{\Ksf-\Usf}{2}=\frac{\Ksf(2\Usf-\Ksf+1)}{2}-\Usf.\label{eq:length of G3}
\end{align}

For each $\Vc \in \Gc_3$, we search for the   minimum   subset   of $\Gc_2$ the union of whose elements  is a super-set of $\Vc$; we denote this minimum   subset by $\Mc^{\prime}_{\Vc}$.  We let $\av_{\Vc}$ be a linear combination of $\av_{\Vc_2}$ where $\Vc_2 \in \Mc^{\prime}_{\Vc}$.

More precisely, for each $ \Tc \in \binom{[\Ksf-\Usf]\cup [2\Ksf-2\Usf+1:\Ksf]}{2}$ where  $\Tc \cap [2\Ksf-2\Usf+1:\Ksf]   \neq \emptyset$,

* if $\Tc=\{i,j\}$ where $i\in [\Ksf-\Usf]$ and $j\in [2\Ksf-2\Usf+1:\Ksf]$, by assuming $\Vc=[\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup\{i,j\}$,
we have

\begin{align*}
&   \Mc^{\prime}_{\Vc} =
\big\{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{i\}, [\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\}   \big\}.
\end{align*}

Define $ \Mc^{\prime}_{\Vc}(1)=[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{i\}$ and  $ \Mc^{\prime}_{\Vc}(2)=[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\}$.
Hence, we aim to let $\av_{\Vc}$   be a linear combination of

\begin{align}
&\av_{\Mc^{\prime}_{\Vc}(1)}=   b_{\Mc^{\prime}_{\Vc}(1),1} \  \ev_{\Usf,1}+ \cdots+ b_{\Mc^{\prime}_{\Vc}(1), \Ksf-\Usf}  \ \ev_{\Usf,\Ksf-\Usf} ,\label{eq:from of ai first case}\\
& \text{and } \av_{\Mc^{\prime}_{\Vc}(2)}= b_{\Mc^{\prime}_{\Vc}(2),1} \  \ev_{\Usf,1}+ \cdots+ b_{\Mc^{\prime}_{\Vc}(2), \Ksf-\Usf} \  \ev_{\Usf,\Ksf-\Usf}+  b_{\Mc^{\prime}_{\Vc}(2), \Ksf-\Usf+1} \  \ev_{\Usf,j-\Ksf+\Usf},\label{eq:from of aj first case}
\end{align}

where (<ref>) and (<ref>) come from (<ref>) and (<ref>), respectively. Recall that each element in
$\bv_{\Mc^{\prime}_{\Vc}(1)}$ and  $\bv_{\Mc^{\prime}_{\Vc}(2)}$ is chosen uniformly and i.i.d.   over $\mathbb{F}_{\qsf}$.

In addition, we have

\begin{align*}
\Mc_{\Vc} =&\big\{[\Ksf-\Usf]\cup \{\Ksf-\Usf+1\}, [\Ksf-\Usf]\cup \{\Ksf-\Usf+2\},\ldots, [\Ksf-\Usf]\cup \{2\Ksf-2\Usf-1\},  \\& [\Ksf-\Usf]\cup \{j\} \big\}.
\end{align*}

Hence, from (<ref>), $\av_{\Vc}$ is   with the form

\begin{align}
\av_{\Vc} &=b_{\Vc,1} \  \av_{[\Ksf-\Usf]\cup \{\Ksf-\Usf+1\}} + \cdots+ b_{\Vc,\Ksf-\Usf-1} \  \av_{[\Ksf-\Usf]\cup \{2\Ksf-2\Usf-1\}} + b_{\Vc,\Ksf-\Usf} \  \av_{[\Ksf-\Usf]\cup \{j\}} \\
&= b_{\Vc,1}  \ \ev_{\Usf,1} + \cdots+ b_{\Vc,\Ksf-\Usf-1} \  \ev_{\Usf,\Ksf-\Usf-1}   + b_{\Vc,\Ksf-\Usf}  \ \ev_{\Usf,j-\Ksf+\Usf}.\label{eq:form of Tij first case}
\end{align}

By comparing (<ref>) with the form of $\av_{\Vc}$ in (<ref>), we need to `zero-force'  $\ev_{\Usf,\Ksf-\Usf}$, which could be done by letting

\begin{align}
\av_{\Vc} = b_{\Mc^{\prime}_{\Vc}(2), \Ksf-\Usf}  \  \av_{\Mc^{\prime}_{\Vc}(1)} - b_{\Mc^{\prime}_{\Vc}(1), \Ksf-\Usf}  \ \av_{\Mc^{\prime}_{\Vc}(2)}.\label{eq:value of aij first case}
\end{align}

* if $\Tc=\{i,j\}$ where $2\Ksf-2\Usf+1 \leq i<j \leq \Ksf$, by assuming $\Vc=[\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup\{i,j\}$,
it can be seen that

\begin{align*}
&   \Mc^{\prime}_{\Vc} =
\big\{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{i\}, [\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\}   \big\}.
\end{align*}

Hence, we aim to let $\av_{\Vc}$   be a linear combination of

\begin{align}
&\av_{\Mc^{\prime}_{\Vc}(1)}=   b_{\Mc^{\prime}_{\Vc}(1),1} \  \ev_{\Usf,1}+ \cdots+ b_{\Mc^{\prime}_{\Vc}(1), \Ksf-\Usf}  \ \ev_{\Usf,\Ksf-\Usf} +  b_{\Mc^{\prime}_{\Vc}(1), \Ksf-\Usf+1} \  \ev_{\Usf,i-\Ksf+\Usf} ,\label{eq:from of ai second case}\\
& \text{and } \av_{\Mc^{\prime}_{\Vc}(2)}= b_{\Mc^{\prime}_{\Vc}(2),1} \  \ev_{\Usf,1}+ \cdots+ b_{\Mc^{\prime}_{\Vc}(2), \Ksf-\Usf}  \ \ev_{\Usf,\Ksf-\Usf}+  b_{\Mc^{\prime}_{\Vc}(2), \Ksf-\Usf+1}  \ \ev_{\Usf,j-\Ksf+\Usf},\label{eq:from of aj second case}
\end{align}

where (<ref>) and (<ref>) come from (<ref>).

In addition, we have

\begin{align*}
\Mc_{\Vc} =&\big\{[\Ksf-\Usf]\cup \{\Ksf-\Usf+1\}, [\Ksf-\Usf]\cup \{\Ksf-\Usf+2\},\ldots, [\Ksf-\Usf]\cup \{2\Ksf-2\Usf-1\},    \\& [\Ksf-\Usf]\cup \{i\}, [\Ksf-\Usf]\cup \{j\} \big\}.
\end{align*}

Hence, from (<ref>), $\av_{\Vc}$ is with the form

\begin{align}
\av_{\Vc}&= b_{\Vc,1}  \ \av_{[\Ksf-\Usf]\cup \{\Ksf-\Usf+1\}} + \cdots+ b_{\Vc,\Ksf-\Usf-1}  \ \av_{[\Ksf-\Usf]\cup \{2\Ksf-2\Usf-1\}} + b_{\Vc,\Ksf-\Usf}  \ \av_{[\Ksf-\Usf]\cup \{i\}} \nonumber \\& + b_{\Vc,\Ksf-\Usf+1}  \ \av_{[\Ksf-\Usf]\cup \{j\}} \\
&= b_{\Vc,1}  \ \ev_{\Usf,1} + \cdots+ b_{\Vc,\Ksf-\Usf-1}  \ \ev_{\Usf,\Ksf-\Usf-1}  +b_{\Vc,\Ksf-\Usf}  \ \ev_{\Usf,i-\Ksf+\Usf}  + b_{\Vc,\Ksf-\Usf+1} \  \ev_{\Usf,j-\Ksf+\Usf}.\label{eq:form of Tij second case}
\end{align}

By comparing (<ref>) with the form of $\av_{\Vc}$ in (<ref>), we need to `zero-force'  $\ev_{\Usf,\Ksf-\Usf}$, which could be done by letting

\begin{align}
\av_{\Vc} = b_{\Mc^{\prime}_{\Vc}(2), \Ksf-\Usf}  \  \av_{\Mc^{\prime}_{\Vc}(1)} - b_{\Mc^{\prime}_{\Vc}(1), \Ksf-\Usf}  \ \av_{\Mc^{\prime}_{\Vc}(2)}.\label{eq:value of aij second case}
\end{align}

* Finally, for each $\Vc\in \binom{[\Ksf]}{\Ssf} \setminus (\Gc_1\cup \Gc_2 \cup \Gc_3)$, we let

\begin{align}
\av_{\Vc}=\mathbf{0}_{\Usf}. \label{eq:last class all zero}
\end{align}

This concludes our selection  on $\av_{\Vc}$ where $\Vc \in \binom{[\Ksf]}{\Ssf}$.
Next we will show that the above choice of these   $\Usf$-dimensional vectors  satisfies the constraints in (<ref>), (<ref>), and (<ref>), with high probability.

*Constraints in (<ref>)
For each user $k\in [\Ksf-\Usf]$, the   matrix
$$[\av_{[\Ksf-\Usf]\cup\{\Ksf-\Usf+1\}}, \av_{[\Ksf-\Usf]\cup\{\Ksf-\Usf+2\}},\ldots, \av_{[\Ksf-\Usf]\cup \{\Ksf\}}]$$
is the identity matrix  $\mathbf{I}_{\Usf}$, whose rank is $\Usf$.

For each user $k\in [\Ksf-\Usf+1:2\Ksf-2\Usf]$,  let us focus on the matrix

\begin{align}
[\av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{1\}},  \ldots, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{\Ksf-\Usf\}}, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{2\Ksf-2\Usf+1\}},\ldots, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{\Ksf\}}],\label{eq:user k-u+1 full rank matrix}
\end{align}

whose dimension is $\Usf \times \Usf$.
By our construction, for each $j\in [\Ksf-\Usf]$, by (<ref>) we have (assume $\Vc=[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\}$)

\begin{align}
\av_{\Vc}= b_{\Vc,1} \  \ev_{\Usf,1}+ \cdots+ b_{\Vc, \Ksf-\Usf}  \ \ev_{\Usf,\Ksf-\Usf},
\label{eq:user k-u+1 full first case}
\end{align}

where  $ b_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\},i}$, $i\in [\Ksf-\Usf]$, is chosen uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.
In addition,
for each $j\in [2\Ksf-2\Usf+1:\Ksf]$, by (<ref>) we have  (assume $\Vc=[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\}$)

\begin{align}
\av_{\Vc}& = b_{\Vc,1}  \ \ev_{\Usf,1}+ \cdots+ b_{\Vc, \Ksf-\Usf}  \ \ev_{\Usf,\Ksf-\Usf}  +  b_{\Vc, \Ksf-\Usf+1} \  \ev_{\Usf,j-\Ksf+\Usf}, \label{eq:user k-u+1 full sec case}
\end{align}

where each $ b_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\},i}$, $i\in [\Ksf-\Usf+1]$, is chosen uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.
Since $\qsf$ is large enough, from (<ref>) and (<ref>), it can be seen that the matrix in (<ref>) has rank equal to $\Usf$ with high probability.

For each user $k\in [2\Ksf-2\Usf+1:\Ksf]$,  let us focus on the matrix

\begin{align}
&\big[\av_{\{1\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup \{k\}}, \av_{\{2\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup \{k\}},\ldots, \av_{\{\Ksf-\Usf\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup \{k\}},\nonumber\\
& \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup\{2\Ksf-2\Usf,k\} }, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup\{2\Ksf-2\Usf+1,k\}},\ldots, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup\{ k,\Ksf\} }
\big], \label{eq:user 2k-2u+1 full rank matrix}
\end{align}

whose dimension is $\Usf \times \Usf$.
For each $j\in [\Ksf-\Usf]$, by (<ref>), we have

\begin{align}
\av_{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup \{k\}} &= b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{k\},\Ksf-\Usf}  \ \av_{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] } \nonumber\\&-
b_{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] ,\Ksf-\Usf}  \ \av_{ [\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{k\}},
\label{eq:user 2k-2u+1 full rank matrix j small}
\end{align}

where $b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{k\},\Ksf-\Usf}$ and  $b_{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] ,\Ksf-\Usf}$ are chosen uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.
For each $j\in [2\Ksf-2\Usf+1:\Ksf]\setminus \{k\}$, by (<ref>), we have

\begin{align}
&\av_{[\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup\{j,k\} }= \nonumber\\
&   \begin{cases} b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{k\},\Ksf-\Usf}  \ \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\}}  -
b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\},\Ksf-\Usf}  \ \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{k\}}, & \text{ if }  j<k;
\\ b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\},\Ksf-\Usf}  \ \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{k\}}  -
b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{k\},\Ksf-\Usf}  \ \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\}},  & \text{ if }  j>k , \end{cases}
\label{eq:user 2k-2u+1 full rank matrix j large}
\end{align}

where $b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{k\},\Ksf-\Usf}$ and $b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\},\Ksf-\Usf}$ are chosen uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.
In addition, as we showed before,

$$\av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{1\}},  \ldots, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{\Ksf-\Usf\}}, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{2\Ksf-2\Usf+1\}},\ldots, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{\Ksf\}}$$

which are the columns of the matrix in (<ref>),  are linearly independent with high probability.
Hence, by (<ref>), (<ref>), and the fact
that $ \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf-1]\cup\{2\Ksf-2\Usf,k\} }=\av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup\{k\} }$  is in the matrix in (<ref>), we can see that    the matrix in (<ref>) is full rank with high probability.

The following lemma will be proved in Appendix <ref> by     the Schwartz-Zippel lemma <cit.>.

For each user $k\in [2\Ksf-2\Usf+1:\Ksf]$, the matrix in (<ref>) has rank equal to $\Usf$ with high probability.

Hence, the constraints in (<ref>) are satisfied with high probability.

*Constraints in (<ref>)
For each user $k\in [\Ksf-\Usf]$,   the sets in $\Vc\in \binom{[\Ksf]\setminus \{k\}}{\Ssf}$ do not contain $k$.
By our construction, it can be seen that

\begin{align}
\binom{[\Ksf]\setminus \{k\}}{\Ssf} \cap \Gc_1 &=\emptyset,\\
\binom{[\Ksf]\setminus \{k\}}{\Ssf} \cap \Gc_2&=\{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf]: j\in [\Ksf] \setminus (\{k\} \cup [\Ksf-\Usf+1:2\Ksf-2\Usf] ) \}, \label{eq:unknown G2}\\
\binom{[\Ksf]\setminus \{k\}}{\Ssf} \cap \Gc_3&=\Big\{\Tc \cup [\Ksf-\Usf+1:2\Ksf-2\Usf-1]: \Tc \in \binom{([\Ksf-\Usf]\cup [2\Ksf-2\Usf+1:\Ksf]) \setminus \{k\}}{2}, \nonumber\\& \Tc \cap [2\Ksf-2\Usf+1:\Ksf]   \neq \emptyset \Big\}.\label{eq:unknown G3}
\end{align}

Focus on the sets in (<ref>).
Since the matrix in (<ref>) is full rank with high probability,
the $\Usf-1$  vectors in

\begin{align}
\{\av_{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] } : j\in [\Ksf] \setminus (\{k\} \cup [\Ksf-\Usf+1:2\Ksf-2\Usf] ) \} \label{eq:unknown G2 set}
\end{align}

are linearly independent with high probability.

Focus on the sets in (<ref>).
For each $\Tc \in \binom{([\Ksf-\Usf]\cup [2\Ksf-2\Usf+1:\Ksf]) \setminus \{k\}}{2}$ where $\Tc \cap [2\Ksf-2\Usf+1:\Ksf]   \neq \emptyset$,
by assuming that $\Vc=\Tc \cup [\Ksf-\Usf+1:2\Ksf-2\Usf-1]$ and
$\Tc=\{i,j\}$ where $i<j$,
it can be seen from (<ref>) and (<ref>) that

\begin{align}
\av_{\Vc}= b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\},\Ksf-\Usf} \ \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{i\}}- b_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{i\},\Ksf-\Usf} \ \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\}},\label{eq:unknown G3 set}
\end{align}

where both $\av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{i\}}$ and $\av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup \{j\}}$ are in (<ref>).

Recall that for   each  set   $\Vc\in \binom{[\Ksf]}{\Ssf} \setminus (\Gc_1\cup\Gc_2\cup\Gc_3)$,  from (<ref>) we have $\av_{\Vc}=\mathbf{0}_{\Usf}$.
As a result, the matrix  $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$ has rank equal to $\Usf-1$ with high probability, which is the same as its column-wise sub-matrix (whose dimension is $\Usf\times (\Usf-1)$)

\begin{align}
&[ \av_{\{1\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] }, \ldots, \av_{\{k-1\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] },\av_{\{k+1\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] },\ldots, \nonumber\\&
\av_{\{\Ksf-\Usf\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] }, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup\{\Ksf-\Usf+1\}},\ldots, \av_{[\Ksf-\Usf+1:2\Ksf-2\Usf]\cup\{\Ksf\}}]
, \label{eq:unknown G2 matrix}
\end{align}

where  $\av_{\{j_1\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] }$, $j_1\in [\Ksf-\Usf]\setminus \{k\}$ is given in (<ref>) and
$\av_{\{j_2\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf] }$, $j_2\in [2\Ksf-2\Usf+1:\Ksf] $ is given in (<ref>).

For each user $k\in [\Ksf-\Usf+1:\Ksf]$, among the sets in   $\Vc\in \binom{[\Ksf]\setminus \{k\}}{\Ssf}$ which do not contain $k$, we can see that
in $\av_{\Vc}$ the coefficient of  $\ev_{\Usf, k-\Ksf+\Usf}$ is $0$. This could be directly checked from  the second step to select the $\Usf$-dimensional vectors,    where we fix the composition of $\av_{\Vc}$ in (<ref>).
Thus the rank of $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$  is no more than $\Usf-1$. In addition, its column-wise sub-matrix

\begin{align}
&[ \av_{[\Ksf-\Usf]\cup\{\Ksf-\Usf+1\} }, \ldots, \av_{[\Ksf-\Usf]\cup\{k-1\} },\av_{[\Ksf-\Usf]\cup\{k+1\} },\ldots, \av_{[\Ksf-\Usf]\cup\{\Ksf\} }]\nonumber\\
&=[\ev_{\Usf,1},\ldots,\ev_{\Usf,k-\Ksf+\Usf-1},\ev_{\Usf,k-\Ksf+\Usf+1},\ldots,\ev_{\Usf,\Usf}  ]
, \label{eq:unknown G1 matrix}
\end{align}

has rank equal to $\Usf-1$. Hence, the rank of $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$  is $\Usf-1$.

Hence, the constraints in (<ref>) are satisfied with high probability.

*Constraint in (<ref>)
For each user $k\in [\Ksf-\Usf]$, as we showed before,  the matrix  $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$ has the same rank equal to $\Usf-1$, as its column-wise sub-matrix  in (<ref>).
Hence, the left null space of the matrix  $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$ is the same as that of its column-wise sub-matrix  in (<ref>). Since the matrix in (<ref>) has dimension $\Usf\times (\Usf-1)$ and rank $\Usf-1$ with high probability, its left null space contains exactly one linearly independent left null space vector (with dimension $1\times \Usf$).
Let $\sv_k$ be one   left null space vector of  the matrix in (<ref>).

For each user $k\in [\Ksf-\Usf+1:\Ksf]$,   the matrix  $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$ has the same rank equal to $\Usf-1$, as its column-wise sub-matrix  in (<ref>). Hence, the left null space of the matrix  $\left[ \av_{\overline{\Sc}_{k}(1)}, \ldots, \av_{\overline{\Sc}_{k}\left(\binom{\Ksf-1}{\Ssf}\right)}  \right]$ is the same as that of its column-wise sub-matrix  in (<ref>), which contains exactly one linearly independent left null space vector. One possible choice of the left null space vector could be

\begin{align}
\sv_k=\ev^{\text{T}}_{\Usf,k-\Ksf+\Usf}. \label{eq:left null vector of user k-u+1}
\end{align}

The most difficult part in the proof of the constraint in (<ref>) is    the
following lemma, which  will be proved in Appendix <ref> by     the Schwartz-Zippel lemma <cit.>.

For any $\Ac \subseteq [\Ksf]$ where $|\Ac|=\Usf$, the $\Usf$-dimensional vectors $\sv_{k}$ where $k\in \Ac$ are linearly independent with high probability.

Directly from Lemma <ref>, it can be seen that the constraint in (<ref>) is satisfied with high probability.

In conclusion, all constraints in (<ref>), (<ref>), and (<ref>) are satisfied with high probability.  Hence, there must exist a choice of $\bv_{\Vc}$ where $\Vc\in \Gc_2$ satisfying those constraints.
Thus the proposed scheme is decodable and secure.
In this case, we need the keys   $Z_{\Vc}$ where $\Vc \in (\Gc_1\cup \Gc_2\cup \Gc_3)$. It can be seen from (<ref>), (<ref>), and (<ref>) that there are totally

\Usf+\Usf+  \frac{\Ksf(2\Usf-\Ksf+1)}{2}-\Usf=\Usf+  \frac{\Ksf(2\Usf-\Ksf+1)}{2}

keys each of which is shared by $\Ssf$ users.

§ EXPERIMENTAL RESULTS

We implement our proposed secure aggregation scheme (which is referred to as  for the sake of simplicity)  in Python2.7 by using the MPI4py library over the Amazon EC2 cloud, which is then compared to the   original  secure aggregation  scheme in <cit.> (referred to as ), and the
best existing information theoretic secure aggregation scheme with offline key sharing  in <cit.> (referred to as ). We compare the   key sharing    times
of    and , since the communication costs in the model aggregation phase of these two schemes are the same.
In addition, since    provides computational security instead of information theoretic security, the total size of needed keys is much smaller in . Thus we compare   the model aggregation times of    and .
Note that  in the experiments, we only record the  the communication  time as the running time in each procedure;     the detail of running   times in each procedure  of ,     , and  could be found in   Appendix <ref>.

Amazon EC2 Setup.
The Amazon EC2  and

instances are selected, where we take one specific
instance as the server and all the other instances are users.
The Amazon EC2 T2 instances have a 3.0 GHz Intel Scalable Processor, and all instances which we use in this experiment have the same  capacity of computation,  memory and network resources. The transmission speed is up to 100MB/s between the server and users. By setting the field size $\qsf$ as $7$,
we  generate the  input vectors uniformly i.i.d. over $\mathbb{F}_7$, and consider the  three   sizes of  each input vector  (100KB, 200KB, 300KB) as suggested  in <cit.>.
In the offline key sharing phase, we consider that each two users have a private link to communicate as in <cit.>; thus  between each two users,  we use the   command.
For each considered system with $(\Ksf,\Usf,\Ssf)$,
we use Monte-Carlo methods with $20$ samples and take the average times over these $20$ samples.

v.s. : $\Usf=(\Ksf+1)/2$

() v.s. : $\Usf=\Ksf-1$

v.s. : $\Usf=(\Ksf+1)/2$

v.s. : $\Usf=\Ksf-1$

The key sharing time and the model aggregation time of  versus  and , respectively.

v.s. .
We first compare our  with , by  considering  the
two cases  where  $\Usf = (\Ksf + 1)/2$ illustrated in Fig. <ref> and $\Usf =  \Ksf- 1$ illustrated in Fig. <ref>, respectively. For each case, our  needs $\Ssf=\Ksf-\Usf+1$.

In Fig. <ref>, since $\Usf = (\Ksf + 1)/2$, we have $\Usf=\Ksf-\Usf+1$ and thus our secure aggregation scheme is the one in Section <ref>. We use the cyclic key assignment; more precisely, for each $i\in [\Ksf]$, we let user $i$ randomly generate a key $Z_{\Cc(i)}$ with $(\Ksf-\Usf+1)\Lsf/\Usf=\Lsf$ symbols, and transmit   $Z_{\Cc(i)}$ to the other $\Usf-1$ users  in $\Cc(i)$, where  $\Cc$ is defined in (<ref>).
Compared to ,  reduces the key sharing time by at least $16.5\%$ and at most $31.7\%$ in Fig. <ref>.
The improvement of  is mainly because the number of keys is smaller than that of , and thus  less number of connections is needed to build among users.

In Fig. <ref>, since $\Usf =  \Ksf- 1$, our secure aggregation scheme is the one  in Section <ref>. In this case, for each pair of users $\Vc=\{\Vc(1),\Vc(2)\}$ where $\Vc\subseteq [\Ksf]$, $|\Vc|=2$, and $\Vc(1)< \Vc(2)$, there is one key $Z_{\Vc}=\{Z_{\Vc,\Vc(1)},Z_{\Vc,\Vc(2)}\}$ with $(\Ksf-\Usf+1)\Lsf/\Usf=2\Lsf/\Usf$ symbols shared by users in $\Vc$. We consider two ways of key sharing: (i) “” in Fig. <ref>:  user $\Vc(1)$ randomly generates $Z_{\Vc}$ and sends  $Z_{\Vc}$ to user $\Vc(2)$; (ii) “” in Fig. <ref>: user $\Vc(1)$ randomly generates $Z_{\Vc,\Vc(1)}$ and sends $Z_{\Vc,\Vc(1)}$ to user $\Vc(2)$, while user $\Vc(2)$ randomly generates $Z_{\Vc,\Vc(2)}$ and sends $Z_{\Vc,\Vc(2)}$ to user $\Vc(1)$.
Compared to ,
increase the key sharing time by at least $11.2\%$ and at most $23.7\%$ in Fig. <ref>, while the key sharing time of
is close to that of . The reason that the key sharing time of  is more than that of  is because
the transmissions of users  in Amazon EC2 are parallel, and in  the users with smaller indices  transmit more keys in the key sharing phase. In , we “balance” the numbers of user transmissions which reduce key sharing time.

v.s. .
We then compare our  with , by  considering the      two cases   where  $\Usf = (\Ksf + 1)/2$ illustrated in Fig. <ref> and $\Usf =  \Ksf- 1$ illustrated in Fig. <ref>, respectively.
Compared to ,  reduces the model aggregation time by at least $48\%$ and at most $53\%$ in Fig. <ref>, and reduces the model aggregation time by at least $33\%$ and at most $44\%$ in Fig. <ref>.
From the theoretic viewpoint, this improvement is because our  achieves the optimal communication cost in the model aggregation phase, while   is sub-optimal.

§ CONCLUSIONS

In this paper, we formulated the information theoretic secure aggregation problem with uncoded groupwise keys, where the keys are independent of each other and each of them is shared by a group of users. 	For the case   $\Ssf >\Ksf-\Usf$, we proposed a new secure aggregation scheme, which is the first scheme with uncoded   keys.  Quite surprisingly, the proposed scheme with uncoded groupwise keys  achieves the same capacity region of the communication rates in the two-round transmissions as the optimal scheme with any possible keys.  In addition, to achieve the capacity region, we showed that not all keys shared by   $\Ssf$ users are needed; instead, the number of keys used in the proposed scheme is   no more than $\Oc(\Ksf^2)$.
When $\Ssf \leq \Ksf-\Usf$, by proposing a new converse bound under the constraint of uncoded groupwise keys, we showed that uncoded groupwise keys sharing is strictly sub-optimal compared to coded keys sharing.

Ongoing work includes
the characterization of the capacity region for the case  $\Ssf \leq \Ksf-\Usf$ and the extension  of the proposed secure aggregation scheme to tolerate the collusion between the server and the users.

§ PROOF OF THEOREM <REF>

We first consider the case $1=\Ssf\leq \Ksf-\Usf$.  In this case, it can be seen that $\Usf\leq \Ksf-1$.
We will show by contradiction that there does not exist any feasible secure aggregation scheme.

Assume that there exists one feasible secure aggregation scheme.
When $ \Uc_1=[\Usf+1]$ and $\Uc_2=[2:\Usf+1]$, the server can recover $\sum_{k \in [\Usf+1]} W_{k }$; thus

\begin{align}
0&=H\left(  W_{1}+\cdots+W_{\Usf+1}  | X_1,  (X_{k_1}, Y^{[\Usf+1]}_{k_1} :k_1\in [2:\Usf+1] ) \right) \\
&\geq  H\left(W_{1}+\cdots+W_{\Usf+1}   | X_1,    (W_{k_1}, Z_{\{k_1\}}:k_1\in [2:\Usf+1] ) \right)\label{eq:S1 impos 1}\\
&= H\left(W_1 | X_1,    (W_{k_1}, Z_{\{k_1\}}:k_1\in [2:\Usf+1] ) \right) \\
&=  H(W_1| X_1 ),
\label{eq:S1 impos 2}
\end{align}

where (<ref>) follows since $(X_{k_1}, Y^{[\Usf+1]}_{k_1} :k_1\in [2:\Usf+1] ) $ is a function of $(W_{k_1}, Z_{\{k_1\}}:k_1\in [2:\Usf+1] )$ and condition does not increase entropy, (<ref>) follows since $X_k$ is a function of $(W_1,Z_{\{1\}})$  and $(W_1,Z_{\{1\}})$ is independent of $(W_{2},\ldots,W_{\Usf+1},Z_{\{2\}},\ldots,Z_{\{\Usf+1\}})$.
However, by the security constraint in (<ref>), we should have $I(X_1;W_1)=0$, which leads (recall that $W_1$ contains $\Lsf$ uniform and i.i.d. symbols over $\mathbb{F}_{\qsf}$)

\begin{align}
H(W_1|X_1)=H(W_1)-I(X_1;W_1)=\Lsf. \label{eq:contradiction}
\end{align}

Hence, (<ref>) contradicts to (<ref>).

In the rest of this proof, we consider the case where $2\leq \Ssf \leq \Ksf-\Usf$.
By the converse bound in Lemma <ref>, we have $\Rsf_1\geq 1$. Hence, for any feasible secure aggregation scheme,
we can assume that it achieves $\Rsf_1=1+\asf$, where $\asf \geq 0$.
Then in the following, we focus on this scheme.

For each $k\in [\Ksf]$, when $|\Uc_1|\geq \Usf+1$, $k\in\Uc_1$,  and $\Uc_2=\Uc_1\setminus \{k\}$, the server can recover $\sum_{k_1\in \Uc_1} W_{k_1}$; thus
we have

\begin{align}
0&=H\left(\sum_{k_1\in \Uc_1} W_{k_1} \Big| X_k,  (X_{k_2}, Y^{\Uc_1}_{k_2} :k_2\in \Uc_2 ) \right) \\
&\geq  H\left(\sum_{k_1\in \Uc_1} W_{k_1} \Big| X_k, Z_k,  (W_{k_2}, Z_{k_2}:k_2\in \Uc_2 ) \right)\label{eq:function and condition}\\
&=  H(W_k| X_k, Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 ) ),
\label{eq:prove markov}
\end{align}

where (<ref>) follows since   $(X_{k_2}, Y^{\Uc_1}_{k_2} :k_2\in \Uc_2 )$ is a function of $(W_{k_2}, Z_{k_2}:k_2\in \Uc_2 )$,   and condition does not  increase entropy.
From (<ref>), we have

\begin{align}
H(X_k|Z_k) &\geq H(X_k| Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 ) ) \\
&= I(W_k;X_k| Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 )) + H(X_k| W_k,Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 ))\\
&=I(W_k;X_k| Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 )) \label{eq:function of Zk Wk}\\
&= H(W_k|Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 ) ) -H(W_k| X_k,Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 ))\\
&\stackrel{\eqref{eq:prove markov}}{\geq}
H(W_k|Z_k, (W_{k_2}, Z_{k_2} :k_2 \in \Uc_2 ) )\\
\label{eq:HXk given Zk}
\end{align}

where (<ref>) follows since $X_k$ is a function of $(W_k,Z_k)$.
From (<ref>), we have

\begin{align}
I(W_k; X_k | Z_k)&= H(X_k|Z_k)-H(X_k|Z_k,W_k)\\
&\stackrel{\eqref{eq:HXk given Zk}}{\geq}   \Lsf. \label{eq:I independent}
\end{align}

From (<ref>), we have

\begin{align}
H(X_k|Z_k)=I(W_k; X_k | Z_k) + H(X_k|Z_k, W_k)\geq  \Lsf.
\label{eq:H(X_k|Z_k)}
\end{align}

In addition, from (<ref>) we also have

\begin{align}
H(W_k|Z_k,X_k)=H(W_k|Z_k) -I(W_k;X_k|Z_k)\stackrel{\eqref{eq:I independent}}{\leq} H(W_k|Z_k)-\Lsf=0.
\label{eq:new Marcov}
\end{align}

We   define that  $\Sc^{\prime}_k:=\left\{\Vc \in \binom{[\Ksf]}{\Ssf}  :   k\in \Vc \right\}$, and sort the sets in  $\Sc^{\prime}_k$ in a lexicographic order. $\Sc^{\prime}_k(j) $ represents the $j^{\text{th}}$ set in $\Sc^{\prime}_k$, where $j\in \left[\binom{\Ksf-1}{\Ssf-1} \right]$. Since
$2\leq \Ssf \leq \Ksf-\Usf$,  we can see that $\binom{\Ksf-1}{\Ssf-1} \geq 2$.
For any set $\Sc\subseteq \Sc^{\prime}_k$,  from (<ref>) we have

\Lsf \stackrel{\eqref{eq:H(X_k|Z_k)}}{\leq}    H(X_k|Z_k) \leq H(X_k| (Z_{\Vc}:\Vc\in \Sc) ) \leq H(X_k)  \leq \Rsf_1 = \Lsf(1+\asf).

Hence, we have

\begin{align}
\Lsf \leq H(X_k| (Z_{\Vc}:\Vc\in \Sc) ) \leq \Lsf(1+\asf). \label{eq:HXk given Zv}
\end{align}

Then  for any two non-empty collections of sets $\Vc_1, \Vc_2 \subseteq \Sc^{\prime}_k$ where $\Vc_1 \neq \Vc_2$, we have

\begin{align}
&H((Z_{\Vc}:\Vc \in \Vc_1\cup \Vc_2) |X_k)\nonumber\\
&=  \sum_{j\in [2]} H((Z_{\Vc}:\Vc \in \Vc_{j} ) | X_k, (Z_{\Vc}:\Vc \in \Vc_{j-1} )  )  \\
\sum_{j\in [2]} H((Z_{\Vc}:\Vc \in \Vc_{j} ) |   (Z_{\Vc}:\Vc \in \Vc_{j-1} )  )-I((Z_{\Vc}:\Vc \in \Vc_{j} );X_k | (Z_{\Vc}:\Vc \in \Vc_{j-1} )  )\\
%\sum_{j\in [|\Sc^{\prime}_k|]} H(Z_{\Sc^{\prime}_k(j)} | Z_{\Sc^{\prime}_k(1)},\ldots, Z_{\Sc^{\prime}_k(j-1)}  ) -I(Z_{\Sc^{\prime}_k(j)};X_k | Z_{\Sc^{\prime}_k(1)},\ldots, Z_{\Sc^{\prime}_k(j-1)} ) \\
&\geq \sum_{j\in [2]} \left( H((Z_{\Vc}:\Vc \in \Vc_{j} ) |   (Z_{\Vc}:\Vc \in \Vc_{j-1} )  ) -\asf\Lsf\right)  \label{eq:Mutual infor to Xk}  \\
&=  \sum_{j\in [2]} H((Z_{\Vc}:\Vc \in \Vc_{j}\setminus\Vc_{j-1} ))   -2 \asf\Lsf \label{eq:independence given Xk},
\end{align}

where (<ref>) follows since

\begin{align*}
I((Z_{\Vc}:\Vc \in \Vc_{j} );X_k | (Z_{\Vc}:\Vc \in \Vc_{j-1} )  ) &=H(X_k | (Z_{\Vc}:\Vc \in \Vc_{j-1} ) ) - H(X_k | (Z_{\Vc}:\Vc \in \Vc_{1}\cup\Vc_{2} )  )  \\
&\stackrel{\eqref{eq:HXk given Zv}}{\leq}  \Lsf(1+\asf)-\Lsf=\asf\Lsf.
%I(Z_{\Sc^{\prime}_k(j)};X_k | Z_{\Sc^{\prime}_k(1)},\ldots, Z_{\Sc^{\prime}_k(j-1)} )  &= H(X_k | Z_{\Sc^{\prime}_k(1)},\ldots, Z_{\Sc^{\prime}_k(j-1)} ) - H(X_k | Z_{\Sc^{\prime}_k(1)},\ldots, Z_{\Sc^{\prime}_k(j)} )  \\
%&\stackrel{\eqref{eq:HXk given Zv}}{\leq}  \Lsf(1+\asf)-\Lsf=\asf\Lsf.
\end{align*}

For any collections of sets $\Sc,\Sc^{\prime} \subseteq \Sc^{\prime}_k$ we have (which will be proved in Appendix <ref>)

\begin{align}
&H(W_k|X_k, (Z_{\Vc_1}:\Vc_1\in  \Sc ) ) + H(W_k|X_k, (Z_{\Vc_2}: \Vc_2 \in \Sc^{\prime})) \nonumber\\& \geq  H(W_k|X_k, (Z_{\Vc_0}:\Vc_0 \in \Sc\cup \Sc^{\prime}) ) +H(W_k|X_k, (Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) )
\nonumber\\& - I\left(  (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k,(Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) \right)
.\label{eq:from submodularity}
\end{align}

In addition,  we have

\begin{align}
&I\left(  (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k,(Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) \right) \\& \leq I\left(  (Z_{\Vc_1}: \Vc_1 \in \Sc  ) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k  \right) \\
&= H( (Z_{\Vc_1}: \Vc_1 \in \Sc  )| X_k)+ H((Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc) |X_k) -H( (Z_{\Vc_0}: \Vc_0 \in \Sc\cup \Sc^{\prime}  )|X_k)\\
&\leq H(  Z_{\Vc_1}: \Vc_1 \in \Sc    )+ H( Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc ) -H( (Z_{\Vc_0}: \Vc_0 \in \Sc\cup \Sc^{\prime}  )|X_k)\\
&= H(  Z_{\Vc_1}: \Vc_1 \in \Sc    )+ H( Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc ) -   H(Z_{\Vc_0}: \Vc_0 \in \Sc\cup \Sc^{\prime} ) +I( (Z_{\Vc_0}: \Vc_0 \in \Sc\cup \Sc^{\prime}  ); X_k)\\
&=I( (Z_{\Vc_0}: \Vc_0 \in \Sc\cup \Sc^{\prime}  ); X_k)\\
&=H( X_k)-H(X_k|(Z_{\Vc_0}: \Vc_0 \in \Sc\cup \Sc^{\prime}  ))\\
%& = H((Z_{\Vc_1}: \Vc_1 \in \Sc  ) |  X_k)- H((Z_{\Vc_2}: \Vc_2 \in \Sc^{\prime}  \setminus \Sc) |  X_k, (Z_{\Vc_1}: \Vc_1 \in \Sc  ) )\\
&\stackrel{\eqref{eq:HXk given Zv}}{\leq}  \Lsf(1+\asf)-\Lsf=\asf\Lsf.\label{eq:derive conditional sub}
\end{align}

By taking (<ref>) into (<ref>), we have

\begin{align}
&H(W_k|X_k, (Z_{\Vc_1}:\Vc_1\in  \Sc ) ) + H(W_k|X_k, (Z_{\Vc_2}: \Vc_2 \in \Sc^{\prime})) \nonumber\\& \geq  H(W_k|X_k, (Z_{\Vc_0}:\Vc_0 \in \Sc\cup \Sc^{\prime}) ) +H(W_k|X_k, (Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) ) -  \asf\Lsf.\label{eq:further sub}
\end{align}

Hence, by using (<ref>) iteratively, we have

\begin{align}
\sum_{j\in \left[\binom{\Ksf-1}{\Ssf-1}\right]} H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(j)\})) &\geq  H(W_k|X_k) -\left(\binom{\Ksf-1}{\Ssf-1}-1\right)  \asf\Lsf \label{eq:contra 1} \\
& =\left(1-\Big(\binom{\Ksf-1}{\Ssf-1}-1\Big)  \asf \right)\Lsf, \label{eq:contra}
\end{align}

where (<ref>) comes from the security constraint $I(W_k;X_k)=0$ and $H(W_k)=\Lsf$.[To make the derivation of (<ref>) more clear,
we first consider the first two terms on the LHS of (<ref>).
We can see that  $\big(\Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(1)\}) \big) \cup \big(\Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(2))\} \big)= \Sc^{\prime}_k$, and
$\big(\Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(1)\}) \big) \cap \big(\Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(2))\} \big)= \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(1),\Sc^{\prime}_k(2)\}$.
From (<ref>), we have $\sum_{j\in [2]} H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(j)\})) \geq H(W_k|X_k, Z_k)+ H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(1),\Sc^{\prime}_k(2)\}))-\asf\Lsf$, and we recall that $H(W_k|X_k, Z_k)=0$.
Next, from (<ref>) again,  we can lower bound the sum of $H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(1),\Sc^{\prime}_k(2)\}))$ and $H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(3)\}))$, by    $H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(1),\Sc^{\prime}_k(2),\Sc^{\prime}_k(3)\})) -\asf \Lsf$.
We repeat this  iteratively. The last (i.e., $\left(\binom{\Ksf-1}{\Ssf-1}-1\right)^{\text{th}}$) step is to lower bound the sum of $H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(1),\ldots,\Sc^{\prime}_k(\binom{\Ksf-1}{\Ssf-1}-1)\}))$ and $H(W_k|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Sc^{\prime}_k(\binom{\Ksf-1}{\Ssf-1})\}))$, by
$H(W_k|X_k) -\asf\Lsf$.
In conclusion, we can obtain (<ref>).

For each set  $\Vc \in \Sc^{\prime}_k$,   we have

\begin{align}
&H\left(W_k\Big|X_k, (W_{k_1}:k_1\in [\Ksf]\setminus \{k\}),\Big(Z_{\Vc_1}:\Vc_1 \in \binom{[\Ksf]}{\Ssf}   , \Vc_1\neq \Vc\Big) \right) \nonumber\\
%& =I(W_k;Z_{\Vc}|X_k,  (W_{k_1}:k_1\in [\Ksf]\setminus \{k\}),(Z_{\Vc_1}:\Vc_1 \in \binom{[\Ksf]}{\Ssf}, \Vc_1\neq \Vc))  \nonumber\\&+ H(W_k| X_k, (W_{k_1}:k_1\in [\Ksf]\setminus \{k\}),Z_1,\ldots,Z_{\Ksf}) \\
%&\stackrel{\eqref{eq:Marcov}}{\leq} I(W_k;Z_{\Vc}|X_k,  (W_{k_1}:k_1\in [\Ksf]\setminus \{k\}),(Z_{\Vc_1}:\Vc_1 \in \binom{[\Ksf]}{\Ssf}  , \Vc_1\neq \Vc)) \\
& \geq I\left(W_k;Z_{\Vc} \Big|X_k,  (W_{k_1}:k_1\in [\Ksf]\setminus \{k\}),\Big(Z_{\Vc_1}:\Vc_1 \in \binom{[\Ksf]}{\Ssf}, \Vc_1\neq \Vc\Big)\right)\\
& =I(W_k;Z_{\Vc}|X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Vc\}))  \label{eq:Wk's independent} \\
%&\stackrel{\eqref{eq:prove by contradiction}}{>}0, \label{eq:final contra}
& =H(W_k| X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Vc\})) -H(W_k| X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k))\\
&=H(W_k| X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \{\Vc\})),\label{eq:after sub}
\end{align}

where (<ref>) follows since $(W_{k_1}:k_1\in [\Ksf]\setminus \{k_1\})$ and $\left(Z_{\Vc_1}:\Vc_1 \in \binom{[\Ksf]\setminus \{k\}}{\Ssf}  \right)$ are independent of $(X_k, Z_k, W_k)$, (<ref>) comes from (<ref>).

On the other hand, when $\Uc_1=([\Ksf]\setminus \Vc) \cup \{k\}$ and $\Uc_2=[\Ksf]\setminus \Vc$,[This case is possible because, $|\Vc|= \Ssf \leq \Ksf-\Usf$, and thus $|[\Ksf]\setminus \Vc| \geq \Usf$.] we have

\begin{align}
0&=H\left(\sum_{k_1\in \Uc_1} W_{k_1} \Big| X_k, (X_{k_2}, Y^{\Uc_1}_{k_2} :k_2\in \Uc_2) \right)\\
&\geq H\left(\sum_{k_1\in \Uc_1} W_{k_1} \Big| X_k, (W_{k_2},Z_{k_2}:k_2\in \Uc_2)\right)\label{eq:k2functions}\\
&= H(W_k| X_k, (W_{k_2},Z_{k_2}:k_2\in \Uc_2))\\
&\geq H\left(W_k \Big|X_k, (W_{k_1}:k_1\in [\Ksf]\setminus \{k\}), \Big(Z_{\Vc_1}:\Vc_1 \in \binom{[\Ksf]}{\Ssf}, \Vc_1\neq \Vc\Big) \right),\label{eq:last term}
\end{align}

where (<ref>) follows since $(X_{k_2}, Y^{\Uc_1}_{k_2})$ is a function of $(W_{k_2},Z_{k_2})$, and (<ref>) follows since $k\notin \Uc_2$ and   $\Vc \cap \Uc_2=\emptyset$.

From (<ref>) and (<ref>), we have

\begin{align}
H(W_k| X_k, (Z_{\Vc_1}:\Vc_1 \in \Sc^{\prime}_k\setminus \Vc)) \leq 0.\label{eq:each term<0}
\end{align}

By taking (<ref>) into (<ref>), we have

\begin{align}
&1-\left(\binom{\Ksf-1}{\Ssf-1}-1 \right) \asf \leq 0,  \\
&\Longleftrightarrow \asf \geq \frac{1}{\binom{\Ksf-1}{\Ssf-1}-1 }  .\label{eq:lower bound of a}
\end{align}

Hence,     Theorem <ref> can be proved from $\Rsf_1=1+\asf$ and (<ref>).

§ PROOF OF (<REF>)

The proof of (<ref>) follows    the proof of <cit.> (which shows a generalized version of the submodularity of entropy).
More precisely,  we have

\begin{align}
&H(W_k|X_k, (Z_{\Vc_1}:\Vc_1\in  \Sc ) )-H(W_k|X_k, (Z_{\Vc_0}:\Vc_0\in  \Sc \cup \Sc^{\prime}) ) + H(W_k|X_k, (Z_{\Vc_2}: \Vc_2 \in \Sc^{\prime})) \nonumber\\
&=I(W_k;(Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime} \setminus \Sc) | X_k, (Z_{\Vc_1}:\Vc_1\in  \Sc)  )+  H(W_k|X_k, (Z_{\Vc_2}: \Vc_2 \in \Sc^{\prime})) \\
& =  I(W_k;(Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime} \setminus \Sc) | X_k, (Z_{\Vc_1}:\Vc_1\in  \Sc)  ) + H(W_k|X_k, (Z_{\Vc_0}:\Vc_0\in  \Sc \cup \Sc^{\prime}) )    \nonumber\\
& + I(W_k;(Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) | X_k, (Z_{\Vc_2}:\Vc_2\in  \Sc^{\prime})  ).  \label{eq:submod first step}
\end{align}

In addition,  we have

\begin{align}
&  I(W_k;(Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime} \setminus \Sc) | X_k, (Z_{\Vc_1}:\Vc_1\in  \Sc)  )
+I(W_k;(Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) | X_k, (Z_{\Vc_2}:\Vc_2\in  \Sc^{\prime})  ) \nonumber\\
&=I(W_k,(Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ;(Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime} \setminus \Sc) | X_k, (Z_{\Vc_5}:\Vc_5\in  \Sc \cap \Sc^{\prime})  )
\nonumber\\& - I\left(  (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k,(Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) \right)\nonumber\\&  +I(W_k;(Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) | X_k, (Z_{\Vc_2}:\Vc_2\in  \Sc^{\prime})  ) \\
& \geq  H(W_k,(Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime})| X_k, (Z_{\Vc_5}:\Vc_5\in  \Sc \cap \Sc^{\prime}) )  -
H(W_k  | X_k, (Z_{\Vc_2}:\Vc_2\in  \Sc^{\prime}))  \nonumber\\
& - I\left(  (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k,(Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) \right)\nonumber\\&  +I(W_k;(Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) | X_k, (Z_{\Vc_2}:\Vc_2\in  \Sc^{\prime})  ) \\
%& - H (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime})| X_k, (Z_{\Vc_2}:\Vc_2\in  \Sc^{\prime}))
&=  H(W_k,(Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime})| X_k, (Z_{\Vc_5}:\Vc_5\in  \Sc \cap \Sc^{\prime}) )- H(W_k | X_k, (Z_{\Vc_0}:\Vc_0\in  \Sc \cup \Sc^{\prime} )  )\nonumber \\
& - I\left(  (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k,(Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) \right)   \\
& \geq H(W_k | X_k, (Z_{\Vc_5}:\Vc_5\in  \Sc \cap \Sc^{\prime}) )- H(W_k | X_k, (Z_{\Vc_0}:\Vc_0\in  \Sc \cup \Sc^{\prime} )  )\nonumber \\
& - I\left(  (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k,(Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) \right).\label{eq:comp from sub prove}
\end{align}

By taking (<ref>) into (<ref>), we have

\begin{align}
&H(W_k|X_k, (Z_{\Vc_1}:\Vc_1\in  \Sc ) )-H(W_k|X_k, (Z_{\Vc_0}:\Vc_0\in  \Sc \cup \Sc^{\prime}) ) + H(W_k|X_k, (Z_{\Vc_2}: \Vc_2 \in \Sc^{\prime})) \nonumber\\
&\geq  H(W_k | X_k, (Z_{\Vc_5}:\Vc_5\in  \Sc \cap \Sc^{\prime}) )- I\left(  (Z_{\Vc_4}: \Vc_4 \in \Sc \setminus \Sc^{\prime}) ; (Z_{\Vc_3}: \Vc_3 \in \Sc^{\prime}  \setminus \Sc)      | X_k,(Z_{\Vc_5}: \Vc_5 \in \Sc\cap \Sc^{\prime}) \right),
\end{align}

which coincides with (<ref>).

§ PROOF OF THE SECURITY CONSTRAINT IN (<REF>) FOR THE PROPOSED SECURE AGGREGATION SCHEME

Assume that in the proposed secure aggregation scheme for Theorem <ref>, the $\Usf$-dimensional vectors $\av_{\Vc}$ where $\Vc\in \binom{[\Ksf]}{\Ssf}$ are determined, such that the constraints in (<ref>), (<ref>), and (<ref>) are satisfied.

Let us then prove that the scheme is secure.
By our construction, since the constraint in (<ref>) is satisfied,   we have

\begin{align}
I(X_1,\ldots,X_{\Ksf};W_1, \ldots, W_{\Ksf})
&= \sum_{k\in [\Ksf]} I(X_k; W_k) \label{eq:each Xk indep}\\
&=\sum_{k\in [\Ksf]} \left( H(X_k)-H(X_k| W_k) \right)\\
&=\sum_{k\in [\Ksf]} \left( \Lsf -H(X_k| W_k)\right)\label{eq:each Xk indep2}\\
&=\sum_{k\in [\Ksf]} \left( \Lsf -\Lsf \right) =0 , \label{eq:case 1 first round secrey}
\end{align}

where (<ref>) follows since $(X_1,W_1), \ldots, (X_{\Ksf},W_{\Ksf})$ are mutually independent in our scheme (Recall (<ref>) and that  $X_1,\ldots,X_{\Ksf}$ use different keys), (<ref>) follows since each $W_k$ contains $\Lsf$ uniform and i.i.d. symbols over $\mathbb{F}_{\qsf}$   and the keys are independent of $W_k$,
and (<ref>) follows since (recall that each $Z_{\Vc,k}$ where $\Vc\in \binom{[\Ksf] }{\Ssf}$ and $k\in \Vc$ contains $\Lsf/\Usf$ uniform and i.i.d. symbols over $\mathbb{F}_{\qsf}$)

\begin{align}
H(X_k| W_k)&=H\left(\bigg( W_{k,j} + \sum_{\Vc\in\binom{[\Ksf]}{\Ssf}: k \in \Vc} a_{\Vc, j} Z_{\Vc,k}: j\in [\Usf] \bigg) \bigg| (W_{k,j}:j\in [\Usf])  \right)\\
&\stackrel{\eqref{eq:key constraint}}{=} H\left(   \sum_{\Vc\in\binom{[\Ksf]}{\Ssf}: k \in \Vc} a_{\Vc, j} Z_{\Vc,k}: j\in [\Usf]    \right)\\
& \stackrel{\eqref{eq:full rank constraint}}{=}  \Lsf.
\end{align}

Hence, we have

\begin{align}
&I\left(W_1,\ldots,W_{\Ksf}; X_{1},\ldots,X_{\Ksf}, (Y^{\Uc_1}_{k}:k\in \Uc_1) \Big| \sum_{k\in \Uc_1} W_{k} \right) \nonumber\\
&=   I\left(W_1,\ldots,W_{\Ksf}; (Y^{\Uc_1}_{k}:k\in \Uc_1) \Big| \sum_{k\in \Uc_1} W_{k}, X_{1},\ldots,X_{\Ksf}\right) \label{eq:XindpendW}\\
&\leq I\left(W_1,\ldots,W_{\Ksf}; F_1,\ldots, F_{\Usf} \Big| \sum_{k\in \Uc_1} W_{k}, X_{1},\ldots,X_{\Ksf}\right)\label{eq:YfunctionF}\\
&=0, \label{eq:FfunctionXW}
\end{align}

where (<ref>) comes from (<ref>), (<ref>) comes from  $(Y^{\Uc_1}_{k}:k\in \Uc_1) $ are in the linear space spanned by  $F_1,\ldots,F_{\Usf}$ and thus are determined by $F_1,\ldots,F_{\Usf}$, (<ref>) follows since $F_1,\ldots,F_{\Usf}$ can be recovered from $\sum_{k\in \Uc_1} W_{k}$ and $\sum_{k\in \Uc_1} X_{k}$. Hence, the security constraint in (<ref>) is satisfied.

§ PROOF OF LEMMA <REF>

Consider one set $\Ac \subseteq [\Ksf]$ where $|\Ac|=\Usf$. Assume that $\Ac=\{\Ac(1),\ldots,\Ac(\Usf)\}$  where $\Ac(1)<\cdots<\Ac(\Usf)$.
We also assume that the sets in

$$\Gc_2=\left\{    [\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\} : j\in ([\Ksf-\Usf] \cup [2\Ksf-2\Usf+1: \Ksf])  \right\}$$

are $\Gc_{2,1},\ldots,\Gc_{2,\Ksf-\Usf}, \Gc_{2,2\Ksf-2\Usf+1},\ldots,\Gc_{2,\Ksf} $,  where $\Gc_{2,j}=[\Ksf-\Usf+1:2\Ksf-2\Usf] \cup \{j\}$ for each $j\in ([\Ksf-\Usf] \cup [2\Ksf-2\Usf+1: \Ksf])$.

Recall that by our construction,
for each user $k\in[\Ksf-\Usf]$,  $\sv_{k}$ is a left null space vector of the matrix in (<ref>).
Note that each column of the matrix in (<ref>) is $\av_{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf]}$ where $j\in ([\Ksf-\Usf]\setminus \{k\})\cup [2\Ksf-2\Usf+1:\Ksf]$. In addition, it can be seen  that $\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf]$ is in $\Gc_2$; thus
each element  of  $\bv_{\{j\}\cup [\Ksf-\Usf+1:2\Ksf-2\Usf]}$ is chosen uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.
For each user   $k\in [\Ksf-\Usf+1:\Ksf]$, from (<ref>) we have that $\sv_{k}=\ev^{\text{T}}_{\Usf,k-\Ksf+\Usf}$.

Hence, the determinant of  the matrix

\begin{align}
\begin{bmatrix}
\sv_{\Ac(1)} \\
\cdots \\
\sv_{\Ac(\Usf)}
\end{bmatrix}
\label{eq:U vectors matrix}
\end{align}

could be seen as $D_{\Ac}= \frac{P_{\Ac}}{Q_{\Ac}}$, where $P_{\Ac}$ and $Q_{\Ac}$ are multivariate polynomials whose variables are the elements in  $\bv_{\Vc}$ where $\Vc \in \Gc_2$.

Since   each  element in   $\bv_{\Vc}$ where $\Vc \in \Gc_2$
is uniformly and i.i.d. over $\mathbb{F}_{\qsf}$ where   $\qsf$ is large enough,
by the  Schwartz-Zippel Lemma <cit.>, if we can further show that the multivariate polynomial  $P_{\Ac}$ is   non-zero      (i.e., a multivariate polynomial whose coefficients are not all $0$), the probability that this  multivariate polynomial is equal to $0$ over all possible realization of the elements in  $\bv_{\Vc}$ where $\Vc \in \Gc_2$ goes to $0$ when $\qsf$ goes to infinity, and thus
the matrix in (<ref>) is full rank with high probability.
So in the following, we need to show that $P_{\Ac}$ is   non-zero.
For the matrix (whose dimension is $\Usf \times \Usf$)

\begin{align}
{\bf G}&=
\begin{bmatrix}
\av_{\Gc_{2,1}},\ldots, \av_{\Gc_{2,\Ksf-\Usf}}, \av_{\Gc_{2,2\Ksf-2\Usf+1}},\ldots, \av_{\Gc_{2,\Ksf}}
\end{bmatrix}\\
\begin{blockarray}{ccccccccc}
& c_1 & c_2 & \cdots & c_{\Ksf-\Usf} & c_{\Ksf-\Usf+1} & c_{\Ksf-\Usf+2} & \cdots & c_{\Usf} \\
\begin{block}{c[cccccccc]}
r_1 & * & * & \cdots & * & * & * & \cdots & * \\
r_2 &  * & * & \cdots & *& * & * & \cdots & *\\
\vdots &  \vdots& \vdots & \ddots & \vdots & \vdots &  \vdots & \ddots &  \vdots\\
r_{\Ksf-\Usf} & * & * & \cdots & *  &* & * & \cdots & *\\
r_{\Ksf-\Usf+1} & 0 & 0 & \cdots & 0  &* & 0 & \cdots & 0\\
r_{\Ksf-\Usf+2} &  0 & 0 & \cdots & 0&0 & * & \cdots & 0\\
\vdots &  \vdots& \vdots & \ddots & \vdots & \vdots &  \vdots & \ddots &  \vdots \\
r_{\Usf} &  0 & 0 & \cdots & 0&0 & 0 & \cdots & *\\
\end{block}
\end{blockarray}
\end{align}

where $r_1,\ldots,r_{\Usf}$ denote the labels of rows, $c_1,\ldots,c_{\Usf}$ denote   the labels of columns, and each `$*$' denotes a    symbol uniformly and i.i.d. over $\mathbb{F}_{\qsf}$.
With a slight abuse of notation, we define that ${\bf G} \setminus  \av_{\Gc_{2,j}} $ where $j\in [\Ksf-\Usf]\cup [2\Ksf-2\Usf+1:\Ksf]$ as the column-wise sub-matrix
of ${\bf G}$ by removing the column $\av_{\Gc_{2,j}}$.
For each $k\in (\Ac \cap [\Ksf-\Usf])$,  by our construction, $\sv_k$ is a  left null space vector of ${\bf G} \setminus  \av_{\Gc_{2,k}}$.
Hence, to   show that $P_{\Ac}$ is   non-zero, we need to find one realization of the `$*$'s in ${\bf G}$ such that