基于多项式运算的高效安全非平衡数据对齐框架SUDA及其在纵向隐私保护机器学习中的应用

作者及发表信息
本研究的核心作者团队来自复旦大学和字节跳动，包括Lushan Song（复旦大学/字节跳动）、Qizhi Zhang（字节跳动）、Yu Lin（字节跳动）、Haoyu Niu（复旦大学）等。该研究发表于第34届USENIX Security Symposium（USENIX安全研讨会），会议时间为2025年8月13日至15日，地点为美国西雅图。论文标题为《SUDA: An Efficient and Secure Unbalanced Data Alignment Framework for Vertical Privacy-Preserving Machine Learning》，并被收录于会议论文集（ISBN: 978-1-939133-52-6）。

学术背景
纵向隐私保护机器学习（Vertical Privacy-Preserving Machine Learning, VPPML）是隐私计算领域的重要分支，旨在解决多方在数据特征垂直分布（即各方持有相同样本ID但不同特征或标签）下的协同建模问题。例如，广告场景中，互联网公司（持有用户ID和特征）与广告商（持有用户ID和标签）需通过VPPML联合训练点击率预测模型，同时保护数据隐私。

然而，现有非平衡数据对齐方法（如基于布谷鸟哈希的Circuit-PSI）存在两大缺陷：
1. 冗余数据问题：布谷鸟哈希会引入交集外的冗余数据，导致后续安全训练通信量激增；
2. 效率瓶颈：虽可通过安全洗牌（secure shuffle）剔除冗余，但额外操作带来高昂通信开销。

SUDA的提出旨在解决上述挑战，其核心目标是通过多项式运算直接、高效地输出交集内的数据份额，避免冗余数据与洗牌操作，从而提升VPPML整体效率。

技术框架与工作流程
SUDA分为两个核心步骤：安全ID编码（Secure ID Encoding）和安全特征对齐（Secure Feature Alignment）。

1. 安全ID编码

协议设计：基于椭圆曲线密码学（Elliptic Curve Cryptography, ECC）的ECDH-PSI协议（Elliptic Curve Diffie-Hellman PSI）。
- 服务器（Ps）：本地打乱数据顺序，将样本索引作为新ID（如0至n-1），生成ECC私钥α并计算αh(Is)。
- 客户端（Pc）：生成ECC私钥β和加法同态加密（Additive Homomorphic Encryption, AHE）密钥对，加密标签后发送βh(Ic)和加密标签至Ps。
- 交集同步：Ps计算αβh(Ic)，加密标签减去随机掩码r，打乱后发送给Pc。Pc通过比对哈希值确定交集ID，同时双方获得标签份额〈y〉s和〈y〉c。

创新点：
- 通过ECC实现高效ID对齐，避免直接暴露原始ID；
- 结合AHE实现标签的秘密共享，支持后续安全训练。

2. 安全特征对齐

核心协议：

（1）批量隐私信息检索（Batch PIR）

• 特征编码：服务器使用数论变换（Number Theoretic Transform, NTT）将特征编码为多项式fk(x)=∑a_{k,j}x^j，复杂度从O(n²)降至O(n log n)。
  
• ** oblivious多项式降阶（OPR）**：基于模多项式定理（Theorem 1），将高次多项式fk(x)降阶为f̄k(x)≡fk(x) mod g(x)，其中g(x)=∏(x−z_i)（z_i为Pc的查询点）。降阶后多项式度数从O(n)降至O(n)，显著减少计算量。
  
• ** oblivious多项式求值（OPE）**：Pc通过随机多项式γk(x)掩码f̄k(x)，确保仅能解密交集内特征值，防止信息泄露。
  

（2）批量PIR-to-Share

• ** oblivious多项式插值（OPI）**：Ps生成随机份额ri,k，Pc构造基多项式rfμ(x)和cfν(x)，通过定理2（Theorem 2）将ri,k插值为多项式f̄ s_k(x)，使得f̄ s_k(z_i)=ri,k。Ps最终获得特征份额〈x〉s=ri,k，Pc通过f̄ c_k(x)=f̄k(x)−f̄ s_k(x)获得〈x〉c。
  

技术亮点：
- 多项式运算替代哈希：避免布谷鸟哈希的冗余数据问题；
- NTT加速：多项式编码复杂度优化至O(n log n)；
- 模块化设计：支持特征与标签的端到端秘密共享。

实验结果
1. 性能对比：
- 通信量：在特征维度m=1000、n=2²⁴时，SUDA比IPrivJoin减少36.45倍通信量（39.5 GB vs. 1.1 GB）；
- 耗时：在WAN设置下，SUDA运行时间比IPrivJoin快8.21倍（7215秒 vs. 879秒）。
2. Batch PIR效率：相比最先进的PIRANA框架，SUDA服务器时间提升11.53倍，客户端内存占用减少5.97倍。

案例验证：在SVHN和Character Font Images数据集上，SUDA的端到端训练（含100轮逻辑回归）总耗时显著低于基线（如SVHN：SUDA 2546秒 vs. IPrivJoin 12203秒）。

结论与价值
1. 科学价值：
- 提出首个基于多项式运算的非平衡数据对齐框架，为VPPML提供理论新范式；
- 设计OPR、OPE、OPI等新型协议，拓展了隐私计算协议库。
2. 应用价值：
- 已支持字节跳动广告业务中十亿级样本的高效对齐（24小时完成亿级数据对齐）；
- 兼容多客户端场景，可通过Spark并行化进一步加速。

亮点总结
- 直接输出交集数据：避免冗余计算与通信；
- 多项式运算创新：结合NTT、LFHE（Leveled Fully Homomorphic Encryption）实现高效安全计算；
- 实践友好性：实验证明其在WAN/LAN环境下均保持高效稳定。

局限与展望
当前SUDA需暴露交集大小n′，未来计划扩展至多方场景并进一步优化动态数据支持。