Private Structured-Subset Retrieval
For researchers in information theory and private information retrieval, this work provides a new framework that leverages demand structure to improve retrieval rates and reduce subpacketization, showing that MPIR-optimal schemes can be suboptimal for structured demands.
The paper introduces the Private Structured-Subset Retrieval (PSSR) problem, which generalizes PIR and MPIR by restricting user demand to a known structured family of subsets. The authors derive converse bounds on retrieval rate and subpacketization, and construct schemes that achieve higher rates for certain families, sometimes exceeding the best-known MPIR rate upper bound, while also reducing subpacketization.
We introduce the \emph{Private Structured-Subset Retrieval (PSSR)} problem, where a user retrieves $D$ messages from a database of $K$ messages replicated across $N$ non-colluding servers, and the demand is restricted to a known structured family of $D$-subsets. This formulation generalizes classical Private Information Retrieval (PIR) and multi-message PIR (MPIR), and captures settings where the demand space is constrained by application-specific structure. Focusing on balanced ${\{0,1\}}$-linear schemes, we derive converse bounds on the maximum retrieval rate and minimum subpacketization level, and develop an optimization-based framework for constructing schemes for general structured demand families. Our results show that, for certain families, the PSSR rate converse bound can exceed the best-known MPIR rate upper bound; when this PSSR bound is achievable, MPIR rate-optimal schemes become suboptimal for those families. By exploiting demand structure, our PSSR schemes achieve higher retrieval rates for many families and never underperform the best-known balanced ${\{0,1\}}$-linear MPIR schemes. Our results also show that demand structure can reduce the required subpacketization even when the optimal rate is unchanged. Our parallel work on contiguous-demand families further illustrates the scope of this framework by yielding rate-optimal schemes with substantially smaller subpacketization and no field-size restrictions, improving upon MPIR-based schemes.