A Shannon-Theoretic Approach to the Storage-Retrieval Tradeoff in PIR Systems Conference Paper uri icon

abstract

  • 2018 IEEE. We consider the storage-retrieval rate tradeoff in private information retrieval systems using a Shannon-theoretic approach. Our focus is on the canonical two-message two-database case, for which a coding scheme based on random codebook generation, joint typicality encoding, and the binning technique is proposed. It is first shown that when the retrieval rate is kept optimal, the proposed non-linear scheme uses less storage than the optimal linear scheme. Since the other extreme point corresponding to using the minimum storage requires both messages to be retrieved, the performance through space-sharing of the two points can also be achieved. However, using the proposed scheme, further improvement can be achieved over this simple strategy. Although the random-coding based scheme has a diminishing but nonzero probability of error, the coding error can be eliminated if variable-length codes are allowed. Novel outer bounds are finally provided and used to establish the superiority of the non-linear codes over linear codes.

name of conference

  • 2018 IEEE International Symposium on Information Theory (ISIT)

published proceedings

  • 2018 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT)

author list (cited authors)

  • Tian, C., Sun, H., & Chen, J.

citation count

  • 25

complete list of authors

  • Tian, Chao||Sun, Hua||Chen, Jun

publication date

  • January 2018