PPC Insights 系列：高效在线匿踪查询技术

随着数字经济的高速发展，数据要素的重要性日益凸显，数据安全与隐私保护备受重视。匿踪查询（也称「隐私信息检索」）（Private Information Retrieval，PIR）是隐私计算的重要引擎之一，能够在检索数据的同时防止数据持有方知晓检索条件中的隐私信息。本文将从传统信息查询方式存在的问题出发，梳理匿踪查询技术的发展现状，并介绍洞见科技基于关键词检索的高效匿踪查询技术方案。

需求背景

银行、保险等金融机构因自身业务发展需要，经常要向外部数据合作方查询自身客户的画像标签信息来增强自身业务决策的有效性。在传统数据接口（API）方式的查询中，金融机构需要向数据合作方提供客户的身份标识信息作为检索条件。在这个过程中，客户信息存在被数据合作方或数据中介机构破解、缓存、转售等后链路风险，可能造成非常严重的商业损失和隐私泄漏事故。

匿踪查询作为隐私计算领域中安全多方计算下的子分支，能够有效解决上述问题，使数据持有方无法获知具体查询对象，从而很好地保护查询方的隐私信息，打消安全顾虑，促进数据安全有序流通。在应用场景上，匿踪查询主要适用于标签查询、评分查询、名单查询、信息核验等场景。

研究现状

匿踪查询的技术概念首先由 Chor 等人提出，并引出了两条技术路径：基于信息论安全的匿踪查询（Information Theoretic PIR，IT-PIR）和计算安全的匿踪查询（Computational PIR，C-PIR）。

在信息论安全的匿踪查询方案中，数据库被复制到多个无合谋的服务器上。客户端向每个服务器发出查询，并在本地合并来自所有服务器的响应完成查询。该方案有两个优点：第一，每个计算节点计算量相对较少（不同数据库可仅存储每个数据的异或拆分结果）；第二，协议本身可证明是信息论安全的。这意味着该方案能够抵御拥有无限计算量的对手，且能显著减少对加密强度的依赖。然而，该方案的系统部署难度较高，因为在工程实现上很难保证不同服务器不会共谋。

计算安全的匿踪查询只需要部署在单个服务器上，其隐私保护能力基于高强度加密算法。该种方案可以在满足加密强度下与由单个管理域（例如公司）控制的数据库一起使用。缺点是它们比信息论安全的匿踪查询方案的计算开销更大，因为该种方案要求在查询时对每个数据库中每条数据都执行昂贵的加密操作。虽然有大量工作来改善计算安全的匿踪查询的资源开销，但不幸的是，这些方案有的具有很高的网络成本，有的对数据宽度有一定限制。

在应用场景上，匿踪查询可分为离线批量匿踪查询和在线实时匿踪查询两种。离线批量匿踪查询用于大批量数据的统一查询，由查询方批量提供需要查询的关键词，批量地向数据持有方请求信息。而在线实时匿踪查询则是请求方每次发送一条查询请求。离线批量匿踪查询主打平均性能，由于可以单次大批量进行查询，通信量有较大幅度的下降。此外，应用 SIMD （Single Instruction Multiple Data，单指令流多数据流）等技术，使得服务端和客户端的计算量也得到优化。而在线实时匿踪查询对响应时间的要求更高，须支持客户端可随时向数据持有方灵活地发起请求，同时服务端也需要感知到查询次数的特性，用以对账计费，因此技术挑战更大。

支持关键词检索的高性能在线匿踪查询

支持关键词检索的匿踪查询

传统 C-PIR 协议需要查询方提前知道待查元素在被查询方数据库中所处的位置，在实际应用中，这一假设过强，难以取得商业应用。实际的数据查询过程一般通过关键词（keyword）检索来获取对应信息。在原有 C-PIR 协议基础上，一个直观的改进想法就是：如果能找到一种方式，可以实现在不泄露额外信息的前提下，建立关键词与上述位置信息的对应关系，即可实现基于关键词的匿踪查询。

图 1 基于位置信息的匿踪查询

图 2 基于关键词的匿踪查询

基于上述思想，当前支持关键词查询的 PIR （keyword PIR）方案主要分为以下三类：

隐私集合求交（PSI）与 C-PIR 相结合

在某些 PSI 协议（如 CM20）中，最后通过 OPRF 结合哈希函数的输出进行匹配得到交集信息，而在此过程中如果可以保证被查询方数据传输的有序性，查询方即可通过匹配获取到待查关键词的位置信息，在此基础上，再结合 C-PIR 协议，即可获取最终的待查信息。此外，还可以在原始的 PSI 协议中，对被查询方产出的哈希值进行拆分，一部分用来匹配，另一部分作为对称加密的对称密钥加密对应的待查信息并发送匹配串及密文给查询方，如果查询方能匹配出对应的对称密钥，则可以解密对应的密文。（此类方案均为工业界对原有协议的改造，目前还没有完整的学术论文发表，PIR 的定义中要求传输量小于数据库规模，而此类解决方案并未严格符合该定义）

不经意传输（OT）与多项式插值相结合

即把被查询方数据库中的数据的待查关键词（对应 x 坐标）以及对应的信息（对应 y 坐标）转化为多项式上的点(x,y)，从而得到一系列点的集合(Xi,Yi,i⋳n)，客户端与服务端同步一个多项式，只要拥有对应的关键词，即可直接计算出对应的待查信息。其中，同步多项式的过程需要借助不经意传输来保证协议的安全性。（在现有的方案中，为了保证隐私性，一般需要多个随机多项式的嵌套来构造最终的插值多项式）

