2025-11-17T12:40:13.303016

Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection

Arpaci, Boutaba, Kerschbaum
An important function of collaborative network intrusion detection is to analyze the network logs of the collaborators for joint IP addresses. However, sharing IP addresses in plain is sensitive and may be even subject to privacy legislation as it is personally identifiable information. In this paper, we present the privacy-preserving collection of IP addresses. We propose a single collector, over-threshold private set intersection protocol. In this protocol $N$ participants identify the IP addresses that appear in at least $t$ participant's sets without revealing any information about other IP addresses. Using a novel hashing scheme, we reduce the computational complexity of the previous state-of-the-art solution from $O(M(N \log{M}/t)^{2t})$ to $O(t^2M\binom{N}{t})$, where $M$ denotes the dataset size. This reduction makes it practically feasible to apply our protocol to real network logs. We test our protocol using joint networks logs of multiple institutions. Additionally, we present two deployment options: a collusion-safe deployment, which provides stronger security guarantees at the cost of increased communication overhead, and a non-interactive deployment, which assumes a non-colluding collector but offers significantly lower communication costs and applicable to many use cases of collaborative network intrusion detection similar to ours.
academic

Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection

基本信息

  • 论文ID: 2510.12045
  • 标题: Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection
  • 作者: Onur Eren Arpaci, Raouf Boutaba, Florian Kerschbaum (University of Waterloo)
  • 分类: cs.CR (Cryptography and Security), cs.NI (Networking and Internet Architecture)
  • 发表时间: 2025年10月14日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.12045

摘要

协作网络入侵检测的一个重要功能是分析协作者的网络日志以识别共同的IP地址。然而，明文共享IP地址是敏感的，甚至可能受到隐私法律的约束，因为它是个人可识别信息。本文提出了IP地址的隐私保护收集方法，提出了一个单收集器、超阈值私有集合交集协议。在该协议中，N个参与者识别出现在至少t个参与者集合中的IP地址，而不泄露关于其他IP地址的任何信息。通过新颖的哈希方案，将之前最先进解决方案的计算复杂度从O(M(Nlog⁡M/t)2t)O(M(N \log{M}/t)^{2t})降低到O(t2M(Nt))O(t^2M\binom{N}{t})，其中M表示数据集大小。这种降低使得将协议应用于真实网络日志在实践中变得可行。

研究背景与动机

问题定义

协作网络入侵检测面临的核心问题是如何在保护隐私的前提下识别多机构攻击。研究表明，75%的机构攻击会在一天内扩散到第二个机构，超过40%会在一小时内扩散。攻击者通常利用少数外部IP地址同时攻击多个机构，如果某个外部IP在特定时间窗口内连接到至少t个机构，则可以95%的召回率将其分类为恶意。

隐私挑战

传统方法要求机构以明文形式共享网络日志，这带来了严重的隐私风险：

  1. 法律合规性：IP地址被GDPR、PIPEDA、CCPA等法律认定为个人可识别信息
  2. 数据敏感性：原始网络数据比安全警报更敏感，包含大量无关的敏感信息
  3. 数据规模：原始数据比安全警报大几个数量级，使现有解决方案在计算上不可行

现有方法局限性

  • Kissner and Song 26：需要O(N)通信轮次，计算复杂度O(N³M³)
  • Mahdavi et al. 34：虽然改进了通信复杂度，但计算成本仍然过高，复杂度为O(M(N logM/t)²ᵗ)

核心贡献

  1. 新颖哈希方案：提出了创新的哈希算法，将计算复杂度从O(M(N logM/t)²ᵗ)降低到O(t²M(N choose t))，实现了对M的线性复杂度
  2. 实用性提升：使协议能够处理真实规模的网络日志，在33个参与机构、最多144,045个IP的设置下170秒内完成检测
  3. 双重部署选项：
    • 抗合谋部署：提供更强安全保证，但通信开销更高
    • 非交互部署：假设非合谋收集器，显著降低通信成本
  4. 安全性证明：在半诚实多方计算模型下证明了协议的安全性
  5. 实际验证：使用CANARIE IDS项目的真实网络日志进行了评估

