Cross Subspace Alignment and the Asymptotic Capacity of $X$ -Secure $T$ -Private Information Retrieval
Skip to main content
eScholarship
Open Access Publications from the University of California

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

  • Author(s): Jia, Zhuqing
  • Sun, Hua
  • Jafar, Syed Ali
  • et al.
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\rightarrow\infty$. Capacity is also characterized for any number of messages if either $N=3, X=T=1$ or if $N\leq 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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View