技术摘要：基于黑盒密码学的带预处理 PIR 下界

1. 问题陈述

本文研究了预处理模型下单服务器私有信息检索 (PIR) 的基本极限。在这种设定中，客户端执行一个离线阶段，以存储关于 $n$ 位数据库的少量状态（$s$ 比特），从而实现更高效的在线查询。虽然最近的突破（如 [CHK22, ZPZS24, LMW23]）通过利用预处理技术，展示了具有亚线性查询计算和通信量的单服务器 PIR 方案，但这些构造的理论边界仍不明确。

具体而言，作者探讨了是否可以构建出满足以下条件的单服务器 PIR 方案：

1. 实现亚线性摊还在线计算（具体为 $o(n/s)$）。
2. 依赖于黑盒密码学（通过密码学预言机建模，包括随机预言机、虚拟黑盒混淆以及通用的多线性群）。
3. 支持对称 PIR (SPIR)（即客户端仅能获知所查询的条目），且在线阶段仅使用单向函数 (OWF)。

此前针对带预处理 PIR 的下界研究仅限于受限类别的方案（例如：要求非编码服务器、数据库无关查询或单轮往返交互），或者依赖于未证实的复杂度假设。本研究旨在为更广泛的一类使用黑盒密码学的方案提供无条件的下界。

2. 研究方法

本文方法论的核心是引入了一个名为 Dual PIR 的新原语，并将标准带预处理 PIR 规约至该原语。

2.1 对偶私有信息检索 (Dual PIR)

作者将 Dual PIR 定义为标准 PIR 预处理模型的逆过程：

• 建议阶段 (Advice Phase)： 在任何查询已知之前，客户端根据数据库生成一个 $t$ 比特的建议字符串（transcript）。
• 提示阶段 (Hint Phase)： 给定数据库、一批 $k$ 个查询索引以及建议，客户端生成一个 $s$ 比特的提示 (hint)。
• 重构 (Reconstruction)： 仅使用查询索引、建议和提示（但不使用数据库），客户端必须重构被查询的数据库条目。

这种形式化将 PIR 的效率问题转化为了一个压缩问题。如果一个 PIR 方案过于高效（即 $t = o(n)$ 且 $s < k$），则意味着存在一个 Dual PIR，它仅使用 $t$ 比特的预共享建议就能将 $k$ 比特的信息压缩为 $s$ 比特，这在特定条件下在信息论上是不可能的。

2.2 从 PIR 到 Dual PIR 的规约

作者构建了一个规约，证明任何带有预处理的安全 PIR 方案都可以转化为一个 Dual PIR 方案。

• 建议 (Advice)： 通过模拟固定查询的 PIR 执行，生成通信记录（transcript）和一组服务器密码学预言机查询。
• 提示 (Hint)： 通过重新随机化客户端的状态，使其与针对另一个查询的固定记录相匹配。关键在于，为了处理密码学的黑盒性质，提示算法会采样新的密码学预言机，这些预言机与服务器之前的查询保持一致（使用共享的随机预言机以确保一致性）。
• 重构 (Reconstruction)： 使用采样的状态和固定的记录来模拟 PIR 查询的客户端侧。

2.3 与子密钥预测的联系

为了证明高效 Dual PIR 的不可能实现，作者将该问题与泄漏抗性密码学中的子密钥预测 ([BKR16]) 联系起来。他们表明，一个正确且高效的 Dual PIR 将允许攻击者在给定 $t$ 比特泄漏的情况下，以超过已知信息论边界的成功概率预测 $k$ 个随机比特的 $n$ 位密钥。具体而言，如果 $t < n/2$ 且 $k = \Omega(s)$，则正确重构的概率被限制在 $2^{s - \Omega(k)}$。

3. 核心贡献与结果

3.1 计算下界

本文确定了对于任何使用黑盒密码学进行客户端预处理的单服务器 PIR：

• 定理 1.1： 不可能同时实现 $o(n/s)$ 的摊还在线通信和 $o(n/s)$ 的摊还服务器密码学操作。
• 含义： 任何此类方案必须至少满足以下条件之一：
  1. 摊还在线通信为 $\Omega(n/s)$ 比特。
  2. 服务器执行 $\Omega(n/s)$ 个密码学比特操作。