方法详解

任务定义

Over-Threshold Multiparty Private Set Intersection (OT-MP-PSI)：

  • 输入：N个参与者，每个持有最多M个元素的集合Si
  • 输出：识别出现在至少t个集合中的元素，不泄露低于阈值的元素信息
  • 约束：半诚实安全模型，参与者遵循协议但可能尝试学习额外信息

核心技术组件

1. Shamir秘密共享

使用(t,n)阈值方案，任何t方可以重构秘密V，少于t方无法获得任何信息：

P(x) = c_{t-1}x^{t-1} + c_{t-2}x^{t-2} + ... + c_1x + V

2. 遗忘伪随机函数(OPRF)

参与者学习H_K(x)而不了解密钥K，密钥持有者不了解输入x或输出值。

3. 遗忘伪随机秘密共享(OPR-SS)

结合秘密共享和OPRF的安全属性，允许参与者从密钥持有者获得唯一的秘密份额。

协议架构

非交互部署

  1. 份额创建：每个参与者为其集合中的每个元素创建秘密份额
  2. 哈希映射：使用新的哈希方案将份额映射到大小为1的桶中
  3. 重构：聚合器尝试所有t个参与者的组合进行Lagrange插值
  4. 结果通知：聚合器通知参与者成功重构的索引

抗合谋部署

使用OPR-SS协议替代共享密钥，通过多密钥OPRF协议计算哈希函数，提供更强的抗合谋保证。

技术创新点

新哈希方案

核心思想：使用大小为1的桶避免哈希冲突，而不是容纳冲突：

  1. 冲突处理：当多个元素映射到同一桶时，使用伪随机排序选择最小的一个
  2. 多表策略：每个参与者创建多个表，确保丢失的值在其他表中出现
  3. 失败概率控制：通过20个表将失败概率控制在2⁻⁴⁰以下

关键优势：

  • 聚合器只需尝试参与者组合，而非份额组合
  • 复杂度从指数降至线性（对M而言）
  • 避免了传统分桶方法的大常数因子

优化技术

  1. 排序反转：连续两表使用相同排序函数，偶数表反转排序
  2. 空桶利用：进行第二次插入利用第一次插入后的空桶

实验设置

数据集

  • 真实数据：CANARIE IDS项目54个机构的网络连接日志
  • 时间范围：2023年11月1-8日，每日约80亿日志条目
  • 数据规模：每日约700GB（gzip压缩）
  • 处理方式：按小时批次处理，提取外部IP到内部IP的连接

评价指标

  • 重构时间：聚合器完成重构的时间
  • 份额生成时间：单个参与者创建份额的时间
  • 通信复杂度：协议的总通信开销
  • 正确性：失败概率验证

对比方法

  • Mahdavi et al. 34：当前最先进的OT-MP-PSI解决方案
  • 理论上界：与计算的失败概率上界比较

实现细节

  • 编程语言：Julia，430行代码
  • 密码学库：SHA.jl, Nettle.jl
  • 有限域：61位梅森素数
  • 硬件环境：8×Intel Xeon E7-8870处理器，80物理核心，1TB内存

实验结果

主要结果

性能对比

与Mahdavi et al. 34相比：

  • 速度提升：至少两个数量级，最高23,066倍
  • 可扩展性：在M=10⁵时，本方法需要数百秒，对比方法需要数天

真实数据表现

在CANARIE数据上的表现：

  • 平均重构时间：170秒
  • 最大重构时间：438秒（40个机构，220,011个IP）
  • 平均参与机构：33个
  • 平均最大集合大小：144,045个IP

复杂度分析

计算复杂度

  • 聚合器：O(t²M(N choose t))
  • 参与者（非交互）：O(tM)
  • 特殊情况：N=t=2时为O(M)，N=t时为O(N²M)

