In this paper, we consider the problem of private information retrieval with secure storage (SS-PIR) under a setting with disjoint colluding sets, where the user wishes to privately retrieve one out ofKindependent messages that are securely stored acrossNservers. TheNservers are partitioned intoMdisjoint colluding sets, i.e., within them-th group,m∈[M], any set of up toTmcolluding servers cannot learn any information about the index of the desired message, and any set of up toXmcolluding servers cannot learn any information about theKmessages. The asymptotic capacity is defined as the maximum possible number ofq-ary symbols of the desired message that can be retrieved perq-ary downloaded symbol, in the limit as the number of messagesK→ ∞. We demonstrate that the asymptotic capacity of SS-PIR with disjoint colluding sets is the solution to a linear program parameterized by the server partition, privacy thresholdsTm, and security thresholdsXm. Our achievability scheme introduces a novel pre-decoding strategy built upon cross-subspace alignment (CSA) codes. In this strategy, instead of requiring the user to decode the message from all of the original CSA coded answer symbols, our approach allows certain servers to perform a local pre-decoding and return intermediate results that turn out to be more communication-efficient. This mechanism is the key to minimizing the download cost, allowing our scheme to match the information-theoretic converse and thereby establish the asymptotic capacity of SS-PIR with disjoint colluding sets.

The problem of weakly-private information retrieval (WPIR) is to allow the user to retrieve one out of$K$messages from a set of$N$distributed servers while guaranteeing that the information about the identity of the index of the desired message is leaked to the servers in a controlled manner, i.e., the privacy level cannot be less than a prescribed threshold as measured by a privacy metric. In this work, we consider the converse-induced privacy metric (CIPM) for WPIR proposed by Jia and fully settle the capacity, i.e., the supremum of the average number of desired message symbols retrieved per downloaded symbol, for the arbitrary number of messages$K$and the number of servers$N$. Our achievability scheme makes use of a symmetrized (with respect to the servers) version of the PIR codes due to Tian et al. by carefully designing the query distributions. It turns out that the optimal trade-off between the privacy level and the reciprocal of the retrieval rate in terms of the CIPM metric is linear for non-degenerate settings.

We consider the problem ofX-secure andT-private linear computation with graph based replicated storage (GXSTPLC), which enables the user to privately retrieve a linear combination of messages from a set ofNdistributed servers where each message is restricted to be stored exclusively among a subset of servers, adhering to anX-security constraint. This constraint dictates that any group of up toXcolluding servers must not disclose any information about the stored messages. Furthermore, any group of up toTservers is restricted from learning anything about the coefficients of the linear combination retrieved by the user. In this work, we completely characterize the asymptotic capacity of GXSTPLC, i.e., the supremum of achievable rates (which is the average number of desired symbols retrieved per downloaded symbol), in the limit as the number of messagesKapproaches infinity. Specifically, it is shown that a prior linear programming based upper bound on the asymptotic capacity of GXSTPLC due to Jia and Jafar is tight (thus settles their conjecture) by constructing achievability schemes. Notably, our achievability scheme also settles the exact capacity (i.e., for finiteK) ofX-secure linear combination with graph based replicated storage (GXSLC). Our achievability proof builds upon an achievability scheme for a closely related problem named asymmetric X-secure T-private linear computation with graph based replicated storage (Asymm-GXSTPLC) that guarantees non-uniform security and privacy levels across messages and coefficients (of the desired linear combination). In particular, by carefully designing Asymm-GXSTPLC settings for GXSTPLC problems, the corresponding Asymm-GXSTPLC schemes can be reduced to asymptotic capacity achieving schemes for GXSTPLC. In regard to the achievability scheme for Asymm-GXSTPLC, interesting aspects of our construction include a novel query and answer design which makes use of a Vandermonde decomposition of Cauchy matrices, and a trade-off among message replication, security and privacy thresholds.

Deep learning (DL)-based channel state information (CSI) feedback provides satisfactory reconstruction accuracy of downlink CSI for the base station in massive multiple-input multiple-output (MIMO) systems. Although the introduction of codeword quantization improves the efficiency and feasibility of DL-based CSI feedback networks, the gradient problem caused by quantizers in the training stage compromises the performance of neural networks. In this paper, by considering the test channel as an equivalent of ideal rate-distortion quantization in a mutual information sense, we propose a test channel-based quantization module (TCQM) for DL-based CSI feedback networks which mitigates the gradient problem in the end-to-end training of CSI feedback networks. Moreover, the training of the CSI feedback network with TCQM is not dependent on the design of practical quantizer in the inference stage, which reduces the complexity of the training and design constraints of the CSI feedback system. Finally, for the setting of fixed feedback overhead, based on the idea of TCQM, we propose an adaptive training strategy for CSI feedback networks to evaluate the proper combination of codeword length and quantization rate of codeword elements to achieve the optimal reconstruction accuracy. Experiment results show that the proposed schemes outperform existing codeword quantization schemes in the literature.

