技术摘要：对抗性服务器环境下实现容量达到型私密信息检索的充要条件

问题陈述

私密信息检索（PIR）使用户能够在不向服务器泄露所需索引的情况下，从存储在 $M$ 条消息及 $S$ 个服务器中的数据库中检索特定消息。虽然现有文献已经确定了各种对抗性 PIR 场景下的信息论容量（即最大下载效率），但仍缺乏构建能够达到该容量的查询方案的系统化方法。具体而言，现有文献尚未明确定义查询矩阵必须满足哪些必要且充分的条件，以在存在对抗行为时同时保证隐私性、正确性和容量可达性。

本文针对三种主要的对抗场景进行了研究：

1. 共谋 PIR（Colluding PIR）： $T$ 个服务器组成的子集进行共谋，共享其查询并试图推断用户的目标索引。
2. 鲁棒 PIR（Robust PIR）： $U$ 个服务器处于无响应状态（丢包/擦除），用户必须利用总计 $S+U$ 个服务器中的剩余 $S$ 个服务器的响应来检索消息。
3. 拜占庭 PIR（Byzantine PIR）： $B$ 个服务器返回错误（噪声）响应，用户利用 $S+2B$ 个服务器来纠正这些错误。

核心问题在于推导关于查询生成过程的数学条件，以确保 PIR 方案不仅具备隐私性和正确性，而且能达到下载率的理论上界（容量）。

研究方法

作者采用了信息论方法，侧重于线性 PIR 方案，其中服务器响应被构造为消息与查询的矩阵乘积。研究方法包括以下步骤：

1. 形式化： 本文定义了系统模型，包括消息熵、通过随机因子 $F$ 生成的查询，以及针对共谋、鲁棒和拜占庭场景的具体隐私与正确性约束。
2. 条件推导：
   • 正确性： 作者建立了一个解码矩阵 $D_m$ 必须存在的条件，使得服务器响应的线性组合能够产生目标消息 $W_m$，同时抵消所有其他消息。
   • 隐私性： 对于共谋和非共谋（鲁棒/拜占庭）场景，作者分析了查询集的熵。他们证明，当生成特定查询实现的候选随机因子 $f$ 的数量与目标消息索引无关时，隐私性得到满足。这确保了任何服务器子集观察到的查询分布与用户的选择是独立的。
   • 容量可达性： 通过分析先前容量推导中使用的不等式（特别是涉及互信息和条件熵的部分），作者确定了实现容量需要这些不等式取等号。这导致了对查询矩阵的具体秩（rank）条件。
3. 验证： 将推导出的条件应用于两种具有代表性的现有方法：Sun 的方法（已知是容量达到的）和 Wang 的方法（在某些语境下已知是次优的）。作者验证了这些方法是否满足新推导出的充要条件。

核心贡献

本文的主要贡献是推导出了对抗环境下实现容量达到型 PIR 方案的充要条件，并将其明确地表达为查询矩阵的属性。

1. 正确性条件

对于任何目标消息 $m$，必须存在一个解码矩阵 $D_m$，使得：
$$D_m \begin{pmatrix} Q^{(m)}_1 \\ \vdots \\ Q^{(m)}_S \end{pmatrix} = \begin{pmatrix} O \\ E \\ O \end{pmatrix}^\top$$
其中 $E$ 是单位矩阵，$O$ 代表对应于非目标消息的零矩阵。

2. 隐私性条件

• 鲁棒/拜占庭隐私： 对于任何服务器 $j$ 及任何两个消息索引 $m, m'$，生成相同查询实现 $q_j$ 的随机因子 $f$ 的数量必须相等：$|\{f | Q^{(m)}_j = q_j\}| = |\{f | Q^{(m')}_j = q_j\}|$。
• 共谋隐私： 同样的条件适用于任何 $T$ 个共谋服务器集合 $T$：$|\{f | Q^{(m)}_T = q_T\}| = |\{f | Q^{(m')}_T = q_T\}|$。

3. 容量可达性条件

论文确立了基于秩的查询矩阵条件：

• 针对鲁棒/拜占庭 PIR：
  • 所有服务器中非目标消息的查询矩阵的秩必须等于任何单个服务器针对这些消息的查询矩阵的最大秩：$\text{rank } Q^{(m)}_{1:S+\mu}[\bar{m}] = \max_{j} \text{rank } Q^{(m)}_j[\bar{m}]$。
  • 对于任何服务器子集 $\kappa$，目标消息组件的查询矩阵的秩应等于各部分秩之和：$\text{rank } Q^{(m)}_\kappa[I] = \sum_{j \in \kappa} \text{rank } Q^{(m)}_j[I]$。
• 针对共谋 PIR：
  • 对于所有服务器中的目标消息组件，同样适用秩加性条件。
  • 所有服务器中非目标消息的查询矩阵的秩必须等于任何 $T$ 个共谋服务器子集所能达到的最大秩：$\text{rank } Q^{(m)}_{1:S}[\bar{m}] = \max_{T} \text{rank } Q^{(m)}_T[\bar{m}]$。

结果

作者应用这些推导出的条件来验证现有的 PIR 方案：

1. Sun 的方法： 分析确认 Sun 的共谋、鲁棒和拜占庭 PIR 方案均满足所有推导出的充要条件。具体而言，使用最大距离可分（MDS）码和全秩随机矩阵确保了容量所需的秩条件和隐私所需的计数条件均得到满足。
2. Wang 的方法： 分析显示，尽管 Wang 的共谋 PIR 方案满足正确性和隐私性，但它未能满足容量条件。具体而言，合并后的目标消息组件查询矩阵的秩（$\text{rank } Q^{(m)}_{1:S}[m]$）并不等于单个服务器秩之和（$\sum \text{rank } Q^{(m)}_j[m]$）。这种差异解释了为什么 Wang 的方法实现的下载率低于理论容量。论文表明，在 Wang 的方案中，某些查询向量会以非零概率变为零向量，从而导致次优的下载率。

重要意义

本文声称其主要意义在于提供了一个用于构建和验证容量达到型 PIR 方案的系统化框架。在此之前，此类方案的构建依赖于经验性的方法，且验证容量可达性非常困难。通过将条件表达为查询矩阵的属性（特别是秩属性和随机因子的分布），作者提供了一个清晰的清单，用于：

• 验证所设计的 PIR 方案是否达到容量。
• 指导系统地构建新的容量达到型方案。

这项工作弥合了对抗环境下 PIR 容量的理论上界与实现这些上界的实际方案构建之间的鸿沟。它证实了已知的容量达到型方法（如 Sun 的方法）确实满足这些严密的数学条件，同时识别出了导致次优方法（如 Wang 的方法）无法达到容量的具体结构性缺陷。