Private Structured-Subset Retrieval
2026-05-06 • Information Theory
Information Theory
AI summaryⓘ
The authors study a problem called Private Structured-Subset Retrieval (PSSR), where a user wants to privately get a specific group of messages from multiple servers, but this group follows certain patterns or structures. They show that by using these structures, the user can sometimes retrieve messages more efficiently than in traditional private retrieval methods. Their new approach also reduces the complexity of how data is split up and stored on servers. Overall, the authors provide new limits and construction methods that improve message retrieval for these structured demands without sacrificing privacy.
Private Information Retrieval (PIR)Multi-message PIR (MPIR)Structured Subset RetrievalRetrieval RateSubpacketizationReplicationLinear SchemesNon-colluding Servers
Authors
Maha Issa, Anoosheh Heidarzadeh
Abstract
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.