On the Asymptotic Capacity of Information-Theoretic Privacy-Preserving Epidemiological Data Collection

Abstract

The paradigm-shifting developments of cryptography and information theory have focused on the privacy of data-sharing systems, such as epidemiological studies, where agencies are collecting far more personal data than they need, causing intrusions on patients’ privacy. To study the capability of the data collection while protecting privacy from an information theory perspective, we formulate a new distributed multiparty computation problem called privacy-preserving epidemiological data collection. In our setting, a data collector requires a linear combination of K users’ data through a storage system consisting of N servers. Privacy needs to be protected when the users, servers, and data collector do not trust each other. For the users, any data are required to be protected from up to E colluding servers; for the servers, any more information than the desired linear combination cannot be leaked to the data collector; and for the data collector, any single server can not know anything about the coefficients of the linear combination. Our goal is to find the optimal collection rate, which is defined as the ratio of the size of the user’s message to the total size of downloads from N servers to the data collector. For achievability, we propose an asymptotic capacity-achieving scheme when $E<N-1$, by applying the cross-subspace alignment method to our construction; for the converse, we proved an upper bound of the asymptotic rate for all achievable schemes when $E<N-1$. Additionally, we show that a positive asymptotic capacity is not possible when $E\ge N-1$. The results of the achievability and converse meet when the number of users goes to infinity, yielding the asymptotic capacity. Our work broadens current researches on data privacy in information theory and gives the best achievable asymptotic performance that any epidemiological data collector can obtain.

1. Introduction

During any prevention and control period in an epidemic, strengthening the protection of personal information is conducive not only to safeguarding personal interests, but also better controlling the development of the epidemic. Differently from the collection of other homogeneous data, such as the large-scale labeled sample obtained in machine learning, the characteristics of medical or epidemiological data collection are reflected in the following aspects: (1) In order to establish a surveillance system for a dynamical group of people to collect syndromic data, the sample size is always changing [1,2]; (2) Data sharing and early response are critical in containing the spread of highly infectious diseases, such as COVID-19. This requires the data stored in the database to be updated to track real-time changes in symptoms, severity, or other disease-related patterns [3,4]; (3) Some of the epidemiological data, such as the locations of infected individuals, the blood oxygen saturation levels of patients with respiratory diseases after medication, or the physical condition monitoring data after viral infection, are related to the user’s privacy, so a “privacy-first” approach which uses dynamic identifiers and stores their data in a cryptographically secure manner is needed [5]. Hence, for these factors of epidemiological data collection, the key to ensuring the efficiency of information sharing and privacy protection is to maximize the balance between data privacy and collection rate in epidemic analysis.

While the data collection from public health authorities and the open-source access to researchers can provide convenience to epidemiologists, these strategies may also significantly intrude upon citizens’ privacy. Some of these individuals were affected by unwanted privacy invasion, and the ubiquitous data surveillance devices certainly exacerbate those concerns. Therefore, the responsible use of shared data and algorithms, the compliance with data protection regulations, and the appropriate respect for privacy and confidentiality have become important topics in epidemiological data collection [6,7]. In 2014, the Global System for Mobile Communications (GSM) Association outlined some privacy standards for data-processing agencies regarding mobile phone data collection in response to the Ebola virus [8]. Some other methods that effectively guarantee user privacy include: encryption mechanisms [9], the privacy-aware energy-efficient framework (P-AEEF) protocol [10], the differential privacy-based classification algorithm [11], and the spatio-temporal trajectory method [12]. Moreover, unauthorized agencies, malicious hackers, and unidentified attacks, such as traffic analysis attacks, fake-node injection, and selective forwarding, may also eavesdrop on users’ data under the current ambiguous and non-uniform collecting algorithms [13]. To avoid the leakage of information from malicious collecting servers or untrusted access, the privacy of data needs to be ensured during data storage and processing.

In line with ensuring the security and privacy of user data, epidemiological data collection also requires the protection of data collectors. In accessing public databases, various epidemiological investigation agencies have different requirements for data privacy. For example, many epidemiological surveys are conducted by governments, universities, research institutes, pharmaceutical companies, and private institutions. Access to public data may reveal these agencies’ data preferences, resulting in information leakage. Therefore, the private-preserving epidemiological data collection includes the user’s privacy regarding the storage and data collector, along with the data collector’s privacy in data storage.

In epidemiological modeling, many recent studies have shown that various models have a good fitting effect on the nature of epidemics, such as the Bayesian model [14] and deep learning models, including multi-head attention, long short-term memory (LSTM), and the convolutional neural network (CNN) [15]. Additionally, when it comes to privacy and security concerns, some work conducted in computer science, cryptography, and information theory provides handy tools to model and solve such problems. The privacy leakage was modeled in differential privacy [16], k-anonymity [17], t-closeness [18], interval privacy [19], etc. With those concerns and analysis, several studies in cryptography and information theory have focused on the issue of sharing messages to untrusted agencies, such as distributed linear separable computation [20,21,22], secured matrix multiplication [23,24,25], secure aggregation [26], participatory sensing [27], and private information retrieval [28,29,30,31]. Specifically, a cryptographical epidemiological model with data security and privacy called RIPPLE was analyzed [32]. This model enables the execution of epidemiological models based on the most-recent real contact graph while keeping all the users’ information private. As an extension to the model, the data collector uses the sum private information retrieval (PIR) schemes to obtain the statistical data, which is described as the sum of a set of elements from a database.

Inspired by the cryptographical epidemiological model in [32], we propose an information-theoretic privacy-preserving epidemiological-data-collection problem, described as follows. We have a large and changing number of users sharing their real-time epidemiological data to N servers. The server will update its database once new data are uploaded. The storage of those users’ data is also open to all authorized data collectors. For any data collector who desires only some statistical feature, rather than all the data, it directly retrieves the statistic from N servers. We designed the protocol of the interaction between the N servers and the data collector so that when all N servers honestly answer the queries from the data collector, then the desired statistical data can be correctly decoded at the data collector. To simplify the problem, we assume the desired statistics to be the linear combinations of users’ personal data. The privacy of this model is reflected in the following three aspects: (1) The privacy of users’ data against the data collector: after downloading all answers from the servers, the data collector can decode the desired data without learning anything about the irrelevant details of the users’ personal information. (2) The privacy of users’ data against servers: for any user successfully sharing the data to all N servers, the personal information of the user is still confidential, even if of any up to $E(E<N)$ servers collude. (3) The privacy of the data collector’s preference against servers: the protocol between data collector and servers should promise that any single server cannot know any preference of the desired statistical data from the query generated by the data collector. In our paper, we take the above privacy concerns into consideration and analyze the data collector’s ability of privately receiving the shared data, with respect to the number of symbols it needs to download.

The remainder of the paper is organized as follows: In Section 2, we introduce an information-theoretic description of the privacy-preserving epidemiological-data-collection problem, and we define the communication rate and capacity of our problem. In Section 3, we give a closed-form expression for the asymptotic capacity, which is the main result of the paper. In Section 4, we derive a converse proof for $E<N-1$, which provides an upper bound on the asymptotic capacity when the number of users tends to infinity. An asymptotically capacity-achieving scheme using the technique of cross-subspace alignment when $E<N-1$ is given in Section 5, and in Section 6, we prove that the problem is not asymptotically achievable when $E=N-1$. Finally, in Section 7, we summarize our results and suggest some open problems in this field.

2. System Model

We formulate the privacy-preserving epidemiological-data-collection problem over a typical distributed, secure computation system, in which there are K users, N servers, and a data collector; and the number of users ($K\in N_{+}$) is a large-enough integer. Here and throughout the paper, we assume that all of the random symbols in our system are generated by a large-enough finite field ${\mathbb{F}}_q$, and we standardize the entropy of any uniformly distributed symbol to be 1 by taking the term log in the entropy, conditional entropy, and mutual information to be base q. The model is depicted in Figure 1.

