Skip to main content
eScholarship
Open Access Publications from the University of California

UC Irvine

UC Irvine Previously Published Works bannerUC Irvine

Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length

  • Author(s): Sun, H
  • Jafar, SA
  • et al.
Abstract

A private information retrieval (PIR) scheme is a mechanism that allows a user to retrieve any one out of K messages from N non-communicating replicated databases, each of which stores all K messages, without revealing anything (in the information theoretic sense) about the identity of the desired message index to any individual database. If the size of each message is L bits and the total download required by a PIR scheme from all N databases is D bits, then D is called the download cost and the ratio L/D is called an achievable rate. For fixed K,N in N , the capacity of PIR, denoted by C , is the supremum of achievable rates over all PIR schemes and over all message sizes, and was recently shown to be C=(1+1/N+1/N2+ cdots +1/N^K-1-1. In this paper, for arbitrary K and N , we explore the minimum download cost DL across all PIR schemes (not restricted to linear schemes) for arbitrary message lengths L under arbitrary choices of alphabet (not restricted to finite fields) for the message and download symbols. If the same M -ary alphabet is used for the message and download symbols, then we show that the optimal download cost in M -ary symbols is DL=LC. If the message symbols are in M -ary alphabet and the downloaded symbols are in M -ary alphabet, then we show that the optimal download cost in M -ary symbols, DL in (L'C), (L/C-1, (L'/C) -2, where L'= L M' M, i.e., the optimal download cost is characterized to within two symbols.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View