PaperlayerView exact revision on arXiv

Source-linked AI summary

The Capacity of Cache Aided Private Information Retrieval

Ravi Tandon

arXiv:1706.07035v1cs.ITcs.CRcs.DCmath.IT

TL;DR

The paper asks how cache storage changes the optimal download cost for private information retrieval. It achieves intermediate storage points through memory sharing and proves a converse. The result is that simple memory sharing is information-theoretically optimal in the analyzed setting.

  • Problem

    The paper asks for the optimal normalized download cost of private retrieval when a user may cache a function of the messages.

    Source: §1 · p. 2, §2 · pp. 3–4

  • Method

    It combines endpoint PIR schemes by memory sharing and proves a converse using bounds on conditional entropies given the cache.

    Source: §1 · p. 2, §3 · pp. 4, 8

  • Results

    The converse establishes that simple memory sharing is information-theoretically optimal for cache-aided PIR.

    Source: §1 · p. 2, §4 · p. 8

  • Takeaways & Limitations

    The work characterizes storage-dependent capacity when databases know the cached content.

    Source: §1 · p. 2, §4 · p. 8

    The analysis assumes databases know the cache; a hidden dynamic cache could improve capacity but adds cache-refresh download cost.

    Source: §4 · p. 8

Abstract

from arXiv · show

The problem of cache enabled private information retrieval (PIR) is considered in which a user wishes to privately retrieve one out of $K$ messages, each of size $L$ bits from $N$ distributed databases. The user has a local cache of storage $SL$ bits which can be used to store any function of the $K$ messages. The main contribution of this work is the exact characterization of the capacity of cache aided PIR as a function of the storage parameter $S$. In particular, for a given cache storage parameter $S$, the information-theoretically optimal download cost $D^{*}(S)/L$ (or the inverse of capacity) is shown to be equal to $(1- \frac{S}{K})\left(1+ \frac{1}{N}+ \ldots + \frac{1}{N^{K-1}}\right)$. Special cases of this result correspond to the settings when $S=0$, for which the optimal download cost was shown by Sun and Jafar to be $\left(1+ \frac{1}{N}+ \ldots + \frac{1}{N^{K-1}}\right)$, and the case when $S=K$, i.e., cache size is large enough to store all messages locally, for which the optimal download cost is $0$. The intermediate points $S\in (0, K)$ can be readily achieved through a simple memory-sharing based PIR scheme. The key technical contribution of this work is the converse, i.e., a lower bound on the download cost as a function of storage $S$ which shows that memory sharing is information-theoretically optimal.

1 Introduction

PIR seeks efficient retrieval of one replicated message without revealing its identity, and this paper studies how user caching changes PIR capacity. It proves that simple memory sharing is optimal through a converse lower bound on download cost.

  • PIR seeks efficient retrieval of one of K replicated messages without revealing which message the user requests.Source: §1 · p. 1
  • Without caching, Sun and Jafar characterized PIR capacity as (1+1/N+...+1/N^(K-1))^-1 [6].Source: §1 · p. 2
  • Prior variants include colluding and robust [8], Byzantine [9], MDS-coded [10] [11], symmetric [14] [15], and multi-message PIR [16]; general MDS-TPIR capacity remains open [12] [13].Source: §1 · p. 2
  • The paper characterizes cache-aided PIR capacity as a function of storage and proves simple memory sharing optimal via a converse lower bound on download cost.Source: §1 · p. 2

2 Cached Aided PIR: Problem Statement

The problem statement defines private retrieval from replicated databases with a user cache and asks for the optimal download cost as a function of storage. Schemes must preserve request privacy and allow reliable recovery of the desired message.

  • Each database stores all K messages, and the user privately requests one message while keeping its index secret from the databases.Source: §2 · p. 3
  • The user cache may store any function of the messages using SL bits; databases know the cached content, which remains fixed over time.Source: §2 · p. 3
  • A valid scheme must make each database's query distribution identical across requested messages and let the user recover the target with vanishing error as message size grows.Source: §2 · p. 3
  • The objective is to characterize optimal normalized download cost as a function of storage S, with PIR rate defined as desired-message bits per downloaded bit.Source: §2 · pp. 3–4

3 Main Results and Insights

The section establishes that the optimal download cost is convex in cache storage and develops a lower bound for the main result. Memory sharing constructs schemes at intermediate storage levels, while the converse uses permutation bounds and conditional Han’s inequality.

3 Main Results and Insights

  • The optimal download cost D*(S) is convex in the storage parameter S.The section states this as Lemma 1 and uses the convexity result in deriving a bound from the endpoint storage values.Source: §3 · p. 4
  • Memory sharing splits each message into independent parts and applies a different PIR scheme to each part, mixing their cache use and download costs.For storage S = αS1 + (1 − α)S2, the construction uses cache (αS1 + (1 − α)S2)L and downloads (αD*(S1) + (1 − α)D*(S2))L bits.Source: §3 · p. 4
  • The endpoint costs are D*(0) = 1 + 1/N + … + 1/N^(K−1) and D*(K) = 0; convexity gives the stated interpolation upper bound for intermediate S.The section derives the bound by writing S as a convex combination of 0 and K.Source: §3 · pp. 4–5
  • The converse averages download bounds over all K! message orderings and uses conditional Han’s inequality to obtain a tight lower bound.The proof uses the inequality to order conditional subset entropies, then lower-bounds them by the entropy of all messages given the cache.Source: §3 · pp. 7–8
  • The cache constraint H(Z) = SL and independent L-bit messages reduce the residual joint entropy to (K − S)L.This substitution appears in the final step of the lower-bound derivation.Source: §3 · p. 8

4 Conclusions and Discussion

The paper characterizes cache-aided PIR capacity as a function of storage and shows that memory sharing is optimal under its cache-visibility assumption. It identifies hidden-cache retrieval and the cost of refreshing cached content as an open direction.

4 Conclusions and Discussion

  • The converse establishes a lower bound on download cost that makes simple memory sharing information-theoretically optimal.The characterization assumes cached content is publicly known to all databases.Source: §4 · p. 8
  • Han’s inequality bounds conditional entropies of message subsets given the cache content Z in the converse proof.The paper assumes Z is publicly known to all databases.Source: §4 · p. 8
  • Dynamic cache-aided PIR with hidden cached content remains an open direction, with total download cost including both retrieval and cache refreshment.The paper raises whether this setting can improve on memory sharing after accounting for both costs.Source: §4 · pp. 8–9

5 Appendix: Proof of Lemma 2

The proof of Lemma 2 proceeds from a sequence of inequalities to its conclusion.

5 Appendix: Proof of Lemma 2

  • The proof of Lemma 2 starts with a sequence of inequalities and concludes by completing the lemma’s proof.Source: §5 · p. 9
Loading 1706.07035v1…