Let $W_1,\cdots ,W_K$ be K independent messages, where $W_k,k\in [1:K]$ denotes the epidemiological data of user k and $W_k\in G{F}_q^{L\times 1},L\in {\mathbb{N}}_{+}$ is an $L\times 1$ vector with L i.i.d. uniform symbols from the finite field $G{F}_q$—i.e.,

$$\begin{array}{cc}\hfill & H\left(W_{[1:K]}\right)={\sum }_{k=1}^{K}H\left(W_k\right),\hfill \\ \hfill & H\left(W_k\right)=L,\forall k\in [1:K].\hfill \end{array}$$

(1)

The data-collection problem contains two phases: the upload phase and the computation phase. The upload phase starts when the user is required to update its data to each of the N servers. Before uploading, user k knows nothing about the contents of other users’ epidemiological data. While uploading their personal data, the users would like to keep his/her message private against E$(E\le N,E\in \mathbb{N})$ colluding servers; i.e., any of up to E servers will learn nothing about the messages uploaded by K users. For any $n\in [1:N]$, let $D_{k,n}\in \mathfrak{D}$ denote the uploaded message from the k-th user to the n-th server. We have the following equality called the privacy constraint of the users against E servers:

$$\begin{array}{c}\hfill I(D_{k,\mathcal{E}};W_k)=0,\forall k\in [1:K],\forall \mathcal{E}\subseteq [1:N],\left|\mathcal{E}\right|\le E.\end{array}$$

(2)

For any $k\in [1:K]$, let $Z_k\in {\mathfrak{Z}}_k$ denote a random variable privately generated by user k, and its realization is not known to any of the N servers. User k utilizes the user-side randomness $Z_k$ to encipher the message $W_k$; i.e., for any user k, there exist N functions ${\left\{d_{k,n}\right\}}_{n\in [1:N]}$ such that $d_{k,n}(W_k,Z_k)=D_{k,n}$, where $d_{k,n}:G{F}_q^L\times {\mathfrak{Z}}_k\to \mathfrak{D}$ is the encoding function from the user k to the server n. We have

$$\begin{array}{c}\hfill H\left(D_{k,[1:N]}\right|W_k,Z_k)=0,\forall k\in [1:K].\end{array}$$

(3)

When the servers receive the updated data from users, the old contents of the server will be replaced with the new contents, and all servers will be ready for the computation phase and allow the access of data updated by data collectors.

The computation phase starts when a data collector would like to compute statistical data of the current epidemiological database. To simplify our problem, we only consider statistical data to be a linear combination of all messages $W_{\left[K\right]}$. Let $W^{\mathbf{f}}$ and $\mathbf{f}$ be the statistical data and the corresponding coefficient vector. Then, we have

$$\begin{array}{c}\hfill W^{\mathbf{f}}={\mathbf{f}}^T\left[\begin{array}{c}{W}_1\\ ⋮\\ W_K\end{array}\right]=\sum _{k=1}^K{f}_k{W}_k,\end{array}$$

(4)

where $W^{\mathbf{f}}\in G{F}_q^L$ has the same number of symbols with the message length, and $\mathbf{f}\in G{F}_q^K$ contains K elements in the finite field $G{F}_q$. In our setting, the coefficient vector $\mathbf{f}$ only contains the preference of the data collector among K user’s epidemiological data records. Therefore, the value of $\mathbf{f}$ does not depend on the users’ messages $W_{[1:K]}$ or the storage of N servers: ${\left\{D_{k,n}\right\}}_{k\in [1:K],n\in [1:N]}$.

Let $Z^{\prime }\in \mathcal{Z}$ denote a random variable privately generated by the data collector, and its realization is not available to any of the N servers and K users. In the computation phase, the data collector with its preference vector $\mathbf{f}$ utilizes the randomness $Z^{\prime }$ to generate its queries to N servers. Assume that the query from the data collector to the n-th server is denoted as $Q_n^{\mathbf{f}}\in {\mathfrak{Q}}_n$. Then, the data collector uses the strategy g to map the randomness and the coefficient to the queries, such that

$$\begin{array}{c}\hfill g(\mathbf{f},Z^{\prime })={\left\{\begin{array}{c}{Q}_1^{\mathbf{f}}{Q}_2^{\mathbf{f}}\cdots Q_N^{\mathbf{f}}\end{array}\right\}}^T,\end{array}$$

where $g:G{F}_q^K\times \mathcal{Z}\to {\prod }_{n=1}^N{\mathfrak{Q}}_n$ is the encoding function from the data collector to the servers. Hence, we have

$$\begin{array}{c}\hfill H\left(Q_{[1:N]}^{\mathbf{f}}\right|Z^{\prime },\mathbf{f})=0.\end{array}$$

(5)

Since the randomness $Z^{\prime }$ and queries $Q_{[1:N]}^{\mathbf{f}}$ are generated privately, and the user-side data and randomness $W_{[1:K]},Z_{[1:K]}$ are already known before the computation phase starts, the data collector has no knowledge of $W_{[1:K]},Z_{[1:K]}$ when the queries $Q_{[1:N]}^{\mathbf{f}}$ are generated. Thus, we have

$$\begin{array}{c}\hfill I(W_{[1:K]},Z_{[1:K]};Q_{[1:N]}^{\mathbf{f}},Z^{\prime })=0.\end{array}$$

(6)

Upon receiving the query $Q_n^{\mathbf{f}}$, the n-th server will send an answer $A_n^{\mathbf{f}}$ back to the data collector according to the storage of the n-th server. We assume that there is no drop-out in the model—i.e., each server n will successfully return its answer to the data collector. Let $A_n^{\mathbf{f}}\in {\mathfrak{A}}_n$ be the answer from the n-th server to the data collector, and then for any $n\in [1:N]$, there exists a deterministic function $a_n^{\mathbf{f}}:{\mathfrak{Q}}_n\times {\mathfrak{D}}^K\to {\mathfrak{A}}_n,$ such that $A_n^{\mathbf{f}}=a_n^{\mathbf{f}}(Q_n^{\mathbf{f}},{\left[\begin{array}{c}{D}_{1,n}{D}_{2,n},\cdots ,D_{K,n}\end{array}\right]}^T),\forall n\in [1:N]$. Hence,

$$\begin{array}{c}\hfill H\left(A_n^{\mathbf{f}}\right|Q_n^{\mathbf{f}},D_{[1:K],n})=0,\forall n\in [1:N].\end{array}$$

(7)

We would like to design a scheme $\varphi ={\{d_{k,n},g,a_n^{\mathbf{f}}\}}_{k\in [1:K],n\in [1:N],\mathbf{f}\in G{F}_q^K}$ in the upload and computation phases so that the following three constraints can be achieved. Firstly, the data collector is able to reconstruct the desired message from all the information it has received, which we call the decodability constraint. Let $\psi$ be the reconstruction function of the data collector, where $\psi :{\prod }_{n=1}^N{\mathfrak{A}}_n\times {\prod }_{n=1}^N{\mathfrak{Q}}_n\times G{F}_q^K\times \mathcal{Z}\to G{F}_q^L$. We have

$$\begin{array}{c}\hfill {\widehat{W}}^{\mathbf{f}}=\psi (A_{[1:N]}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},\mathbf{f},Z^{\prime }).\end{array}$$

(8)

Let $P_e$ be the probability of decoding error achieved by a given scheme $\varphi$ and decoding function $\psi$. We obtain

$$\begin{array}{c}\hfill P_e(\varphi ,\psi )=\underset{\mathbf{f}}{max}\mathrm{Pr}\{{\widehat{W}}^{\mathbf{f}}\ne W^{\mathbf{f}}\}.\end{array}$$

