本文介绍了一篇题为《Incremental Offline/Online PIR》的学术论文，该论文由Yiping Ma、Ke Zhong、Tal Rabin和Sebastian Angel共同撰写，发表于2022年8月10日至12日在美国波士顿举行的第31届USENIX安全研讨会（USENIX Security Symposium）。论文的主要研究领域是密码学中的私有信息检索（Private Information Retrieval, PIR），特别是针对离线/在线PIR协议的改进。
私有信息检索（PIR）是一种密码学工具，允许客户端从数据库中检索数据项，而不向服务器透露检索的具体内容。PIR在许多隐私保护应用中非常有用，例如隐私保护的视频流、密码检查、广告投放、匿名消息传递等。然而，传统的PIR协议存在一个显著的限制：计算复杂度与数据库大小呈线性关系，这意味着随着数据库规模的增加，PIR的计算开销也会显著增加。
为了克服这一限制，近年来研究者提出了离线/在线PIR协议。这类协议通过将大部分计算工作转移到与查询无关的离线预处理阶段，从而在在线查询阶段实现亚线性计算复杂度。然而，现有的离线/在线PIR协议假设数据库是不可变的，即一旦数据库经过预处理，就不能再添加、删除或修改数据项。如果数据库发生变化，现有的协议必须重新进行昂贵的离线预处理，这极大地限制了PIR的实际应用。
本文的核心贡献是提出了增量预处理（Incremental Preprocessing）的概念，使得在数据库发生变化时，无需重新进行完整的预处理，而是只需更新与变化相关的部分，从而显著降低了更新成本。
本文的研究方法主要分为以下几个步骤：
问题定义与目标：
本文的目标是扩展现有的离线/在线PIR协议，使其支持可变的数据库。具体来说，当数据库发生添加、删除或修改操作时，客户端和服务器能够以与变化数量成比例的成本更新预处理结果，而不需要重新进行完整的预处理。
增量预处理的设计：
本文提出了增量预处理的概念，并设计了相应的算法来支持数据库的增量更新。具体来说，本文对两种现有的离线/在线PIR协议进行了扩展：
增量伪随机集（Incremental Pseudorandom Sets）：
为了支持增量预处理，本文提出了增量伪随机集（Incremental PRS）的概念。PRS是一种用于生成伪随机子集的工具，本文通过扩展PRS的定义，使其能够支持数据库的动态变化。具体来说，本文设计了一种新的PRS构造，使得在数据库发生变化时，客户端和服务器能够以较低的成本更新预处理结果。
实验验证：
本文通过实验验证了增量预处理的有效性。实验结果表明，在包含100万个数据项的数据库中，增量预处理的计算成本比从头开始预处理低56倍。此外，本文还将增量预处理应用于PIR-Tor（一种基于PIR的Tor网络改进方案），结果显示，增量预处理显著提高了Tor目录节点的吞吐量。
本文的主要结果包括： 1. 增量预处理的有效性：
实验表明，增量预处理能够显著降低数据库更新时的计算成本。在包含100万个数据项的数据库中，增量预处理的计算成本比从头开始预处理低56倍。
PIR-Tor的性能提升：
本文将增量预处理应用于PIR-Tor，结果显示，使用增量预处理的PIR-Tor实现比使用现有最先进的2服务器PIR协议的实现提高了约7倍的吞吐量。
增量伪随机集的构造：
本文提出了一种新的增量伪随机集构造，使得在数据库发生变化时，客户端和服务器能够以较低的成本更新预处理结果。
本文的主要贡献在于提出了增量预处理的概念，并将其应用于现有的离线/在线PIR协议中。通过引入增量预处理，本文使得PIR协议能够支持可变的数据库，从而显著降低了数据库更新时的计算成本。这一改进不仅具有重要的理论意义，还为PIR在实际应用中的广泛使用提供了可能。
增量预处理的创新性：
本文首次提出了增量预处理的概念，使得PIR协议能够支持可变的数据库，这一创新为PIR的实际应用提供了新的可能性。
增量伪随机集的构造：
本文提出了一种新的增量伪随机集构造，使得在数据库发生变化时，客户端和服务器能够以较低的成本更新预处理结果。
实验验证的有效性：
本文通过实验验证了增量预处理的有效性，并展示了其在PIR-Tor中的应用效果，显著提高了系统的吞吐量。
本文还讨论了增量预处理在关键字PIR（PIR by Keywords）中的应用挑战。关键字PIR允许客户端通过关键字而不是索引来检索数据项，然而，当数据库发生变化时，现有的离线/在线PIR协议无法有效支持关键字PIR。本文指出，这一问题仍然是一个开放的研究方向。
总的来说，本文通过引入增量预处理，显著改进了现有的离线/在线PIR协议，使其能够支持可变的数据库，为PIR在实际应用中的广泛使用提供了新的可能性。