,R^{(2)}_{C-1}\}$ to each selected client as well. Thus, each client obtains a new set of symbols with a set length $C$ through element-wise summation within the field, 
\begin{align}
    R_i = R^{(1)}_i + R^{(2)}_i, \quad i = 0,1,\dots,C-1
\end{align}
Subsequently, each client appends one more symbol $R_C$ to the existing set such that the sum equals zero, i.e., $\sum_{i \in [C]} R_i = 0$. Since the two random sets that are transmitted from the server to each client are the same, these selected clients ultimately share a common randomness set $\{R_0,R_1,\dots,R_C\}$. Further, the individual databases in the server have no knowledge about this set because of the one-time pad encryption.

We next consider the first type of common randomness allocation, i.e., the allocation of $c$. Note that $c$ needs to be uniform in $\mathbb{F}_q \backslash \{0\}$. We could use a modified version of the above method as follows: Each database individually selects a random symbol from $\mathbb{F}_q$ under a uniform distribution and then broadcasts its selected symbol to each client. The global common randomness symbol $c$ is calculated as the sum of the two random values that are transmitted from the two databases. However, $c$ now can take the value $0$ with probability $\frac{1}{|q|}$, thus, the constraint that $c$ is uniformly distributed over $\mathbb{F}_q \backslash \{0\}$ is not immediately satisfied. The two databases in the server can repeat this procedure until $c$ falls into the allowed region, which would require feedback from the clients as explained above.  

In order to overcome this shortcoming, we propose a novel common randomness allocation method via a broadcast variation of the RSPIR scheme introduced in \cite{RSPIR}. We consider a RSPIR problem with $N = 2, K = |q| - 1, L = 1$ and make use of the potentially suboptimal\footnote{This scheme was proved to be optimal for $K=2, 3$, but is a valid scheme for any $K$.} RSPIR achievable scheme provided in \cite[Section~V]{RSPIR}. The corresponding message set stored in the two databases is set as $W_1 = 1, W_2 = 2, \dots, W_{|q|-1} = |q|-1$. We note that there is no need to protect the privacy of the remaining messages at this point since all these messages can be globally known to the clients. As a consequence, the required server-side common randomness in the original RSPIR problem \cite{RSPIR} can be discarded.\footnote{The new idea proposed here seems to be closer to the definition of random private information retrieval (RPIR) as opposed to random \emph{symmetric} private information retrieval (RSPIR) studied in \cite{RSPIR}. RPIR and RSPIR can be further studied to design more efficient and powerful common randomness construction among the clients. We leave this as an interesting future research direction.} Database $1$ has the following set of messages and broadcasts one of them randomly to active clients, 
\begin{align}
    c^{(1)}_1 &= \emptyset \\
    c^{(1)}_2 &= (W_1 + W_2, W_2 + W_3, \dots, W_{|q|-2} + W_{|q|-1}) \\
    c^{(1)}_3 &= (W_1 + W_3, W_2 + W_4, \dots, W_{|q|-2} + W_1) \\
    \vspace{-0.25em}
    &\;\; \vdots \notag \\
    \vspace{-0.25em}
    c^{(1)}_{|q|-1} &= (W_1 + W_{|q|-1}, W_2 + W_1, \dots, W_{|q|-2} + W_{|q|-3}) 
\end{align}
Similarly, database $2$ has the following set of messages and broadcasts one of them randomly to active clients,
\begin{align}
    c^{(2)}_1 &= W_1 \\
    c^{(2)}_2 &= W_2 \\
    \vspace{-0.25em}
    &\;\; \vdots \notag \\
    \vspace{-0.25em}
    c^{(2)}_{|q|-2} &= W_{|q|-2}  \\
    c^{(2)}_{|q|-1} &= W_{|q|-1} 
