本文研究安全多方计算(MPC)中的洗牌(shuffle)协议,特别是针对 Shamir 秘密共享的洗牌操作。洗牌是许多 MPC 任务(如排序、 oblivious 数据结构)的基础原语,其效率直接影响上层应用的可扩展性。现有构造要么产生非均匀的洗牌结果(安全性不足),要么通信和轮数复杂度很高,甚至在某些情况下随参与方数量呈指数级增长。本文提出两种新的洗牌协议,首次在均匀洗牌的前提下,将通信复杂度降至 O((k+l)n^2 m log m / log k),其中 n 为参与方数量,m×l 为输入矩阵规模,k≤m 为可调参数。第一种协议具体效率高,适合实际部署;第二种协议达到目前最优的在线通信量 O(nml) 和 O(n) 轮复杂度。其关键技术贡献是一种新颖的排列共享技术,利用较小的排列矩阵来表示排列,从而显著降低置换应用的通信开销。第一个协议通过顺序应用独立的秘密排列来实现均匀洗牌,第二个协议基于洗牌相关性(shuffle correlation)实现最优在线复杂度。此外,作者将洗牌相关性扩展至支持保证输出交付(guaranteed output delivery)的场景,提出 SLIDE 协议,这是首个同时达到 O(nml) 在线通信量和保证输出交付的洗牌协议。构建仅依赖任何满足域大小大于 n 的场上的基本 Shamir 秘密共享,无需额外密码学假设。实验结果表明,相比已有工作,在线效率和总成本均有显著提升。论文适合 MPC 研究者、系统实现者以及需要高性能安全计算的从业者阅读。
💡 推荐理由: 洗牌协议是 MPC 中排序、隐私数据库等高级功能的性能瓶颈。本文首次在保证均匀性和输出交付的同时实现线性在线通信,可显著降低多方计算在大规模数据上的开销,推动安全计算在实际场景中的落地。
🎯 建议动作: 研究跟进