• 紧致性： 该界限是优的。现有的方案（如 [WR25]）在没有服务器密码学操作的情况下实现了 $O(n/s)$ 通信，而其他方案（如 [ZPZS24]）在没有服务器密码学操作的情况下实现了 $O(n/s)$ 通信，但需要刷新客户端状态。该下界证实了无法同时绕过这两个瓶颈。

3.2 双高效 PIR (DEPIR)

作者排除了存在双高效 PIR（即客户端和服务器都具有亚线性时间）的可能性，即使该方案基于黑盒密码学。

• 定理 1.2： 对于单次查询，不存在具有亚线性查询计算量 ($t = o(n)$) 的单服务器 DEPIR，即使服务器执行任意编码。
• 该结果适用于公钥 DEPIR，并改进了以往仅限于单轮往返查询且服务器为被动模式的不可行性结果。

3.3 通信下界

本文为受限类别的 PIR 推导了特定的通信下界：

• 定理 1.4： 如果一个 PIR 满足以下任一条件，则需要 $\Omega(n/s)$ 的摊还通信：
  1. 服务器执行 $o(n/s)$ 次密码学操作。
  2. 服务器密码学操作仅取决于通信记录（数据库无关的密码学使用）。
  3. 该方案在理想化模型中提供完美隐私。

3.4 对称 PIR (SPIR)

本文讨论了带有客户端预处理的对称 PIR (SPIR) 的构建，其中客户端仅能获知被查询的条目。

• 构造 (定理 1.5)： 作者提出了一种在在线查询阶段仅依赖于单向函数 (OWF) 的带客户端预处理的 SPIR 构造。该方案实现了 $\tilde{O}(n/s)$ 的通信和计算，并支持每个离线阶段 $\tilde{O}(s)$ 次查询。
• 局限性 (定理 1.6)： 在随机预言机模型中，没有任何此类 SPIR 方案能支持每个离线阶段超过 $k > s$ 次的查询。这与非对称 PIR 不同，后者可以通过刷新状态来支持无限次的查询。作者证明，支持 $k > s$ 次查询需要公钥密码学或线性通信。

3.5 弱 PIR

这些下界扩展到了“弱”PIR 方案，即仅针对执行多项次密码学预言机查询的攻击者提供隐私的方案（类似于 Merkle 谜题）。

• 定理 1.3 & 1.5： 即使对于弱攻击者，如果诚实方和攻击者执行了相当数量的预言机查询，单服务器带预处理 PIR 的亚线性在线查询时间也是不可能实现的。

4. 重要性与主张

本文声称解决了在黑盒密码学假设下，单服务器带预处理 PIR 最佳效率的开放性问题。

• 无条件结果： 与以往依赖于复杂度假设（如 SZK 与 BPP 的分离）或受限查询模型（数据库无关、单轮往返）的工作（如 [ISW24]）不同，这些下界是无条件的，并且适用于包括多轮和数据库相关查询在内的更广泛的一类方案。
• 现有构造的优越性： 研究结果验证了近期实现 $\tilde{O}(n/s)$ 通信或计算的构造本质上是优的；在不破坏黑盒密码学假设的前提下，无法同时将通信和服务器计算降低到该阈值以下。
• SPIR 的可行性： 本研究表明，只要查询次数限制在客户端存储状态的大小 ($s$) 内，就可以实现仅在在线阶段使用 OWF 的对称 PIR。这阐明了在预处理模型中，对称性（数据隐私）与查询容量之间的权衡。
• DEPIR 的不可行性： 本文明确排除了从黑盒密码学构建具有亚线性查询计算时间的公钥 DEPIR 的可能性，解决了该领域的一个重要开放问题。

综上所述，本文确立了在近期 PIR 构造中所识别出的“瓶颈”（即高通信量或高服务器计算量）是黑盒密码学固有的基本限制，而非仅仅是当前构造技术的产物。