According to Fano’s inequality, the decodability constraint is equivalent to

$$\begin{array}{cc}\hfill H\left(W^{\mathbf{f}}\right|A_{[1:N]}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })=& o\left(L\right),\forall \mathbf{f}\in G{F}_q^N,\hfill \end{array}$$

(9)

when $P_e\to 0$, where $o\left(L\right)$ denotes any possible function $h:{\mathbb{N}}_{+}\to \mathbb{R}$ of L satisfying $\underset{L\to \infty }{lim}\frac{h\left(L\right)}{L}=0$.

The second constraint guarantees the data privacy of K users against the data collector. The privacy leakage to the data collector is unavoidable, as the data collector must learn some statistical data of the users. This constraint requires that the data collector can learn nothing about the information of the K users other than the desired data $W^{\mathbf{f}}$. We have

$$\begin{array}{cc}\hfill I(W_{[1:K]};A_{[1:N]}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime }|W^{\mathbf{f}})=& 0.\hfill \end{array}$$

(10)

To protect the privacy of data collector, the third constraint requires the coefficient vector $\mathbf{f}$ of the data collector to be indistinguishable from the perspective of each server; i.e., for any different (linearly independent) coefficient vectors $\mathbf{f}$ and ${\mathbf{f}}^{\prime }$ from the same scheme $\varphi$, the queries to every single server are identically distributed, so that any server cannot deduce $\mathbf{f}$ merely from the query and storage without communicating to other servers. Hence, we have

$$\begin{array}{c}\hfill (A_n^{\mathbf{f}},Q_n^{\mathbf{f}},W_{[1:K]})\sim (A_n^{{\mathbf{f}}^{\prime }},Q_n^{{\mathbf{f}}^{\prime }},W_{[1:K]}),\forall \mathbf{f},{\mathbf{f}}^{\prime }\mathrm{linear}\mathrm{independent}\end{array}$$

(11)

where $A\sim B$ means that the random variables A and B have the same distribution. This constraint is called the privacy constraint of the data collector against non-colluding servers.

The reason why in the upload phase, we consider up to E servers may collude, and in the computation phase, we consider non-colluding servers to be defined by the following: the upload phase and the computation phase do not always occur at the same time. For example, the users are required to upload their epidemiological data on a regular basis, and the data collector may start his/her queries of certain statistics at relatively random times. Due to the dynamic topology of the servers, the numbers of colluding servers may be different during the uploading phase and the computation phase. Our work assumes that the servers are non-colluding in the computation phase, since the servers may be more interested in the epidemiological data than the data collector’s interest. If $E=1$, then we have a model where the servers are non-colluding in both the upload phase and the computation phase.

For any scheme $\varphi ={\{d_{k,n},g,a_n^{\mathbf{f}}\}}_{k\in [1:K],n\in [1:N],\mathbf{f}\in G{F}_q^K}$ that satisfies the above decodability constraint, i.e., (9), and the privacy constraints, i.e., the privacy constraint of the users against E servers (2), the privacy constraint of the users against the data collector (10), and the privacy constraint of the data collector against the non-colluding servers (11), its communication rate is characterized by the number of symbols the data collector decodes per download symbol—i.e.,

$$\begin{array}{c}\hfill R:=\frac{L}{{\sum }_{n=1}^{N}H\left(A_n^{\mathbf{f}}\right)}.\end{array}$$

(12)

It is worth noticing that R is not a function of $\mathbf{f}$ due to (11).

A rate R is said to be ($ϵ$-error) achievable if there exists a sequence of schemes indexed by L with their communication rate less than or equal to R where the probability of error $P_e$ goes to zero as $L\to \infty$. The $ϵ$-error capacity of this random secure aggregation problem is defined as the supremum of all $ϵ$-error achievable rates, i.e., $C:=supR$, where the supremum is over all possible $ϵ$-error achievable schemes.

3. Main Result

For the information-theoretical framework of our privacy-preserving epidemiological-data-collection problem presented in Section 2, our main result is the characterization of the asymptotic capacity when $K\to \infty$ for any $N\in {\mathbb{N}}_{+}$ and $E\in \mathbb{N}$.

To begin with, we show that the problem is infeasible when $N=1$ or $N=E$, since in these cases, some constraints of our setting contradict each other, and no scheme can satisfy all the constraints. Firstly, when there is only one server, the privacy of users against the data collector and the privacy of data collector against servers will conflict with each other. The reason is as follows. First, according to (11), the answer A will be given that for two different $\mathbf{f},{\mathbf{f}}^{\prime }$, the distribution of A is the same. Second, the decodability (9) guarantees that $W^{\mathbf{f}}$ can be derived from A. Then, $W^{{\mathbf{f}}^{\prime }}$ can be derived from A, which contradicts the privacy of users against the data collector.

Moreover, when $E=N$, the decodability constraint and the privacy of users against the servers will conflict with each other. The reason is as follows. First, the answers $A_{[1:N]}^{\mathbf{f}}$ from N servers are given by the queries $Q_{[1:N]}^{\mathbf{f}}$ and the storage $D_{[1:K],[1:N]}$ according to (7), so there is a Markov chain $W_{[1:K]}\to (Q_{[1:N]}^{\mathbf{f}},D_{[1:K],[1:N]})\to A_{[1:N]}^{\mathbf{f}}$. Second, when $E=N$, $Q_{[1:N]}^{\mathbf{f}}$ and $D_{[1:K],n}$ are independent from $W_{[1:K]}$ according to (6) and (2), which contradicts the decodability constraint as $A_{[1:N]}^{\mathbf{f}}$ is independent from the database $W_{[1:K]}$. Therefore, no scheme can simultaneously satisfy all the constraints in a single-server or $E=N$ scenario, and there does not exist a positive capacity.

The following theorem gives the asymptotic capacity of private-preserving epidemiological data collection for an infinitely large K, where we have $N\ge 2,$$E<N$ servers.

Theorem 1.

Consider E as a non-negative number, and there are $N\ge 2$ servers. When $E<N$, and the number of users $K\to \infty$, the asymptotic capacity of the secure privacy-preserving epidemiological-data-collection problem is

$$\begin{array}{c}\hfill \underset{K\to \infty ,L\to \infty }{lim}C=\left\{\begin{array}{cc}\frac{N-E-1}{N},\hfill & \mathit{if}E<N-1\hfill \\ 0,\hfill & \mathit{otherwise}\hfill \end{array}\right..\end{array}$$

(13)

When $E<N-1$, the converse proof of Theorem 1 will be given in Section 4, and the achievability proof will be given in Section 5 for any finite $K\in {\mathbb{N}}_{+}$. When $K\to \infty$, our scheme in Section 5 remains achievable at the same rate, and the performance of the achievability and converse will meet. When $E=N-1$, the proof of the zero asymptotic capacity is given in Section 6.

Remark 1.

From Theorem 1, we can see a threshold in the asymptotic capacity on the number of the maximized possible colluding servers E. When $E\ge N-1$, there is no scheme with a positive asymptotic capacity; when $E<N-1$, the asymptotic capacity is a decreasing function of E. When N approaches infinity while E is a constant, the asymptotic capacity approaches one.

Remark 2.

When the number of users K is a finite integer, the achievability and converse results do not always meet. From our converse proof in Section 4, the upper bound we give for finite K depends on the value of K. However, the performance (i.e., achievable rate) of our scheme in Section 5 is irrelevant to K, even though the scheme we propose is different for the finite $K\in {\mathbb{N}}_{+}$. How to close the gap between the upper and lower bounds when K is finite is still an open problem.

4. Proof of Theorem 1: Converse When $\mathit{E}\mathbf{<}\mathit{N}\mathbf{-}\mathbf{1}$

We give the converse proof of Theorem 1 when $E<N-1$ in this section. The converse allows any feasible scheme $\varphi$, and we give an upper bound over the rates of all possible schemes. We start with the following lemma, which states an iterative relationship among the number of linear combinations of the users’ messages.

Lemma 1.

Consider K linear independent vectors ${\mathbf{f}}_1,{\mathbf{f}}_2,\cdots ,{\mathbf{f}}_K\in G{F}_q^K$. Let $\mathcal{E}$ be a set and $\mathcal{E}\subseteq [1:N]$, $\left|\mathcal{E}\right|=E$. We have

$$\begin{array}{cc}\hfill & H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}_k}\right|W^{{\mathbf{f}}_1},\cdots ,W^{{\mathbf{f}}_k},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_k},Z^{\prime })\hfill \\ \hfill & \ge \frac{L}{N-E}+\frac{1}{N-E}H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}_{k+1}}\right|W^{{\mathbf{f}}_1},\cdots ,W^{{\mathbf{f}}_{k+1}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_{k+1}},Z^{\prime })-o\left(L\right).\hfill \end{array}$$

