学术报告：基于布谷鸟哈希和分层全同态加密的非平衡数据库递归私有集合交集协议

一、研究团队与发表信息
本研究由纽约大学阿布扎比分校网络安全中心的Eduardo Chielle和Michail Maniatakos合作完成，发表于2025年网络与分布式系统安全研讨会（NDSS Symposium 2025），会议时间为2025年2月24日至28日，论文DOI为10.14722/ndss.2025.240365。

二、学术背景与研究目标
私有集合交集（Private Set Intersection, PSI）是一种密码学协议，允许两方在不泄露各自集合中非交集信息的前提下计算交集。传统PSI协议多针对集合规模相近的场景，且通常为单次执行设计。然而，实际应用中常出现集合规模严重不对称（如URL过滤、邮件安全检测中一方集合极大而另一方极小）和需多次执行（如反复比对新数据）的需求。现有方案在此类场景下效率低下，例如每次需重新传输大集合数据。

本研究旨在解决两大核心问题：
1. 非平衡集合优化：针对发送方（Sender, S）集合远大于接收方（Receiver, R）的场景（如|X|≈2²⁰，|Y|≤64）；
2. 递归执行效率：避免重复计算，实现大集合数据“一次性传输”，后续交集仅需线性通信成本。

三、研究方法与流程
研究分为理论设计、协议优化、实验验证三阶段，核心创新在于结合分层全同态加密（Leveled FHE）和布谷鸟哈希（Cuckoo Hashing），并通过多级优化实现实时性能。

1. 基础协议设计（Protocol 1）

   • 加密与比较：S用自身密钥加密集合X并发送给R；R对每个y∈Y，计算加密差值∏(xᵢ−y)，若y∈X则结果为加密零。
     
   • 隐私保护：引入随机数rⱼ掩盖交集大小，通过乘法随机因子ρⱼ防止信息泄漏。
     
   • 问题：基础协议需O(|X|·|Y|)次同态乘法，计算深度高导致参数效率低。
     

2. 关键优化技术

   • 布谷鸟哈希与置换哈希
     
     • 布谷鸟哈希：S将X插入k个哈希表（h=3或4哈希函数），每表负载率高达87%（h=4），失败率≤2⁻⁴⁰。通过实验确定最大负载（表I），如|T|=2²⁰时支持插入911,705条目。
       
     • 置换哈希：将条目分为左（σₗ=log₂|T|）右（σᵣ=σ−σₗ）部分，仅存储右部，减少存储和通信开销。
       
   • 四重中国剩余定理（QCRT）
     
     1. RNS分解：将大模数q拆为<64比特的素数积，加速同态运算；
        
     2. NTT加速多项式乘法：复杂度从O(n²)降至O(n log n)；
        
     3. 批处理（Batching）：单密文编码n个明文，SIMD并行计算；
        
     4. 打包（Packing）：每批处理槽内进一步分k个子空间，对应k个哈希表，提升吞吐量（图1）。
        
   • 其他优化
     
     • 分区（Partitioning）：平衡计算深度与通信量，如ηₛ=ηᵣ=1时计算减半但通信翻倍；
       
     • 模切换（Modulus Switching）：降低响应密文尺寸，减少带宽消耗。
       

3. 完整协议（Protocol 2）

   • 初始化阶段：S压缩条目（σₕ≈2 log₂m+λ−1），哈希至k个表，加密后发送密文C（一次性成本）；
     
   • 递归阶段：R对每个y∈Y，计算h个潜在位置的差值，分区乘法后添加随机数，返回密文对(d⁽ⁱ⁾, r̂⁽ⁱ⁾)；S解密并验证零值，旋转结果防止位置泄漏。
     

四、实验结果与性能
实验基于Microsoft SEAL库（BFV加密方案），配置|X|≈2²⁰，|Y|∈{4,16,64}，对比现有最优方案CLR、KKRT、PSSZ：

1. 计算效率

   • Fast Setup（k=2表）：预计算0.09秒，递归交集仅0.01秒（|Y|=4）；
     
   • Fast Intersection（k=1表）：预计算0.30秒，递归0.03秒（|Y|=16）。
     
   • 优势：较CLR（2.21秒）提速1-2个数量级（表II）。
     

2. 通信开销

   • 单次交集通信量低至0.53 MiB（|Y|=4），而KKRT需57.15 MiB（表III）；
     
   • 在100 Mbps网络中，延迟从CLR的2.81秒降至0.24秒（表IV）。
     

3. 负载与安全性

   • 布谷鸟哈希负载率87%（h=4），失败概率≤2⁻⁴⁰；
     
   • 半诚实模型下安全，防止集合大小与条目位置泄漏（定理2）。
     

五、研究结论与价值
1. 科学价值
- 首个支持非平衡集合递归PSI的实用方案，填补领域空白；
- 提出QCRT四重编码策略，为FHE应用提供新优化范式。
2. 应用价值
- 实时安全：URL过滤、邮件检测等场景可在20ms（10 Gbps）或240ms（100 Mbps）内完成；
- 隐私保护：避免第三方接触敏感数据（如企业黑名单）。

六、研究亮点
1. 方法创新：首次将分层FHE与布谷鸟哈希结合，实现递归PSI；
2. 性能突破：较最优方案提速10-100倍，通信成本线性于小集合；
3. 工程贡献：开源C++实现，参数选择工具化（如负载率计算器）。

七、其他价值
实验数据为大规模PSI（如|X|>2²⁴）提供基准，参数优化方法可推广至其他FHE应用。未来工作包括恶意模型扩展与跨平台部署优化。