Akademska digitalna zbirka SLovenije - logo
E-viri
Recenzirano Odprti dostop
  • The Capacity of Symmetric P...
    Sun, Hua; Jafar, Syed Ali

    IEEE transactions on information theory, 2019-Jan., 2019-1-00, 20190101, Letnik: 65, Številka: 1
    Journal Article

    Private information retrieval (PIR) is the problem of retrieving, as efficiently as possible, one out of <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> messages from <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> non-communicating replicated databases (each holds all <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other <inline-formula> <tex-math notation="LaTeX">K-1 </tex-math></inline-formula> messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is <inline-formula> <tex-math notation="LaTeX">1-1/N </tex-math></inline-formula> regardless of the number of messages <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula>, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least <inline-formula> <tex-math notation="LaTeX">1/(N-1) </tex-math></inline-formula> bits per desired message bit. Otherwise, if the amount of common randomness is less than <inline-formula> <tex-math notation="LaTeX">1/(N-1) </tex-math></inline-formula> bits per message bit, then the capacity of SPIR is zero. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.