(14)

Proof. 

According to our problem setting, we have

$$\begin{array}{cc}\hfill & (N-E)H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}_k}\right|W^{{\mathbf{f}}_1},\cdots ,W^{{\mathbf{f}}_k},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_k},Z^{\prime })\hfill \end{array}$$

$$\begin{array}{cc}\hfill \ge & \sum _{n\in [1:N]/\mathcal{E}}H\left(A_n^{{\mathbf{f}}_k}\right|W^{{\mathbf{f}}_1},\cdots ,W^{{\mathbf{f}}_k},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_k},Z^{\prime })\hfill \end{array}$$

(15)

$$\begin{array}{cc}\hfill =& \sum _{n\in [1:N]/\mathcal{E}}H\left(A_n^{{\mathbf{f}}_{k+1}}\right|W^{{\mathbf{f}}_1},\cdots ,W^{{\mathbf{f}}_k},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_{k+1}},Z^{\prime })\hfill \\ \hfill \ge & H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })\hfill \end{array}$$

(16)

$$\begin{array}{cc}\hfill =& H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })+H\left(W^{{\mathbf{f}}^{\prime }}\right|A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }},W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })-o\left(L\right)\hfill \\ \hfill =& H\left(W^{{\mathbf{f}}^{\prime }}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }})+H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }}\right|W^{{\mathbf{f}}^{\prime }},W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })-o\left(L\right)\hfill \end{array}$$

(17)

$$\begin{array}{cc}\hfill =& L+H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }}\right|W^{{\mathbf{f}}^{\prime }},W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })-o\left(L\right),\hfill \end{array}$$

(18)

where (15) holds because of the non-negativity of the following conditional entropy; i.e.,

$$\begin{array}{c}\hfill H\left(A_{[1:N]/(\mathcal{E}\cup \{k\left\}\right)}^{{\mathbf{f}}_k}\right|A_n^{{\mathbf{f}}_k},W^{{\mathbf{f}}_1},\cdots ,W^{{\mathbf{f}}_k},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_k},Z^{\prime })\ge 0,\forall n\in [1:N]/\mathcal{E},\end{array}$$

and (16) holds because of (11). The equality in (17) follows due to the fact that

$$\begin{array}{c}\hfill H\left(W^{{\mathbf{f}}^{\prime }}\right|A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }},W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })=H\left(W^{{\mathbf{f}}^{\prime }}\right|A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }},W^{\mathbf{f}},D_{[1:K],\mathcal{E}},A_{\mathcal{E}}^{{\mathbf{f}}^{\prime }},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })=o\left(L\right),\end{array}$$

where the first equality follows from (7), and the second equality follows from (9). Finally, (18) holds because $W^{{\mathbf{f}}^{\prime }}$ is independent from the queries and randomness, the security constraint and that $\mathbf{f},{\mathbf{f}}^{\prime }\in G{F}_q^K$ are linear independent vectors. □

The following lemma shows that any answers in a set are independent from any queries conditioned on the same set of queries to the same coefficient and any size of messages and randomnesses. This is the direct inference from the independence of message, queries, and randomnesses generated by the data collector (6).

Lemma 2.

Assume that $\mathbf{f}\in G{F}_q^N$, ${\mathcal{N}}_1,{\mathcal{N}}_2\in [1:N]$, and $\mathcal{K}\in [1:K]$. Then, we have the following equality:

$$\begin{array}{c}\hfill I(A_{{\mathcal{N}}_1}^{\mathbf{f}};Q_{{\mathcal{N}}_2}^{\mathbf{f}}|W_{\mathcal{K}},Z^{\prime },Q_{{\mathcal{N}}_1}^{\mathbf{f}})=0.\end{array}$$

(19)

Proof. 

The proof is the same as Section VI, Lemma 1, in [29], and the key to this proof is that $A_{{\mathcal{N}}_1}^{\mathbf{f}}$ is determined by $W_{[1:K]}$, conditioned on $Z^{\prime }$ and $Q_{{\mathcal{N}}_1}^{\mathbf{f}}$. We omit the detailed proof here. □

The lemma below has a similar form to Lemma 2, and it shows that any set of answers with size of E do not depend on the desired statistic, conditioned on the same set of queries and the randomnesses generated by the data collector.

Lemma 3.

For any $\mathcal{E}\subseteq [1:N],\left|\mathcal{E}\right|=E$,

$$\begin{array}{cc}\hfill H\left(A_{\mathcal{E}}^{\mathbf{f}}\right|Q_{\mathcal{E}}^{\mathbf{f}},W^{\mathbf{f}},Z^{\prime })=& H\left(A_{\mathcal{E}}^{\mathbf{f}}\right|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime }).\hfill \end{array}$$

(20)

Proof. 

We only need to show that $I(A_{\mathcal{E}}^{\mathbf{f}};W^{\mathbf{f}}|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })$ is less than or equal to 0 because of its non-negativity.

$$\begin{array}{cc}\hfill I(A_{\mathcal{E}}^{\mathbf{f}};W^{\mathbf{f}}|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })\le & I(A_{\mathcal{E}}^{\mathbf{f}},D_{[1:K],\mathcal{E}};W^{\mathbf{f}}|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })\hfill \\ \hfill =& I(D_{[1:K],\mathcal{E}};W^{\mathbf{f}}|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })+I(A_{\mathcal{E}}^{\mathbf{f}};W^{\mathbf{f}}|D_{[1:K],\mathcal{E}},Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })\hfill \end{array}$$

$$\begin{array}{cc}\hfill =& I(D_{[1:K],\mathcal{E}};W^{\mathbf{f}}|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })\hfill \\ \hfill =& H\left(D_{[1:K],\mathcal{E}}\right|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })-H\left(D_{[1:K],\mathcal{E}}\right|W^{\mathbf{f}},Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })\hfill \end{array}$$

(21)

$$\begin{array}{c}=0,\hfill \end{array}$$

(22)

where (21) holds because the answers $A_{\mathcal{E}}^{\mathbf{f}}$ are determined by $(D_{[1:K],\mathcal{E}},Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })$ in (7), and (22) holds because of (6) and (2). □

The following lemma shows that we can split the answers into two parts—one from E servers that cannot decode the database and the other from $N-E$ servers:

Lemma 4.

For any $\mathbf{f}\in G{F}_q^K$ and $\mathcal{E}\in [1:N]$, $\left|\mathcal{E}\right|=E$, we obtain

$$\begin{array}{cc}\hfill & \left(1-\frac{E}{N}\right)H\left(A_{[1:N]}^{\mathbf{f}}\right|Q_{[1:N]}^{\mathbf{f}},Z^{\prime })\ge L+H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-o\left(L\right).\hfill \end{array}$$

(23)

Proof. 

Based on the system model, we have

