论文标题
不对称泄漏的私人信息检索
Asymmetric Leaky Private Information Retrieval
论文作者
论文摘要
在各种情况下，已经研究了私人信息检索（PIR）问题的信息理论公式。对称的私人信息检索（SPER）是一个变体，用户能够从$ n $ not-n $ non-n $ colluding复制数据库中私下检索一张$ k $消息，而无需了解剩余的$ k-1 $消息。但是，对于某些应用程序，完美隐私的目标可能太征税了。在本文中，我们调查了通过放松用户和DB隐私定义，可以提高SPIR的信息理论能力（等效地，最低下载成本的倒数）。这种放松在可以交易沟通效率的应用程序中相关。我们介绍并调查了不对称的泄漏PIR（AL-PIR）模型，每个方向都有不同的隐私泄漏预算。对于用户隐私泄漏，我们通过非负常数$ε$的函数来限制对数据库查询的所有可能实现之间的概率比。对于DB隐私，我们通过非负常量$δ$的函数在不希望的消息，查询和答案之间绑定了共同信息。我们提出了一个通用的AL-PIR计划，该方案在任意$ε$和$δ$的最佳下载成本上实现了上限。我们表明，Al-Pir的最佳下载成本被上限为$ d^{*}（ε，δ）\ leq 1+ \ frac \ frac {1} {n-1} {n-1} - \ frac {Δee^ε} {n^{n^{k-1} -1} -1} -1} -1} $。其次，我们获得下载成本的信息理论下限，为$ d^{*}（ε，δ）\ geq 1+ \ frac {1} {ne^ε-1} - \fracΔ{（ne^ε）^{K-1} -1} -1} -1} $。两个范围之间的差距分析表明，当$ε= 0 $，即在完美的用户隐私下，我们的Al-PIR方案是最佳的，并且在最大乘法间隙$ \ frac {n-e^{ - ε}}} {n-1} $中是最佳的。
Information-theoretic formulations of the private information retrieval (PIR) problem have been investigated under a variety of scenarios. Symmetric private information retrieval (SPIR) is a variant where a user is able to privately retrieve one out of $K$ messages from $N$ non-colluding replicated databases without learning anything about the remaining $K-1$ messages. However, the goal of perfect privacy can be too taxing for certain applications. In this paper, we investigate if the information-theoretic capacity of SPIR (equivalently, the inverse of the minimum download cost) can be increased by relaxing both user and DB privacy definitions. Such relaxation is relevant in applications where privacy can be traded for communication efficiency. We introduce and investigate the Asymmetric Leaky PIR (AL-PIR) model with different privacy leakage budgets in each direction. For user privacy leakage, we bound the probability ratios between all possible realizations of DB queries by a function of a non-negative constant $ε$. For DB privacy, we bound the mutual information between the undesired messages, the queries, and the answers, by a function of a non-negative constant $δ$. We propose a general AL-PIR scheme that achieves an upper bound on the optimal download cost for arbitrary $ε$ and $δ$. We show that the optimal download cost of AL-PIR is upper-bounded as $D^{*}(ε,δ)\leq 1+\frac{1}{N-1}-\frac{δe^ε}{N^{K-1}-1}$. Second, we obtain an information-theoretic lower bound on the download cost as $D^{*}(ε,δ)\geq 1+\frac{1}{Ne^ε-1}-\fracδ{(Ne^ε)^{K-1}-1}$. The gap analysis between the two bounds shows that our AL-PIR scheme is optimal when $ε=0$, i.e., under perfect user privacy and it is optimal within a maximum multiplicative gap of $\frac{N-e^{-ε}}{N-1}$ for any $(ε,δ)$.
