Cross Subspace Alignment and the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval

Abstract

$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 arbitrary number of servers $N$, and arbitrary security and privacy thresholds $X$ and $T$, in the limit as the number of messages $K\to \infty$. Capacity is also characterized for any number of messages if either $N=3,X=T=1$ or if $N\le 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.

References in corpus (9)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• The Capacity of Private Computation
• The Capacity of Private Information Retrieval with Partially Known Private Side Information
• Multi-Message Private Information Retrieval: Capacity Results and Near-Optimal Schemes
• Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries
• Single-Server Multi-Message Private Information Retrieval with Side Information
• The Capacity of Multi-round Private Information Retrieval from Byzantine Databases

Cited by in corpus (3)

• Converse for Multi-Server Single-Message PIR with Side Information
• On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage
• The Capacity of Multi-round Private Information Retrieval from Byzantine Databases