$$\begin{array}{cc}\hfill & H\left(A_{[1:N]}^{\mathbf{f}}\right|Q_{[1:N]}^{\mathbf{f}},Z^{\prime })\hfill \\ \hfill =& H\left(W^{\mathbf{f}}\right|Q_{[1:N]}^{\mathbf{f}},Z^{\prime })+H\left(A_{[1:N]}^{\mathbf{f}}\right|W^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-H\left(W^{\mathbf{f}}\right|A_{[1:N]}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })\hfill \end{array}$$

$$\begin{array}{cc}\hfill =& L+H\left(A_{[1:N]}^{\mathbf{f}}\right|W^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-o\left(L\right)\hfill \\ \hfill =& L+H\left(A_{\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })+H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},A_{\mathcal{E}}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-o\left(L\right)\hfill \end{array}$$

(24)

$$\begin{array}{cc}\hfill =& L+H\left(A_{\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })+H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},A_{\mathcal{E}}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-o\left(L\right)\hfill \end{array}$$

(25)

$$\begin{array}{cc}\hfill =& L+H\left(A_{\mathcal{E}}^{\mathbf{f}}\right|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })+H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},A_{\mathcal{E}}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-o\left(L\right)\hfill \end{array}$$

(26)

$$\begin{array}{cc}\hfill \ge & L+H\left(A_{\mathcal{E}}^{\mathbf{f}}\right|Q_{\mathcal{E}}^{\mathbf{f}},Z^{\prime })+H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-o\left(L\right)\hfill \end{array}$$

(27)

$$\begin{array}{cc}\hfill \ge & L+\frac{E}{N}H\left(A_{[1:N]}^{\mathbf{f}}\right|Q_{[1:N]}^{\mathbf{f}})+H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},S,Q_{[1:N]}^{\mathbf{f}},Z^{\prime })-o\left(L\right),\hfill \end{array}$$

(28)

where (24) follows from (1), (6), and (9); (25) follows from Lemma 2 when ${\mathcal{N}}_1=\mathcal{E}$ and ${\mathcal{N}}_2=[1:N]$; (26) follows from (20), (6), and (7); (27) is due to (7); and (28) follows from the Han’s inequality—i.e.,

$$\begin{array}{c}\hfill \sum _{\mathcal{E}\subseteq [1:N],\left|\mathcal{E}\right|=E}H\left(A_{\mathcal{E}}^{\mathbf{f}}\right|Q_{\mathcal{E}}^{\mathbf{f}})\ge \frac{E}{N}\left(\genfrac{}{}{0pt}{}{N}{E}\right)H\left(A_{[1:N]}^{\mathbf{f}}\right|Q_{[1:N]}^{\mathbf{f}}).\end{array}$$

(29)

 □

Now, we can get the lower bound on the asymptotic download size when L and K goes infinity by applying (14) to (23). We have

$$\begin{array}{cc}\hfill & \underset{K\to \infty ,L\to \infty }{lim}\left(1-\frac{E}{N}\right)H\left(A_{[1:N]}^{\mathbf{f}}\right|Q_{[1:N]}^{\mathbf{f}})\hfill \end{array}$$

$$\begin{array}{cc}\hfill \ge & \underset{K\to \infty ,L\to \infty }{lim}\left(H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},S,Q_{[1:N]}^{\mathbf{f}})+L-o\left(L\right)\right)\hfill \end{array}$$

(30)

$$\begin{array}{cc}\hfill =& \underset{K\to \infty ,L\to \infty }{lim}H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},S,Q_{[1:N]}^{\mathbf{f}})+L\hfill \\ \hfill \ge & \underset{K\to \infty ,L\to \infty }{lim}\frac{1}{N-E}\left(L+H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }}\right|W^{\mathbf{f}},W^{{\mathbf{f}}^{\prime }},D_{[1:K],\mathcal{E}},S,Q_{[1:N]}^{{\mathbf{f}}^{\prime }}-o\left(L\right))\right)+L\hfill \end{array}$$

(31)

$$\begin{array}{cc}\hfill \ge & \left(\sum _{k=0}^{\infty }\frac{1}{{(N-E)}^k}\right)L,\hfill \end{array}$$

(32)

where (30) follows from (23), (31) is because $o\left(L\right)$ goes zero when $L\to \infty$, and (32) follows from the non-negativity of the conditional entropy. The iteration (14) can be continued because for any $k\in \mathbb{N}$, $\frac{o\left(L\right)}{{(N-E)}^k}\to 0$ when $L\to \infty$. Thus, we can calculate the upper bound of the asymptotic capacity when $E<N-1$ as follows:

