Matthieu Bloch
(Ed.)
Motivated by an open problem and a conjecture,
this work studies the problem of single server private information
retrieval with private coded side information (PIR-PCSI) that was
recently introduced by Heidarzadeh et al. The goal of PIR-PCSI
is to allow a user to efficiently retrieve a desired message Wθ,
which is one of K independent messages that are stored at
a server, while utilizing private side information of a linear
combination of a uniformly chosen size-M subset (S ⊂ [K]) of
messages. The settings PIR-PCSI-I and PIR-PCSI-II correspond
to the constraints that θ is generated uniformly from [K]\S, and
S, respectively. In each case, (θ, S) must be kept private from the
server. The capacity is defined as the supremum over message
and field sizes, of achievable rates (number of bits of desired
message retrieved per bit of download) and is characterized by
Heidarzadeh et al. for PIR-PCSI-I in general, and for PIR-
PCSI-II for M > (K + 1)/2 as (K − M + 1)−1. For
2 ≤ M ≤ (K + 1)/2 the capacity of PIR-PCSI-II remains
open, and it is conjectured that even in this case the capacity
is (K − M + 1)−1. We show the capacity of PIR-PCSI-II is
equal to 2/K for 2 ≤ M ≤ K+1, which is strictly larger 2
than the conjectured value, and does not depend on M within this parameter regime. Remarkably, half the side-information is found to be redundant. We also characterize the infimum capacity (infimum over fields instead of supremum), and the capacity with private coefficients. The results are generalized to PIR-PCSI-I (θ ∈ [K] \ S) and PIR-PCSI (θ ∈ [K]) settings.
more »
« less
