论文标题
在单个服务器上，私人信息检索和私人编码的侧面信息
On Single Server Private Information Retrieval with Private Coded Side Information
论文作者
论文摘要
这项工作是出于一个开放问题和猜想的动机，研究了Heidarzadeh等人最近引入的单个服务器私人信息检索问题（PIR-PCSI）。 PIR-PCSI的目的是允许用户有效检索所需的消息$ \ bm {w} _ {\bmθ} $，它是存储在服务器上的$ k $独立消息之一，同时利用均匀选择的size-$ m $ $ m $子集的线性组合的私人侧面信息（$ \ bm {\ Mathcal {s}} \ subset [k] $）的消息。设置PIR-PCSI-I和PIR-PCSI-II对应于$ \bmθ$是从$ [K] \ SetMinus \ bm {\ Mathcal {s}}} $均匀生成的约束。在每种情况下，必须将$（\bmθ，\ bm {\ mathcal {s}}）$从服务器中私有化。容量被定义为有关消息和现场大小，可实现的速率（每次下载的所需消息的数量）的至上，并由Heidarzadeh等人的特征。对于PIR-PCSI-I通常，对于Pir-PCSI-II，$ m>（k+1）/2 $ as $（k-m+1）^{ - 1} $。对于$ 2 \ leq m \ leq（k+1）/2 $，PIR-PCSI-II的容量仍然开放，并且猜想即使在这种情况下，容量也是$（K-M+1）^{ - 1} $。我们显示PIR-PCSI-II的容量等于$ 2/k $，$ 2 \ leq m \ leq \ leq \ frac {k+1} {2} $严格大于猜测值，并且不依赖于$ m $在此参数范围内。值得注意的是，发现一半的侧信息是多余的。我们还表征了最大的容量（在田地而不是冠军）以及具有私人系数的容量。结果被推广到PIR-PCSI-I（$θ\ in [k] \ setMinus \ Mathcal {s} $）和pir-pcsi（$θ\ in [k] $）设置。
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 $\bm{W}_{\bmθ}$, 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 ($\bm{\mathcal{S}}\subset[K]$) of messages. The settings PIR-PCSI-I and PIR-PCSI-II correspond to the constraints that $\bmθ$ is generated uniformly from $[K]\setminus\bm{\mathcal{S}}$, and $\bm{\mathcal{S}}$, respectively. In each case, $(\bmθ,\bm{\mathcal{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\leq M\leq (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 \leq M \leq \frac{K+1}{2}$, which is strictly larger 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 ($θ\in[K]\setminus\mathcal{S}$) and PIR-PCSI ($θ\in[K]$) settings.