The problem of X-secure T-private linear computation with graph based replicated storage (GXSTPLC) is to enable the user to retrieve a linear combination of messages privately from a set of N distributed servers where every message is only allowed to replicate among a subset of servers subject to an X-security constraint, i.e., any groups of up to X colluding servers must reveal nothing about the messages. Besides, any groups of up to T servers must reveal no information about the coefficients of the linear combination retrieved by the user. In this paper, inspired by a Vandermonde decomposition of Cauchy matrices, we propose an achievability scheme for GXSTPLC that achieves the rate of (ρmin−X −T)/N if every message is replicated at least ρmintimes and ρmin> X + T, which coincides with a lower bound of the rate of X-secure T-private information retrieval with graph based replicated storage (GXSTPIR) by Jia and Jafar. Moreover, the asymptotic capacity of GXSTPLC is partially settled, including the setting where the storage forms a symmetric pattern.

Motivated by recent interest in federated submodel learning, this work explores the fundamental problem of privately reading from and writing to a database comprised of$K$files (submodels) that are stored across$N$distributed servers according to an$X$-secure threshold secret sharing scheme. One after another, various users wish to retrieve their desired file, locally process the information and then update the file in the distributed database while keeping the identity of their desired file private from any set of up to$T$colluding servers. The availability of servers changes over time, so elastic dropout resilience is required. The main contribution of this work is an adaptive scheme, called ACSA-RW, that takes advantage of all currently available servers to reduce its communication costs, fully updates the database after each write operation even though the database is only partially accessible due to server dropouts, and ensures a memoryless operation of the network in the sense that the storage structure is preserved and future users may remain oblivious of the past history of server dropouts. The ACSA-RW construction builds upon cross-subspace alignment (CSA) codes that were originally introduced for$X$-secure$T$-private information retrieval and have been shown to be natural solutions for secure distributed batch matrix multiplication problems. ACSA-RW achieves the desired private read and write functionality with elastic dropout resilience, matches the best results for private-read from PIR literature, improves significantly upon available baselines for private-write, reveals a striking symmetry between upload and download costs, and exploits storage redundancy to accommodate arbitrary read and write dropout servers up to certain threshold values. It also answers in the affirmative an open question by Kairouz et al. for the case of partially colluding servers (i.e., tolerating collusion up to a threshold) by exploiting synergistic gains from the joint design of private read and write operations.

The problem of (information-theoretic) X-secure T-private federated submodel learning represents a setting where a large scale machine learning model is partitioned into K submodels and stored across N distributed servers according to an X-secure threshold secret sharing scheme. Various users wish to successively train (update) the submodel that is most relevant to their local data while keeping the identity of their relevant submodel private from any set of up to T colluding servers. Inspired by the idea of cross-subspace alignment (CSA) for X - secure T -private information retrieval, we propose a novel CSA-RW (read-write) scheme for efficiently (in communication cost) and privately reading from and writing to a distributed database. CSA-RW improves significantly upon available baselines from prior work and is shown to be asymptotically/approximately optimal in download/upload cost. It also answers an open question previously noted by Kairouz et al. by exploiting synergistic gains from the joint design of private read-write.

Coded distributed matrix multiplication (CDMM) schemes, such as MatDot codes, seek efficient ways to distribute matrix multiplication task(s) to a set of N distributed servers so that the answers returned from any R servers are sufficient to recover the desired product(s). For example, to compute the product of matrices U, V, MatDot codes partition each matrix into $p\gt1$ sub-matrices to create smaller coded computation tasks that reduce the upload/storage at each server by $1 / p$, such that UV can be recovered from the answers returned by any $R=2 p-1$ servers. An important concern in CDMM is to reduce the recovery threshold R for a given storage/upload constraint. Recently, Jeong et al. introduced Approximate MatDot (AMD) codes that are shown to improve the recovery threshold by a factor of nearly 2, from $2 p-1$ to p. A key observation that motivates our work is that the storage/upload required for approximate computing depends not only on the dimensions of the (coded) sub-matrices that are assigned to each server, but also on their precision levels - a critical aspect that is not explored by Jeong et al. Our main contribution is a rudimentary asymptotic dimensional analysis of AMD codes inspired by the Generalized Degrees of Freedom (GDoF) framework previously developed for wireless networks, which indicates that for the same upload/storage, once the precision levels of the task assignments are accounted for, AMD codes are not better than a replication scheme which assigns the full computation task to every server. The dimensional analysis is supported by simple numerical experiments.

