An Optimal Iterative Placement Algorithm for PIR from Heterogeneous Storage-Constrained Databases
share
We study private information retrieval (PIR) where a user privately downloads one of K messages from N databases (DBs) such that no DB can infer which message is being downloaded. Moreover, we consider the general case where DBs are storage constrained such that DB_n can only store a μ[n]KL symbols where 0≤μ[n] ≤ 1 and L is the number of symbols per message. Let t= ∑_n=1^Nμ[n] be an integer, a recent work by Banawan et al. showed that the capacity of heterogeneous Storage Constrained PIR (SC-PIR) is ( 1+ 1/t + 1/t^2 + ... + 1/t^K-1)^-1. However, an achievable, capacity achieving scheme was only developed for a network of N=3 DBs. In this paper, we propose an iterative placement algorithm for arbitrary N which achieves heterogeneous SC-PIR capacity when t is an integer. The algorithm defines storage contents of the DBs by assigning sets of sub-messages to t DBs in each iteration. We show that the proposed placement algorithm converges within N iterations and the storage placement requires at most N sub-messages per message without considering the sub-message requirement for the delivery. Finally, we show that the proposed solution can be applied to the case of non-integer t while still achieving capacity.
READ FULL TEXT