Semantic Private Information Retrieval: Effects of Heterogeneous Message Sizes and Popularities
Sajani Vithana, Karim Banawan, Şennur Ulukuş · 2020
We investigate the problem of semantic private information retrieval (semantic PIR). In semantic PIR, a user privately retrieves a message out of K independent messages stored in N replicated and non-colluding databases. The messages come with different semantics, i.e., the messages are allowed to have non-uniform a priori probabilities denoted by (pi> 0, i ∈ [K]) and arbitrary message sizes (Li, i ∈ [K]). We derive the semantic PIR capacity for general K, N. We present two achievable semantic PIR schemes: The first one is a deterministic scheme with non-uniform subpacketization. The second scheme is probabilistic and is based on choosing one query set out of multiple options at random to retrieve the required message without the need for exponential subpacketization. We derive conditions for the semantic PIR capacity to exceed the classical PIR capacity with equal priors and sizes. Our results show that the semantic PIR capacity can be larger than the classical PIR capacity when longer messages have higher popularities. However, when messages are of equal-length, the non-uniform priors cannot be exploited to improve the retrieval rate.