The goal of coded distributed computation is to efficiently distribute a computation task, such as matrix multiplication, N-linear computation, or multivariate polynomial evaluation, across S servers through a coding scheme, such that the response from any R servers ( R is called the recovery threshold) is sufficient for the user to recover the desired computed value. Current state-of-art approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC) for N-linear computations or multivariate polynomial evaluations). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of secure and private information retrieval. CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms. These codes are shown to unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general in download-limited settings. While matrix-partitioning approaches (EP codes) for distributed matrix multiplication have the advantage of flexible server computation latency, batch processing approaches (CSA, LCC) have significant advantages in communication costs as well as encoding and decoding complexity per matrix multiplication. In order to combine the benefits of these approaches, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches and demonstrate synergistic gains due to cross subspace alignment. Finally, we introduce N-CSA codes for N-linear distributed batch computations and multivariate batch polynomial evaluations. N-CSA codes include LCC codes as a special case, and are in general capable of outperforming LCC codes in download-constrained settings by upto a factor of N. Generalizations of N-CSA codes to include X-secure data and B-byzantine servers are also provided.

The problem of secure distributed batch matrix multiplication (SDBMM) studies the communication efficiency of retrieving a sequence of desired matrix products${\mathbf{AB}} = ({\mathbf{A}}_{1}{\mathbf{B}}_{1},\,\,{\mathbf{A}}_{2}{\mathbf{B}}_{2},\,\,\cdots,\,\,{\mathbf{A}}_{S}{\mathbf{B}}_{S})$from$N$distributed servers where the constituent matrices${\mathbf{A}}=({\mathbf{A}}_{1}, {\mathbf{A}}_{2}, \cdots, {\mathbf{A}}_{S})$and${\mathbf{B}}=({\mathbf{B}}_{1}, {\mathbf{B}}_{2},\cdots,{\mathbf{B}}_{S})$are stored in$X$-secure coded form, i.e., any group of up to$X$colluding servers learn nothing about$\mathbf{ A, B}$. It is assumed that${\mathbf{A}}_{s}\in \mathbb {F}_{q}^{L\times K}, {\mathbf{B}}_{s}\in \mathbb {F}_{q}^{K\times M}, s\in \{1,2,\cdots, S\}$are uniformly and independently distributed and$\mathbb {F}_{q}$is a large finite field. The rate of an SDBMM scheme is defined as the ratio of the number of bits of desired information that is retrieved, to the total number of bits downloaded on average. The supremum of achievable rates is called the capacity of SDBMM. In this work we explore the capacity of SDBMM, as well as several of its variants, e.g., where the user may already have either${\mathbf{A}}$or${\mathbf{B}}$available as side-information, and/or where the security constraint for either${\mathbf{A}}$or${\mathbf{B}}$may be relaxed. We obtain converse bounds, as well as achievable schemes for various cases of SDBMM, depending on the$L, K, M, N, X$parameters, and identify parameter regimes where these bounds match. In particular, the capacity for securely computing a batch of outer products of two vectors is$(1-X/N)^{+}$, for a batch of inner products of two (long) vectors the capacity approaches$(1-2X/N)^{+}$as the length of the vectors approaches infinity, and in general for sufficiently large$K$(e.g.,$K > 2\min (L,M)$), the capacity$C$is bounded as$(1-2X/N)^{+}\leq C < (1-X/N)^{+}$. A remarkable aspect of our upper bounds is a connection between SDBMM and a form of private information retrieval (PIR) problem, known as multi-message$X$-secure$T$-private information retrieval (MM-XSTPIR). Notable features of our achievable schemes include the use of cross-subspace alignment and a transformation argument that converts a scalar multiplication problem into a scalar addition problem, allowing a surprisingly efficient solution.

The goal of coded distributed batch matrix multiplication is to efficiently multiply L instances of λ x κ matrices, A = (A1, · · · , AL), with L instances of κ x μ matrices B = (B1, · · · , BL), by distributing the computation across S servers, such that the response from any R servers (R is called the recovery threshold) is sufficient to compute the L matrix products, AB = (A1B1, A2B2, · · · , ALBL). Existing solutions either compute each AlBl one at a time by partitioning individual matrices and coding across these partitions, or rely only on batch processing, i.e., coding across the batch of matrices without any matrix partitioning. The state-of-art for matrix-partitioning and batch processing approaches is represented by Entangled Polynomial Codes (EP codes), and Lagrange Coded Computing (LCC), respectively. In order to combine the benefits of the two approaches, we propose Generalized Cross-Subspace Alignment Codes (GCSA codes) that unify, generalize and improve upon the state of art. GCSA codes bridge the two extremes by efficiently combining both matrix-partitioning and batch processing, and offer flexibility in how much of each approach is used. Both EP codes and LCC codes can be recovered as special cases of GCSA codes. Remarkably, even without matrix partitioning, GCSA codes demonstrate an advantage over LCC codes in downloadconstrained settings. This is due to cross-subspace alignment, characterized by a Cauchy-Vandermonde code structure that aligns interference along Vandermonde terms, while the desired matrix products remain resolvable along Cauchy terms.

