类型a：这篇文档报告了一项原创研究。

主要作者和机构及发表期刊信息
本文的主要作者包括姜宇婷（Yuting Jiang）、魏江宏（Jianghong Wei）和潘静（Jing Pan）。姜宇婷来自西安电子科技大学综合业务网络国家重点实验室（State Key Laboratory of Integrated Service Networks, Xidian University），魏江宏来自解放军战略支援部队信息工程大学数学工程与先进计算国家重点实验室（State Key Laboratory of Mathematical Engineering and Advanced Computing, PLA Strategic Support Force Information Engineering University），潘静则隶属于广州技术研究院（Guangzhou Institute of Technology, Xidian University）。该研究于2022年发表在《计算机科学与信息安全通讯》（CCIS 1663）中，收录于《SocialSec 2022》会议论文集，由Springer Nature Singapore Pte Ltd.出版。

学术背景
本研究属于隐私保护和密码学领域，具体聚焦于私有集合交集（Private Set Intersection, PSI）协议的设计与优化。PSI是一种允许两个互不信任的参与方安全地计算其私有输入集合的交集，同时不泄露任何额外信息的技术。它在远程诊断、DNA搜索、社交网络隐私保护等场景中具有广泛的应用价值。然而，现有的PSI协议大多无法验证数据的完整性和计算结果的正确性，特别是在恶意攻击模型下。为了解决这一问题，本文提出了一种基于全同态加密（Fully Homomorphic Encryption, FHE）、不经意伪随机函数（Oblivious Pseudo-Random Function, OPRF）和可验证计算（Verifiable Computation, VC）的公开可验证私有集合交集协议（Publicly Verifiable Private Set Intersection, PV-PSI）。研究旨在设计一种支持公开验证且高效的PSI协议，以应对恶意攻击者的威胁。

研究流程
本研究的工作流程可以分为四个主要阶段：发送方设置、接收方设置、发送方计算以及接收方结果验证与检索。以下是各阶段的详细描述：

1. 发送方设置

   • OPRF预处理：双方通过DH-OPRF协议对发送方的集合进行预处理，将其转换为经过哈希映射的新集合。
   • 哈希分桶：发送方使用布谷鸟哈希（Cuckoo Hashing）和简单哈希（Simple Hashing）将集合元素分配到多个桶中，并记录每个桶的最大负载。
   • 分区：为了优化整体成本，发送方和接收方协商一个分区参数α，将表垂直划分为α个子表。
   • 计算多项式系数：发送方为每个子表的每一行定义多项式，其根为行中的元素，并计算这些多项式的系数。
   • 批处理：发送方将每个子表的列转换为向量，并将这些向量打包成多个明文多项式。

2. 接收方设置

   • OPRF预处理：接收方同样通过DH-OPRF协议对其集合进行预处理。
   • 布谷鸟哈希：接收方使用布谷鸟哈希将其集合元素分配到多个桶中。
   • 批处理：接收方将哈希表转换为向量，并将其打包成多个FHE明文多项式。
   • 窗口化：为了降低电路深度，接收方根据窗口化参数l计算每个多项式的幂次分量。

3. 发送方计算

   • 发送方对接收方提供的密文进行同态计算，生成新的密文向量。
   • 对未提供的密文，发送方生成相应的标签并发送给接收方。
   • 发送方计算同态内积，并返回结果。

4. 接收方结果验证与检索

   • 接收方（或可信第三方）使用公钥生成密文的验证值，并验证计算结果的正确性。
   • 如果验证通过，接收方解密所有密文，并输出对应的交集元素。

研究还引入了Fiore等人提出的抗碰撞同态哈希函数（Collision-Resistant Homomorphic Hash Function），并结合剩余数系统（Residue Number System, RNS）对其进行优化，以支持高效的数据压缩和验证。

主要结果
研究在以下几个方面取得了重要成果： 1. 公开可验证性：通过抗碰撞同态哈希函数，接收方能够验证发送方计算结果的正确性和完整性，而无需泄露任何额外信息。 2. 高效性：协议仅需两轮交互，通信复杂度为O(|y| log |x|)，计算复杂度为O(|x|^2 + |x||y|)。实验表明，该协议的性能接近当前最先进的不平衡PSI协议。 3. 安全性：协议在恶意攻击模型下实现了全模拟安全性（Full Simulation-Based Security），能够抵御恶意接收方和发送方的攻击。 4. RNS优化：通过RNS表示法和批处理技术，显著提升了FHE的性能。

结论及其意义
本研究提出了一种公开可验证的私有集合交集协议，解决了现有PSI协议在恶意攻击模型下无法验证计算结果的问题。该协议不仅具有较高的安全性，还通过RNS和批处理技术实现了高效的计算和通信性能。其科学价值在于填补了公开可验证PSI协议的研究空白，为隐私保护领域的理论发展提供了新思路。应用价值体现在其能够广泛应用于隐私保护场景，如远程诊断、社交网络隐私保护等。

研究亮点
1. 创新性方法：首次将抗碰撞同态哈希函数与RNS结合，设计了一种高效的公开可验证PSI协议。 2. 高效性：协议仅需两轮交互，且支持批处理和RNS优化，显著降低了计算和通信开销。 3. 安全性：在恶意攻击模型下实现了全模拟安全性，能够抵御多种攻击方式。

其他有价值内容
研究还提出了未来工作的方向，例如如何进一步降低通信复杂度，为后续研究提供了明确的目标。此外，实验部分详细比较了该协议与现有协议的性能，验证了其在实际应用中的可行性。