Private Contiguous-Block Retrieval
2026-05-06 • Information Theory
Information Theory
AI summaryⓘ
The authors study a problem where a user wants to privately download a series of connected messages (a block) from multiple servers without revealing which block they want. Unlike previous work where any group of messages could be requested, this work focuses on blocks that are next to each other in order. They investigate how this setup can make retrieval more efficient and create a method that achieves the best data download rate while keeping the needed data pieces small. Their approach is better suited for this problem than existing methods made for unrelated message sets.
Private Information RetrievalContiguous BlockMulti-message PIRRetrieval RateSubpacketizationNon-colluding ServersLinear SchemesData PrivacyStorage Systems
Authors
Maha Issa, Anoosheh Heidarzadeh
Abstract
We introduce the \emph{Private Contiguous-Block Retrieval (PCBR)} problem, where a user retrieves a block of $D$ messages with contiguous indices from $K$ replicated messages stored across $N$ non-colluding servers, while hiding the identity of the requested block from each server. This problem is motivated by storage and streaming systems where files are split into ordered segments. Unlike multi-message Private Information Retrieval (MPIR), where any $D$-subset may be requested, PCBR restricts the demand family to contiguous blocks. This relaxation raises a natural question: Can this structure be exploited to improve retrieval efficiency? We answer this question for balanced $\{0,1\}$-linear schemes. We establish an upper bound on the achievable retrieval rate for all problem parameters, derive a lower bound on the subpacketization level required by any scheme achieving the rate upper bound, and construct a rate-optimal scheme whose subpacketization level matches the lower bound for a broad range of problem parameters. Although the optimal PCBR rate coincides with the best-known MPIR rate converse bound, existing MPIR schemes can be suboptimal for PCBR and can require a much larger subpacketization level. In contrast, our scheme exploits the contiguous-block structure to achieve the optimal rate with reduced subpacketization.