A secure multi-party batch matrix multiplication problem (SMBMM) is considered, where the goal is to allow a master to efficiently compute the pairwise products of two batches of massive matrices, by distributing the computation across S servers. Any X colluding servers gain no information about the input, and the master gains no additional information about the input beyond the product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA- NA) is proposed in this work, based on cross-subspace alignment codes. The state of art solution to SMBMM is a coding scheme called polynomial sharing (PS) that was proposed by Nodehi and Maddah-Ali. GCSA-NA outperforms PS codes in several key aspects - more efficient and secure inter-server communication, lower latency, flexible inter-server network topology, efficient batch processing, and tolerance to stragglers.

The problem of private information retrieval with graph-based replicated storage was recently introduced by Raviv, Tamo and Yaakobi. Its capacity remains open in almost all cases. In this work the asymptotic (large number of messages) capacity of this problem is studied along with its generalizations to include arbitrary T -privacy and X-security constraints, where the privacy of the user must be protected against any set of up to T colluding servers and the security of the stored data must be protected against any set of up to X colluding servers. A general achievable scheme for arbitrary storage patterns is presented that achieves the rate (ρmin-X -T )/N, where N is the total number of servers, and each message is replicated at least ρmintimes. Notably, the scheme makes use of a special structure inspired by dual Generalized Reed Solomon (GRS) codes. A general converse is also presented. The two bounds are shown to match for many settings, including symmetric storage patterns. Finally, the asymptotic capacity is fully characterized for the case without security constraints (X = 0) for arbitrary storage patterns provided that each message is replicated no more than T + 2 times. As an example of this result, consider PIR with arbitrary graph based storage (T = 1, X = 0) where every message is replicated at exactly 3 servers. For this 3-replicated storage setting, the asymptotic capacity is equal to 2/ν2(G) where ν2(G) is the maximum size of a 2-matching in a storage graph G[V, E]. In this undirected graph, the vertices V correspond to the set of servers, and there is an edge uv ∈ E between vertices u, v only if a subset of messages is replicated at both servers u and v.

The problem of X-secure T-private information retrieval from MDS coded storage is studied in this paper, where the user wishes to privately retrieve one out of K independent messages that are distributed over N servers according to an MDS code. It is guaranteed that any group of up to X colluding servers learn nothing about the messages and that any group of up to T colluding servers learn nothing about the identity of desired message. A lower bound of achievable rates is proved by presenting a novel scheme based on cross-subspace alignment and a successive decoding with interference cancellation strategy. For large number of messages (K → ∞) the achieved rate, which we conjecture to be optimal, improves upon the best known rates previously reported in the literature by Raviv and Karpuk, and generalizes an achievable rate for MDS-TPIR previously found by Freij-Hollanti et al. that is also conjectured to be asymptotically optimal. The setting is then expanded to allow unresponsive and Byzantine servers. Finally, the scheme is applied to find a new lower convex hull of (download, upload) pairs of secure and private distributed matrix multiplication that generalizes, and in certain asymptotic settings strictly improves upon the best known previous results.

X-secure and T-private information retrieval (XSTPIR) is a form of private information retrieval where data security is guaranteed against collusion among up to X servers and the user's privacy is guaranteed against collusion among up to T servers. The capacity of XSTPIR is characterized for an arbitrary number of servers N and arbitrary security and privacy thresholds X and T, in the limit as the number of messages K → ∞. Capacity is also characterized for any number of messages if either N = 3, X = T = 1 or if N ≤ X +T. Insights are drawn from these results, about aligning versus decoding noise, dependence of PIR rate on field size, and robustness to symmetric security constraints. In particular, the idea of cross subspace alignment, i.e., introducing a subspace dependence between Reed-Solomon code parameters, emerges as the optimal way to align undesired terms while keeping desired terms resolvable.

An extension of private information retrieval (PIR) with colluding servers is considered. The N servers are partitioned into M disjoint sets, such that collusion can only occur between servers that belong to the same set. Specifically, the m-th set is comprised of Nmservers, of which any Tmcan collude. The capacity of this PIR problem is shown to be C = (1 + (Σm = 1MNm/Tm)-1 + ⋯ + (Σm = 1MNm/Tm)-(κ-1))-1.