$$\begin{array}{cc}\hfill \underset{K\to \infty ,L\to \infty }{lim}C\le & \underset{K\to \infty ,L\to \infty }{lim}\frac{L}{H\left(A_{[1:N]}^{\mathbf{f}}\right)}\hfill \\ \hfill \le & \underset{K\to \infty ,L\to \infty }{lim}\frac{L}{H\left(A_{[1:N]}^{\mathbf{f}}\right|H\left(Q_{[1:N]}^{\mathbf{f}}\right)}\hfill \\ \hfill \le & \frac{1-\frac{E}{N}}{{\sum }_{k=0}^{\infty }\frac{1}{{(N-E)}^k}}\hfill \\ \hfill =& \frac{N-E-1}{N}.\hfill \end{array}$$

Thus, for any possible scheme $\varphi$ satisfying the constraints of the problem, the rate cannot be more than $\frac{N-E-1}{N}$ when $E<N-1$ and $K\to \infty$.

5. Proof of Theorem 1: Achievability When $\mathit{E}\mathbf{<}\mathit{N}\mathbf{-}\mathbf{1}$

In this section, we give a cross-subspace alignment (CSA) scheme based on the coding of interference in the computation phase to reach the asymptotic capacity [33] for any integers $N>E+1$ and $K\ge 2$. Throughout the scheme, we choose the length of each personal message $L=N-E-1\ge 1$, and we use the notation ${\Delta }_n={\prod }_{i=1}^L(i+{\alpha }_n)$ for $n\in [1:N]$.

First, we specify the encoding functions ${\left\{d_k\right\}}_{k\in [1:K]}$ in the upload phase. Let $W_k^l\in G{F}_q$ be the l-th symbol of each $W_k$, $k\in [1:K],l\in [1:L]$, and $W^l\in G{F}_q^{1\times K}$ be the row vector of the l-th symbol of all K messages, i.e., $W^l=[W_1^l,\cdots ,W_K^l]$. Assume that ${\alpha }_n,n\in [1:N]$ are N distinct coefficients all belonging to the set $\{\alpha \in G{F}_q:\alpha +i\ne 0,i\in [1:L]\}$—i.e., for any $i,j\in [1:N],{\alpha }_i\ne {\alpha }_j$. Note that the ${\alpha }_n$s are globally shared variables known to the users, servers, and the data collector. In order to protect the privacy of the users against the servers, each user k will generate $L\times E$ random noises $Z_{le}^k$ uniformly from $G{F}_q$. The uploaded information to the n-th server by the k-th user is given by

$$\begin{array}{c}\hfill D_{k,n}=d_{k,n}(W_k,Z_k)={\left[\begin{array}{c}{W}_k^1+\sum _{e=1}^E{(1+{\alpha }_n)}^e{Z}_{1e}^k\\ ⋮\\ W_k^L+\sum _{e=1}^E{(L+{\alpha }_n)}^e{Z}_{Le}^k\end{array}\right]}^T,\forall k\in [1:K],n\in [1:N],\end{array}$$

(33)

For convenience of notation, we write the content stored at server n in a vector form as

$$\begin{array}{cc}\hfill D_n=& [D_{1,n}^1,\cdots ,D_{K,n}^1,D_{1,n}^2,\cdots ,D_{K,n}^2,\cdots ,D_{1,n}^L,\cdots ,D_{K,n}^L]\hfill \end{array}$$

(34)

$$\begin{array}{cc}\hfill =& {\left[\begin{array}{c}{W}^1+\sum _{e=1}^E{(1+{\alpha }_n)}^e{Z}_{1e}\\ ⋮\\ W^L+\sum _{e=1}^E{(L+{\alpha }_n)}^e{Z}_{Le}.\end{array}\right]}^T,\hfill \end{array}$$

(35)

where $D_n\in G{F}_q^{1\times KL}$, and $Z_{le}$ is defined as $Z_{le}=[Z_{le}^1,\cdots ,Z_{le}^K]$.

In the computation phase, the query to Server n is determined by the coefficient $\mathbf{f}$ and the randomness from the data collector $Z^{\prime }$. We design the query to Server n based on $\mathbf{f}$ as

$$\begin{array}{c}\hfill Q_n^{\mathbf{f}}=\left[\begin{array}{c}\frac{{\Delta }_n}{1+{\alpha }_n}(\mathbf{f}+(1+{\alpha }_n)Z_1^{\prime })\\ ⋮\\ \frac{{\Delta }_n}{L+{\alpha }_n}(\mathbf{f}+(L+{\alpha }_n)Z_L^{\prime })\end{array}\right],\end{array}$$

(36)

where $Z_1^{\prime },\cdots ,Z_L^{\prime }$ are L random column vectors of length K, whose elements are uniformly distributed on $G{F}_q$, generated by the data collector.

For any server $n\in [1:N]$, the answer to the data collector $A_n^{\mathbf{f}}\in {\mathfrak{A}}_n=G{F}_q$ is calculated by

$$\begin{array}{cc}\hfill & A_n^{\mathbf{f}}=a_n^{\mathbf{f}}(Q_n^{\mathbf{f}},D_{[1:K],n})=D_n·Q_n^{\mathbf{f}}\hfill \\ \hfill =& \left(W^1+\sum _{e=1}^E{(1+{\alpha }_n)}^e{Z}_{1e}\right)·\left(\frac{{\Delta }_n}{1+{\alpha }_n}(\mathbf{f}+(1+{\alpha }_n)Z_1^{\prime })\right)\hfill \end{array}$$

(37)

$$\begin{array}{cc}\hfill & +\cdots +\left(W^L+\sum _{e=1}^E{(L+{\alpha }_n)}^e{Z}_{Le}\right)·\left(\frac{{\Delta }_n}{L+{\alpha }_n}(\mathbf{f}+(L+{\alpha }_n)Z_L^{\prime })\right),\forall n\in [1:N].\hfill \end{array}$$

(38)

According to the expansion of the representation (38) in the descending power of $\alpha$, we can see that $\frac{A_n^{\mathbf{f}}}{{\Delta }_n}$ is the sum of ${\sum }_{l=1}^L\frac{1}{l+{\alpha }_n}{W}^l·\mathbf{f}$ and a polynomial of degree E in ${\alpha }_n$. We can rewrite (38) as

$$\begin{array}{c}\hfill A_n^{\mathbf{f}}={\Delta }_n\left(\sum _{l=1}^L\frac{W^l\mathbf{f}}{l+{\alpha }_n}+\sum _{e=0}^E{I}_e{\alpha }_n^e\right),\end{array}$$

(39)

where $I_e$ is the coefficient of ${\alpha }_n^e$ for any $e\in [0:E]$. We can clearly see from (38) and (39) that $I_e$ is not a function of n. If we write the answers to the data collector from all the N servers together, we can get the following formula in a matrix form:

$$\left[\begin{array}{c}\frac{A_1^{\mathbf{f}}}{{\Delta }_1}\\ \frac{A_2^{\mathbf{f}}}{{\Delta }_2}\\ \cdots \\ \frac{A_N^{\mathbf{f}}}{{\Delta }_N}\end{array}\right]=\left[\begin{array}{c}\frac{1}{1+{\alpha }_1}\cdots \frac{1}{L+{\alpha }_1}1{\alpha }_1\cdots {\alpha }_1^E\\ \frac{1}{1+{\alpha }_2}\cdots \frac{1}{L+{\alpha }_2}1{\alpha }_2\cdots {\alpha }_2^E\\ \cdots \\ \frac{1}{1+{\alpha }_N}\cdots \frac{1}{L+{\alpha }_N}1{\alpha }_N\cdots {\alpha }_N^E\end{array}\right]·\left[\begin{array}{c}{W}^1·\mathbf{f}\\ ⋮\\ W^L·\mathbf{f}\\ I_0\\ ⋮\\ I_E\end{array}\right].$$

(40)

Now, we prove that this scheme satisfies the decodability constraint, i.e., (9), and the privacy constraints—i.e., the privacy constraint of the users against E servers (2), the privacy constraint of the users against the data collector (10), and the privacy constraint of the data collector against the non-colluding servers (11).

Recall that in our scheme, we let $L=N-E-1$. The decodability constraint is satisfied because the matrix in (40) is an $N\times N$ full-rank matrix when the ${\alpha }_n$s are distinct Lemma 5 in [33]. Hence, $W^1·\mathbf{f},\cdots ,W^L·\mathbf{f}$ can be fully recovered from $\frac{A_1^{\mathbf{f}}}{{\Delta }_1},\cdots ,\frac{A_N^{\mathbf{f}}}{{\Delta }_N}$, and the desired data $W^{\mathbf{f}}$ in (4) is obtained by

$$\begin{array}{c}\hfill W^{\mathbf{f}}=W^T·\mathbf{f}=\left[\begin{array}{c}{W}^1·\mathbf{f}\\ \cdots \\ W^L·\mathbf{f}\end{array}\right].\end{array}$$

(41)

The privacy constraint of the users against E colluding servers is satisfied due to the sharing strategy of the users. In (33), we know that the k-th user shares its l-th symbol to the n-th server in a form

$$\begin{array}{c}\hfill D_{k,n}^l=W_k^l+\sum _{e=1}^E{(1+{\alpha }_n)}^e{Z}_{le}^k,\end{array}$$

(42)

where $D_{k,n}^l$ denotes the storage in server n that $W_k^l$ shares. The security needs to guarantee that any E out of N servers do not know $W_k$ for any $k\in [1:K]$. For any set $\mathcal{E}:=\{o_1,\cdots ,o_E\}$ such that $\mathcal{E}\in [1:N]$ and $\left|\mathcal{E}\right|=E$, we choose the E servers to be in $\mathcal{E}$. We can write the storage of these servers with respect to what $W_k^l$ shares in a matrix form:

$$\left[\begin{array}{c}{D}_{k,o_1}^l\\ \cdots \\ D_{k,o_E}^l\end{array}\right]=\left[\begin{array}{c}{W}_k^l\\ \cdots \\ W_k^l\end{array}\right]+\left[\begin{array}{c}l+{\alpha }_{o_1}{(l+{\alpha }_{o_1})}^2\cdots {(l+{\alpha }_{o_1})}^E\\ \cdots \\ l+{\alpha }_{o_E}{(l+{\alpha }_{o_E})}^2\cdots {(l+{\alpha }_{o_E})}^E\end{array}\right]·\left[\begin{array}{c}{Z}_{l1}^k\\ \cdots \\ Z_{lE}^k\end{array}\right].$$

(43)

Notice that the Vandermonde matrix in (43), denoted by $V_{\mathcal{E}}$, is invertible for distinct $\{1+{\alpha }_e:{\alpha }_e\in G{F}_q,e\in \mathcal{E}\}$, so the second term of (43) contains E symbols that are linearly independent. The privacy constraint of the users against E colluding servers can be guaranteed as the E additional random symbols protect the shared message. We have

$$\begin{array}{cc}\hfill & I(D_{k,\mathcal{E}};W_k)\hfill \\ \hfill \le & \sum _{i=1}^L\sum _{j=1}^{L}I(D_{k,\mathcal{E}}^i;W_k^j|D_{k,\mathcal{E}}^{[1:i-1]};W_k^{[1:j-1]})\hfill \end{array}$$

$$\begin{array}{cc}\hfill =& \sum _{i=1}^L\sum _{j=1}^{L}I(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k;W^j|D_{[1:i-1],\mathcal{E}};W^{[1:j-1]})\hfill \end{array}$$

(44)

$$\begin{array}{cc}\hfill =& \sum _{l=1}^{L}I\left(W_k^l;W_k^l{\mathbf{1}}_E+V_E·Z_{l,\mathcal{E}}^k\right)\hfill \end{array}$$

(45)

$$\begin{array}{cc}\hfill =& {\displaystyle \sum _{l=1}^L}I\left(W_k^l;Z_{l,\mathcal{E}}^k\right)\hfill \\ \hfill =& 0,\forall k\in [1:K],n\in [1:N].\hfill \end{array}$$

where (44) comes from (43), and (45) holds because when $i<j$, we have

$$\begin{array}{cc}\hfill & I(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k;W^j|D_{[1:i-1],\mathcal{E}};W^{[1:j-1]})\hfill \\ \hfill =& H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k|D_{[1:i-1],\mathcal{E}};W^{[1:j-1]})-H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k|D_{[1:i-1],\mathcal{E}};W^{[1:j]})\hfill \\ \hfill =& H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k|W^i)-H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k|W^i)\hfill \\ \hfill =& 0,\forall i\in [1:L],\forall j\in [i+1,L],\hfill \end{array}$$