通信复杂度

  • 非交互部署：O(tMN)
  • 抗合谋部署：O(tkMN)，5轮通信

正确性验证

  • 理论失败概率：2⁻⁴⁰
  • 实验验证：10⁷次试验中，实际失败次数远低于理论上界
  • 表数优化：从理论的28个表优化至实际的20个表

相关工作

OT-MP-PSI解决方案

  1. Kissner and Song 26：首个解决方案，使用多项式环表示，O(N³M³)复杂度
  2. Mahdavi et al. 34：常数轮次，O(M(N logM/t)²ᵗ)复杂度
  3. Ma et al. 33：适用于小输入集和小域，O(N|S|)复杂度

相关问题

  • 阈值私有集合交集(TPSI)：学习交集当且仅当交集大小超过阈值
  • Quorum-PSI：OT-MP-PSI的特殊情况，只有特定参与者有输出

哈希技术

  • 布谷鸟哈希：用于避免哈希冲突，广泛应用于PSI协议
  • 2D布谷鸟哈希：专为两方PSI设计，实现O(M)复杂度

结论与讨论

主要结论

  1. 实用性突破：首次使OT-MP-PSI在真实网络日志规模下实用可行
  2. 效率提升：通过新哈希方案实现了数量级的性能提升
  3. 灵活部署：提供两种部署选项适应不同安全需求
  4. 实际验证：在真实多机构网络环境中验证了协议的实用性

局限性

  1. 半诚实模型：虽然可扩展到恶意模型，但仍易受输入替换攻击
  2. 集合大小泄露：核心协议不将参与者集合大小视为私有信息
  3. 聚合器信任：非交互部署需要信任聚合器不与参与者合谋
  4. 阈值限制：当t接近N/2且N很大时，复杂度优势可能不明显

未来方向

  1. 恶意安全：扩展协议以抵御主动攻击者
  2. 动态阈值：支持多阈值计算而无额外客户端成本
  3. 大规模优化：进一步优化参与者组合的处理效率
  4. 隐私增强：探索差分隐私技术保护集合大小信息

深度评价

优点

  1. 理论贡献显著：新哈希方案是对现有技术的重要突破，将指数复杂度降至线性
  2. 实用价值高：解决了真实世界协作入侵检测的关键隐私问题
  3. 实验充分：既有理论分析又有真实数据验证，实验设置合理
  4. 工程实现完整：提供开源实现，增强可复现性
  5. 安全性严格：提供形式化安全证明和两种部署选项

不足

  1. 安全模型限制：半诚实模型在某些实际场景中可能不够强
  2. 参数选择：20个表的选择基于经验优化，理论指导不够充分
  3. 可扩展性边界：对于极大规模（如全球互联网级别）的适用性未充分探讨
  4. 比较基准有限：主要与一个基准方法比较，缺乏更全面的性能对比

影响力

  1. 学术价值：为多方安全计算领域提供了新的技术路径
  2. 实用意义：直接解决网络安全领域的实际需求
  3. 技术推广：哈希方案可能适用于其他多方计算问题
  4. 标准化潜力：有望成为协作入侵检测的标准协议

适用场景

  1. 多机构网络安全：大学、医院等同类机构的协作防护
  2. 云安全服务：安全运营中心的隐私保护日志分析
  3. 威胁情报共享：在隐私约束下的威胁指标交换
  4. 合规性要求：满足GDPR等隐私法规的数据协作

参考文献

本文引用了53篇相关文献，涵盖了密码学、网络安全、多方计算等多个领域的重要工作，为研究提供了坚实的理论基础和全面的技术背景。

总体评价：这是一篇高质量的应用密码学论文，在理论创新和实际应用之间取得了很好的平衡。新提出的哈希方案不仅在理论上有重要突破，更在实际应用中展现了显著价值。论文的实验验证充分，安全分析严格，为协作网络安全领域提供了重要的技术贡献。