Private Contiguous-Block Retrieval
For designers of private storage and streaming systems, this work shows that exploiting contiguity in block retrieval can achieve the same optimal rate as general MPIR but with significantly lower subpacketization.
The paper introduces Private Contiguous-Block Retrieval (PCBR), where a user retrieves a contiguous block of messages from replicated servers while hiding the block identity. It establishes optimal retrieval rate and subpacketization bounds, and constructs a rate-optimal scheme with reduced subpacketization compared to general MPIR schemes.
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.