and when $i>j$, we have

$$\begin{array}{cc}\hfill & I(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k;W^j|D_{[1:i-1],\mathcal{E}};W^{[1:j-1]})\hfill \\ \hfill =& H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k|D_{[1:i-1],\mathcal{E}};W^{[1:j-1]})-H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k|D_{[1:i-1],\mathcal{E}};W^{[1:j]})\hfill \\ \hfill =& H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k)-H(W_k^i{\mathbf{1}}_E+V_E·Z_{i,\mathcal{E}}^k)\hfill \\ \hfill =& 0,\forall i\in [1:L],\forall j\in [1:i-1],\hfill \end{array}$$

so the remaining items are those $(i,j)$ such that $i=j=l$.

To prove that the privacy constraint of the data collector against the non-colluding servers is satisfied, we notice that the query to each server is composed of the desired coefficient $\mathbf{f}$ and independent additional randomness $Z_{[1:L]}^{\prime }$. Consider two linear independent vectors, $\mathbf{f},{\mathbf{f}}^{\prime }\in G{F}_q^K$. For any $l\in [1:L]$, the l-th entries of $Q_n^{\mathbf{f}}$ and $Q_n^{{\mathbf{f}}^{\prime }}$ are $\frac{{\Delta }_n}{l+{\alpha }_n}(\mathbf{f}+(l+{\alpha }_n)Z_l^{\prime })$ and $\frac{{\Delta }_n}{l+{\alpha }_n}({\mathbf{f}}^{\prime }+(l+{\alpha }_n)Z_l^{\prime })$, respectively. Notice that $Z_l^{\prime }$ (thus $\frac{{\Delta }_n}{l+{\alpha }_n}·Z_l^{\prime }$) is chosen uniformly from $G{F}_q^K$, and that $\frac{{\Delta }_n}{l+{\alpha }_n}·\mathbf{f}$ and $\frac{{\Delta }_n}{l+{\alpha }_n}·{\mathbf{f}}^{\prime }$ are two deterministic vectors in $G{F}_q^K$. The l-th symbol of $Q_n^{\mathbf{f}}$ or $Q_n^{{\mathbf{f}}^{\prime }}$ has the same distribution. Therefore, any single server can not distinguish queries from the data collector with one coefficient $\mathbf{f}$. Furthermore, if we assume the desired coefficient $\mathbf{t}$ is a random variable with some distribution known only to the data collector, and $\mathbf{f}$ is an implementation of $\mathbf{t}$, we can prove that the mutual information between $\mathbf{t}$ and $(Q_n^{\mathbf{t}},A_n^{\mathbf{t}},W_{[1:K]})$ is zero. We have

$$\begin{array}{cc}\hfill & I(Q_n^{\mathbf{t}},A_n^{\mathbf{t}},W_{[1:K]};\mathbf{t})\hfill \end{array}$$

$$\begin{array}{cc}\hfill \le & I(Q_n^{\mathbf{t}},W_{[1:K]},{\left\{Z_{le}\right\}}_{l\in [1:L],e\in [1:E]};\mathbf{t})\hfill \end{array}$$

(46)

$$\begin{array}{cc}\hfill =& I(Q_n^{\mathbf{t}};\mathbf{t}|W_{[1:K]},{\left\{Z_{le}\right\}}_{l\in [1:L],e\in [1:E]})\hfill \end{array}$$

(47)

$$\begin{array}{cc}\hfill =& H\left(Q_n^{\mathbf{t}}\right|W_{[1:K]},{\left\{Z_{le}\right\}}_{l\in [1:L],e\in [1:E]})-H\left(Q_n^{\mathbf{t}}\right|\mathbf{t},W_{[1:K]},{\left\{Z_{le}\right\}}_{l\in [1:L],e\in [1:E]})\hfill \end{array}$$

$$\begin{array}{cc}\hfill =& H\left(Q_n^{\mathbf{t}}\right)-H\left(\left.\left[\begin{array}{c}\mathbf{t}+(1+{\alpha }_n)\left(Z_1^{\prime }\right)\\ \cdots \\ \mathbf{t}+(L+{\alpha }_n)\left(Z_L^{\prime }\right)\end{array}\right]\right|\mathbf{t},W_{[1:K]},{\left\{Z_{le}\right\}}_{l\in [1:L],e\in [1:E]}\right)\hfill \end{array}$$

(48)

$$\begin{array}{cc}\hfill =& H\left(Q_n^{\mathbf{t}}\right)-H(Z_1^{\prime },\cdots ,Z_L^{\prime })\hfill \\ \hfill =& L-L\hfill \\ \hfill =& 0,\hfill \end{array}$$

where (46) is from (38), (47) is from (10), and (48) is from (6).

Finally, to prove that the privacy constraint of the users against the data collector is satisfied, we construct a basis of $G{F}_q^K$ containing the desired $\mathbf{f}$. Assume that the vectors in the basis is denoted by $\{{\mathbf{f}}_1,{\mathbf{f}}_2,\cdots ,{\mathbf{f}}_K\}$ where ${\mathbf{f}}_1=\mathbf{f}$. We then have

$$\begin{array}{cc}\hfill & I\left(W_{[1:K]};A_{[1:N]}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime }|W^{\mathbf{f}}\right)\hfill \\ \hfill =& \sum _{l=1}^{L}I\left(W^l;A_{[1:N]}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime }|W^{[1:l-1]},W^{\mathbf{f}}\right)\hfill \end{array}$$

$$\begin{array}{cc}\hfill \le & \sum _{l=1}^{L}I\left(W^l;A_{[1:N]}^{\mathbf{f}},Q_{[1:N]}^{\mathbf{f}},Z^{\prime }|W^{[1:L]/\left\{l\right\}},Z,W^{\mathbf{f}}\right)\hfill \\ \hfill =& \sum _{l=1}^{L}I\left(\left(W^l+\sum _{e=1}^E{(l+{\alpha }_n)}^e{Z}_{le}\right)·\right.\hfill \end{array}$$

(49)

$$\begin{array}{cc}\hfill & \left.{\left(\frac{{\Delta }_n}{1+{\alpha }_n}(\mathbf{f}+(l+{\alpha }_n){\left(Z_l^{\prime }\right)}^T)\right)}_{n\in [1:N]};W^l|W^{[1:L]/\left\{l\right\}},Z,W^{\mathbf{f}}\right)\hfill \end{array}$$