Labeled-PSI

该方案也是利用了插值多项式的特性，以 CCS'21 方案为例，主要以 unbalanced PSI 为基础，先通过构造多项式判断关键词的存在性，再基于插值多项式计算对应的待查信息，前者以同态加密下的连乘为基础，可以直观地理解被查询方为在密文状态下把待查关键词与查询方发送的关键词的密文分别进行相减后连乘，再进行随机化，查询方通过解密查看连乘结果是否为 0。如果为 0，则代表存在此关键词，否则表示不存在。如果存在，查询方再通过插值多项式计算待查信息。CCS'21 方案是目前已知学术领域最优的方案，其性能（基于 Seal 的实现）如下：

图 3 CCS'21 方案性能

国内已有多个隐私计算专业厂商对匿踪查询的应用开展了商用研究，在信通院 2021 及 2022 年对各厂商匿踪查询产品的测试中，我们可以看到业界大致的安全性和性能测试指标。

图 4 信通院 2021 年、2022 年匿踪查询性能测试结果

高效在线匿踪查询

在大量学术理论研究的基础上，洞见科技根据 PIR 的实际应用场景进行了一系列深入研究和应用探索，涵盖了离线批量查询以及在线实时查询两大类，其中离线批量查询的场景对性能、稳定性没有太高的要求，而在线实时查询则面临诸多技术挑战，例如：

高并发、高性能要求。在线查询场景中，同一个数据源往往需要同时应对多个查询方的并发请求，加上密码学算法和协议本身的性能开销，对于计算效率、网络吞吐以及存储资源都有较高的要求。

高可用要求。高可用要求是在线业务场景天然的要求，尤其对于服务端，需要保证业务节点的实时在线，24 小时不间断提供服务，加上密码学算法本身对计算、编码准确性的要求，给高可用架构的设计提出了更高的要求。

针对上述挑战，洞见科技在基础理论与工程架构两个方面进行了研究探索，推出了针对高并发、高性能、高可用场景的高效匿踪查询架构，结合分布式计算技术、密码算法指令集加速技术、高性能计算（HPC）技术、LLVM 编译优化技术、密文数据高效存储及优先级调度技术，实现了能够支持工业级大规模应用的高效匿踪查询引擎（InsightPIR）。

鉴于商业应用场景中网络带宽的实际情况，我们限制网络的上/下行通信带宽均为 25Mbps，CPU 及内存资源为 8 核 16G，对上述高效匿踪查询引擎进行在线测试，得到如下数据:

图 5 洞见科技 InsightPIR 性能结果

从中可以看出，在限制通信带宽及计算资源的前提下，相比与已公开的解决方案，InsightPIR 引擎仍有明显性能优势（信通院测试环境为不限带宽，6 台 32 核 256G 内存服务器），以响应时间为例，针对 100~100 万的不可区分度，均有着至少 1~3 倍的性能提升，且可以在较低硬件成本下进行部署和应用。

结语

匿踪查询技术不但保留了普通数据查询的基本模式，而且对于查询方隐私信息的保护能力使其具有独特的魅力。尽管其性能与普通单点查询相比仍有较大差距，但经过多年来各国学者、研究人员的持续优化，匿踪查询技术已经有了长足的进步，开始逐步取得商业应用。洞见科技在前沿理论研究的基础上，结合自身在安全多方计算领域多年的实战经验，对匿踪查询进行了深度优化与改造，推出了高效在线匿踪查询引擎，能够在满足安全性的基础上进一步提升性能、降低资源开销及部署门槛，使其满足更多实时应用场景的商业落地。

【参考文献】

1. Akamai state of the internet connectivity report. https://www.akamai.com/fr/fr/multimedia/ documents/state-of-the-internet/q1-2017-stateof-the-internet-connectivity-report.pdf, May 2017.

2. Opensignal state of mobile networks: USA. https://opensignal.com/reportsdata/national/data-2017-08-usa/report.pdf, Aug. 2017.

3. Pung: Unobservable communication over fully untrusted infrastructure. https://github.com/pung-project/pung, Sept. 2017.

4. Simple encrypted arithmetic library — SEAL. https://sealcrypto.org, 2017.

5. XPIR: NFLLWE security estimator. https://github.com/XPIR-team/XPIR/blob/master/ crypto/NFLLWESecurityEstimator/ NFLLWESecurityEstimator-README, June 2017.

6. XPIR NFLParams. https://github.com/XPIRteam/XPIR/blob/master/crypto/NFLParams.cpp, June 2017.

7. Internet providers with data caps. https://broadbandnow.com/internet-providerswith-data-caps, Jan. 2018.

8. C. Aguilar-Melchor, J. Barrier, L. Fousse, and M.-O. Killijian. XPIR: Private information retrieval for everyone. In Proceedings of the Privacy Enhancing Technologies Symposium (PETS), July 2016.

9. M. R. Albrecht, R. Player, and S. Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3), Oct. 2015.

10. S. Angel and S. Setty. Unobservable communication over fully untrusted infrastructure. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), Nov. 2016.

11. Y. Arbitman, M. Naor, and G. Segev. Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), Oct. 2010.

12. Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations. In Proceedings of the ACM Symposium on Theory of Computing (STOC), May 1994.

13. B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs. Journal of the ACM, 59(2), 2012.

14. A. Beimel, Y. Ishai, E. Kushilevitz, and J.-F. Raymond. Breaking the O(n1/(2k−1)) barrier for information-theoretic private information retrieval. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), Nov. 2002.

15. Cong, Kelong, et al. "Labeled psi from homomorphic encryption with reduced computation and communication." Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021.