The server-symmetric capacity of multi-server PIR-CSI equals (1 + 1/N + ... + 1/N^{ceil(K/(M+1))-1})^{-1} when side information is independent of the requested message, and equals 1 (for M=2,K) or N/(N+1) (otherwise) when dependent.
Capacity of Single-Server Single-Message Private Information Retrieval with Private Coded Side Information
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We study the problem of single-server single-message Private Information Retrieval with Private Coded Side Information (PIR-PCSI). In this problem, there is a server that stores a database, and a user who knows a random linear combination of a random subset of messages in the database. The number of messages contributing to the user's side information is known to the server a priori, whereas their indices and coefficients are unknown to the server a priori. The user wants to retrieve a message from the server (with minimum download cost), while protecting the identities of both the demand and side information messages. Depending on whether the demand is part of the coded side information or not, we consider two different models for the problem. For the model in which the demand does not contribute to the side information, we prove a lower bound on the minimum download cost for all (linear and non-linear) PIR protocols; and for the other model wherein the demand is one of the messages contributing to the side information, we prove a lower bound for all scalar-linear PIR protocols. In addition, we propose novel PIR protocols that achieve these lower bounds.
fields
cs.IT 2years
2019 2verdicts
UNVERDICTED 2representative citing papers
Derives exact capacity (1 + 1/N + … + 1/N^{K-M-1})^{-1} for multi-server PIR-PCSI when demand is excluded from side information and a matching lower bound when demand is included.
citing papers explorer
-
Multi-Server Private Information Retrieval with Coded Side Information
The server-symmetric capacity of multi-server PIR-CSI equals (1 + 1/N + ... + 1/N^{ceil(K/(M+1))-1})^{-1} when side information is independent of the requested message, and equals 1 (for M=2,K) or N/(N+1) (otherwise) when dependent.
-
Private Information Retrieval with Private Coded Side Information: The Multi-Server Case
Derives exact capacity (1 + 1/N + … + 1/N^{K-M-1})^{-1} for multi-server PIR-PCSI when demand is excluded from side information and a matching lower bound when demand is included.