(50)

$$\begin{array}{cc}\hfill =& \sum _{l=1}^{L}I\left({\left(W^l{\left(Z_l^{\prime }\right)}^T+\sum _{e=1}^E{(l+{\alpha }_n)}^e{Z}_{le}{\left(Z_l^{\prime }\right)}^T\right)}_{n\in [1:N]};W^l|W^{[1:L]/\left\{l\right\}},W^{\mathbf{f}}\right)\hfill \end{array}$$

(51)

$$\begin{array}{cc}\hfill \le & \sum _{l=1}^{L}I\left({\left(W^l{\left(Z_l^{\prime }\right)}^T,Z_{le}{\left(Z_l^{\prime }\right)}^T\right)}_{e\in [1:E]};W^l|W^{[1:L]/\left\{l\right\}},W^{\mathbf{f}}\right)\hfill \end{array}$$

(52)

$$\begin{array}{cc}\hfill =& 0,\hfill \end{array}$$

(53)

where (49) holds because $(W^{[1:L]/\left\{l\right\}},Z)$ is independent with $W^l$; (50) holds because except for the term containing $W^l$, all terms in (38) are given, so deducting them would not change the mutual information; (51) is because ${\Delta }_n$ is a constant; (52) is because for any $n\in [1:N]$ and $e\in [1:E]$, ${(l+{\alpha }_n)}^e$ is a constant, and for $n\in [1:N]$, $W^l{\left(Z_l^{\prime }\right)}^T+{\sum }_{e=1}^E{(l+{\alpha }_n)}^e{Z}_{le}{\left(Z_l^{\prime }\right)}^T$ can be derived by $W^l{\left(Z_l^{\prime }\right)}^T$ and ${\left(Z_{le}{\left(Z_l^{\prime }\right)}^T\right)}_{e\in [1:E]}$; and (53) holds because for any $l\in [1:L]$, ${\left\{Z_{le}\right\}}_{e\in [1:E]}$ and $Z_l^{\prime }$ are generated independently of $W^{[1:L]}$.

Thus, we prove that the scheme satisfies all the constraints. As the answer from any server contains one symbol (the inner product) from $G{F}_q$, the rate of our proposed scheme is

$$\begin{array}{c}\hfill R=\frac{L}{{\sum }_{n=1}^{N}H\left(A_n^{\mathbf{f}}\right)}\frac{N-E-1}{N}.\end{array}$$

(54)

It can be seen that the scheme we construct by (33), (36), and (38) is achievable with the rate (54) invariant with K by rearranging the data $W_{[1:K]}$ to $W^{[1:L]}$. We notice that the achievable rate meets the asymptotic upper bound for any $K\in {\mathbb{N}}_{+}$, so the scheme is then proved to be asymptotically optimal, by letting $K\to \infty$.

6. Converse Result When $\mathit{E}\mathbf{=}\mathit{N}\mathbf{-}\mathbf{1}$

In this section, we prove that the asymptotic capacity is zero when $N=E+1$. First, the inequality (23) also holds when $N=E+1$ because the inequality in (15) becomes an equality. Hence, we have

$$\begin{array}{cc}\hfill H\left(A_{[1:N]/\mathcal{E}}^{\mathbf{f}}\right|W^{\mathbf{f}},D_{[1:K],\mathcal{E}},S,Q_{[1:N]}^{\mathbf{f}},Z^{\prime })\ge & L+H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}^{\prime }}\right|W^{\mathbf{f}},W^{{\mathbf{f}}^{\prime }},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}^{\prime }},Z^{\prime })-o\left(L\right).\hfill \end{array}$$

(55)

Thus, for any linear independent vectors ${\mathbf{f}}_1,{\mathbf{f}}_2,\cdots ,{\mathbf{f}}_K\in G{F}_q^K$, we have

$$\begin{array}{cc}\hfill \left(1-\frac{E}{N}\right)H\left(A_{[1:N]}^{\mathbf{f}}\right|Q_{[1:N]}^{\mathbf{f}})\ge & H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}_1}\right|W^{{\mathbf{f}}_1},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_1},Z^{\prime })+L-o\left(L\right)\hfill \end{array}$$

(56)

$$\begin{array}{cc}\hfill \ge & 2L+H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}_2}\right|W^{{\mathbf{f}}_1},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_2},Z^{\prime })-o\left(L\right)\hfill \end{array}$$

(57)

$$\begin{array}{cc}\hfill \ge & \sum _{k=0}^{K}L+H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}_K}\right|W^{[1:L]},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_K},Z^{\prime })\hfill \end{array}$$

(58)

$$\begin{array}{cc}\hfill =& \sum _{k=0}^{K}L+H\left(A_{[1:N]/\mathcal{E}}^{{\mathbf{f}}_K}\right|W_{[1:K]},D_{[1:K],\mathcal{E}},Q_{[1:N]}^{{\mathbf{f}}_K},Z^{\prime })\hfill \\ \hfill =& KL,\hfill \end{array}$$

(59)

where (56), (57), and (58) are from (55); and (59) holds because any K linear independent vectors constitute a basis in $G{F}_q^K$, so $W_{[1:K]}$ can be decoded. We can see that the download will go to infinity when $K\to \infty$, and thus the asymptotic capacity will be

$$\begin{array}{cc}\hfill \underset{K\to \infty ,L\to \infty }{lim}C\le & \underset{K\to \infty ,L\to \infty }{lim}\frac{L}{H\left(A_{[1:N]}^{\mathbf{f}}\right)}\hfill \\ \hfill \le & \underset{K\to \infty ,L\to \infty }{lim}\frac{L}{H\left(A_{[1:N]}^{\mathbf{f}}\right|H\left(Q_{[1:N]}^{\mathbf{f}}\right)}\hfill \\ \hfill \le & \underset{K\to \infty ,L\to \infty }{lim}\frac{1-\frac{E}{N}}{KL}\hfill \\ \hfill =& 0.\hfill \end{array}$$

The upper bound of C indicates that it is unfeasible to construct a scheme that has a positive communication rate when $K\to \infty$. However, differently from the $N=E$ scenario, our proof of the zero asymptotic capacity does not mean that there does not exist any scheme that satisfies all the constraints of our problem. In other words, there may be schemes that can satisfy all the constraints of the problem, albeit with an asymptotic capacity of zero. The detailed construction of a feasible scheme for $E=N-1$ and finite K is still an open problem.

7. Conclusions

Thanks to the research on data privacy and modeling of infectious diseases, the privacy-preserving epidemiological-data-collection problem was proposed, which aims to maximize the collection rate while protecting the privacy of all users’ data and the data collector’s preferences. We have found the asymptotic capacity of this problem, and the result shows that when there is more than one remaining server that not colluding with the other servers to decode the users’ data, the asymptotic capacity exists. The objective of this work was to find the best performance for the privacy-preserving epidemiological-data-collection problem, and we partly achieved this goal by giving the construction and proof of the optimal scheme when K is infinitely large. The achievability for $N\ge E+2$ was given by the cross-subspace alignment method, and the infeasibility of $N=1$ or $N=E$ was also proved. Our findings not only extend the research on secure multi-party computing systems in information theory, but also provide information-theoretic frameworks, implementations, and capacity bounds for the study of privacy epidemiological modeling. Although we characterized the asymptotic capacity for this problem, the exact capacity is still unknown. Some future directions include finding the exact capacity for finite K, the construction of a scheme when $N=E+1$, and the performance of asymptotic capacity under irregular colluding patterns. In general, our result of asymptotic capacity for this problem will provide useful insights for further studies in data both privacy and epidemiological modeling.