\end{align}
By applying the decoding procedure in the RSPIR approach in \cite{RSPIR}, all clients will be able to obtain the same global common randomness symbol $c$ that is uniformly distributed over the set $\mathbb{F}_q \backslash \{0\}$. Moreover, the obtained random symbol $c$ will be unknown to each individual database in the server due to the user privacy constraint in RSPIR \cite{RSPIR}.

\subsection{Private Set Union (FSL-PSU) Phase} \label{FSL-PSU Phase}
After the FSL-CRG phase is completed, each selected client will obtain a global common randomness symbol $c$ that is uniformly distributed over $\mathbb{F}_q \backslash \{0\}$, and a set of common randomness symbols $\{u^{\langle [C] \rangle}_k\!\!: k \in [K]\}$ in which the identity $\sum_{i \in [C]} u^{\langle i \rangle}_k = 0$ is true for all $k \in [K]$, and another set of common randomness symbols $\{u_k\!\!: k \in [K]\}$ that are all uniformly distributed over $\mathbb{F}_q$. Following our distributed FSL model in Section~\ref{FSL Formulation}, $C$ selected clients in this round of FSL process are divided into two groups $\mathcal{C}_1$ and $\mathcal{C}_2$. The clients in $\mathcal{C}_1$ send their answers to database $1$ in the server, while the clients in $\mathcal{C}_2$ send their answers to database $2$ in the server. Then, the $i$th client in $\mathcal{C}_1$, after mapping its desired submodel index set $\Gamma^{\langle i \rangle}$ into a corresponding incidence vector $Y^{\langle i \rangle}$, constructs its answer as,
\begin{align}
    A^{\langle i \rangle,(1)}_{U,1} = \{c(Y^{\langle i \rangle}_1+u^{\langle i \rangle}_1),c(Y^{\langle i \rangle}_2+u^{\langle i \rangle}_2),\dots,c(Y^{\langle i \rangle}_K+u^{\langle i \rangle}_K)\}
\end{align}
Similarly, the $i$th client in $\mathcal{C}_2$ constructs its answer as,
\begin{align}
    A^{\langle i \rangle,(2)}_{U,1} = \{c(Y^{\langle i \rangle}_1+u^{\langle i \rangle}_1),c(Y^{\langle i \rangle}_2+u^{\langle i \rangle}_2),\dots,c(Y^{\langle i \rangle}_K+u^{\langle i \rangle}_K)\}
\end{align}
Once the first database in the server receives all the answers from its associated clients in $\mathcal{C}_1$, it produces a corresponding response to be downloaded as, 
\begin{align}
    D^{\langle \theta_1 \rangle,(1)}_{U,2} = \biggl\{c\sum_{i \in \mathcal{C}_1} (Y^{\langle i \rangle}_k + u^{\langle i \rangle}_k)+S_k\!\!: k \in [K] \biggr\} 
\end{align}
where $\{S_k\!\!: k \in [K]\}$ are shared server-side common randomness symbols that are uniformly selected from $\mathbb{F}_q$ as well. This produced response $D^{\langle \theta_1 \rangle,(1)}_{U,2}$ will then be downloaded by a random client whose index $\theta_1$ belongs to $\mathcal{C}_1$. Afterwards, the $\theta_1$th client processes the received response by adding extra common randomness to it, and then, forwards the following answer to both databases in the server,
\begin{align}
    A^{\langle \theta_1 \rangle,([2])}_{U,2} = \biggl\{c\sum_{i \in \mathcal{C}_1} (Y^{\langle i \rangle}_k + u^{\langle i \rangle}_k)+u_k+S_k\!\!: k \in [K] \biggr\} 
\end{align}
Likewise, the second database produces a response to be downloaded as follows, after receiving all the answers in the first step from the client group $\mathcal{C}_2$,
\begin{align}
    D^{\langle \theta_2 \rangle,(2)}_{U,2} = \biggl\{c\sum_{i \in \mathcal{C}_2} (Y^{\langle i \rangle}_k + u^{\langle i