💻 computer science

SafeStats: Efficient 2PC Protocols for Data Statistic-Related Functions

SafeStats 是一个专为统计分析量身定制的高效安全两方计算工具包，它通过专门的协议优化了频率计数、排序和非线性数学函数，与通用库相比实现了显著的速度提升和通信量减少。

原作者： Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

发布于 2026-07-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正和一位朋友试图一起解开一个谜团，但你们都有一个严格的规则：绝不能向对方展示各自的私人线索。也许你们是在比较银行账户以查看谁更有钱，而又不泄露实际数字；或者是在检查医疗记录是否符合某种疾病模式，而不暴露自己的健康史。这就是**安全双向计算（Secure Two-Party Computation, 2PC）**的世界。把它想象成一个神奇的、锁着的房间，两个人在里面混合各自的秘密原料来烘焙一个蛋糕（结果），但绝不会让对方窥视到自己原本的储藏室。长期以来，科学家们已经构建了惊人的工具，帮助在这样的锁闭房间里进行简单的数学运算，比如加法或乘法。但当涉及到更复杂的任务时——比如对一组秘密年龄进行排序，或者统计有多少人符合特定的类别——旧有的工具往往显得缓慢、笨重，且在现实生活中使用成本过高。

于是，有了 SAFESTATS，这是一个由刘探仁（Tanren Liu）及其团队设计的全新工具包，旨在让这些统计学上的谜题变得更容易解决。如果说旧的方法像是通过将一副扑克牌中的每一张牌都与其它每一张牌进行逐一对比来排序，那么 SAFESTATS 就像拥有一位超级聪明的助手，能够通过一次流畅的动作就完成整副牌的排序。该团队意识到，大多数统计任务都可以归结为三个主要工作：统计出现频率、按顺序排列以及进行一些复杂的非线性数学运算。通过为这三项工作发明巧妙的捷径，他们创建了一个系统，该系统比以往更快，且在两个守秘人之间需要的“交谈”（通信）也更少。在测试中，他们的这种新方法在某些任务上比之前的尝试快了多达 20 倍，证明了你可以在保护数据隐私的同时进行复杂的数据分析，而不必为了等待答案而耗费无尽的时间。

SAFESTATS 的三大魔术技巧

研究人员首先观察了一个标准的电子表格程序（如 Microsoft Excel），以了解人们在进行数据分析时究竟在做什么。他们发现，几乎所有的操作——无论是寻找“出现次数最多”的数字（众数）、“中间”数字（中位数），还是运行卡方检验（Chi-Square test）——都依赖于仅仅三个核心构建模块。SAFESTATS 重新设计了这三个模块，使其能够秘密且高效地运作。

1. 用于计数的“位移”技巧（The "Shift" Trick）
想象你有一排 100 个空盒子，你想统计一个秘密数字（例如“7”）在一段数据中出现了多少次。旧的方法是针对列表中的每一个项目询问：“这个数字是 7 吗？”如果你有 100 万个项目，你就得问 100 万个问题，这非常耗时。
SAFESTATS 使用的是“位移”技巧。想象你有一个处于开启状态的单向开关，而其他开关都是关闭的。如果你的秘密数字是 7，你只需将那个“开启”的灯光向右滑动 7 个位置。现在，灯光位于第 7 个盒子里。你对秘密列表中的每一项都这样做，但你做的方式是没人知道你把灯移动到了哪个盒子。最后，你只需统计每个盒子里的灯的总数。如果第 7 个盒子有 50 盏灯，你就知道数字 7 出现了 50 次。这种“滑动”方法非常快，因为它避免了缓慢、重复的“是否相等？”这类提问。团队发现，这种方法使计数速度提高了 4 到近 8 倍，并减少了双方交换的数据量，程度也相仿。

2. 用于排序的“桶”技巧（The "Bucket" Trick）
对秘密数据进行排序通常是一场噩梦，因为这需要通过比较数字的大小来判断。但如果根本不需要进行比较呢？SAFESTATS 使用了一种称为“计数排序”（Counting Sort）的方法，这在你要排序的数字并不大时（比如排序 0 到 100 之间的年龄，而不是排序随机的巨大数字）非常完美。
这就像一个拥有 100 个信箱的邮局。你不需要问“这封信是属于第 5 号还是第 6 号信箱的？”，你只需将信件投入与其编号匹配的信箱即可。SAFESTATS 秘密地执行此操作。他们使用一种特殊的“段指示器”（segment indicator）协议。想象你有一个秘密数字列表。与其一个接一个地排序，该系统会创建一个“映射图”，说明“所有的 5 号数字都属于最终列表中的这个特定范围”。然后，它将所有的 5 号数字作为一个整体放入该范围内。这绕过了对缓慢、秘密比较的需求。对于数值范围较小的数据集，这种新方法被发现比现有最好的方法快 3.4 到 20.5 倍，并将通信成本降低了高达 7.6 倍。

3. 用于复杂数学的“二分”技巧（The "Bisection" Trick）
某些统计公式涉及复杂的数学运算，如平方根或对数，这些在秘密计算中很难处理。通常的做法是先将数字缩小到一个可控的大小（就像在地图上缩小比例尺进行缩放），然后利用多项式公式来猜测答案。缓慢的部分在于确定“要缩放多少”。
旧的方法就像是通过逐页翻阅书籍来寻找某个特定的词。SAFESTATS 使用的是“二分法”，这就像是在玩“猜数字”游戏。与其检查每一页，不如将书对半切开，检查目标词是在前半部分还是后半部分，然后再次将那一半对半切开。你不断地将搜索空间减半，直到找到需要调整数字的确切位置。这种“分而治之”的方法将这些数学函数的处理时间减少了 1.2 到 1.7 倍，同时也节省了一些通信时间。

总结：卡方检验

为了证明其工具包的有效性，研究人员在 14 种不同的现实世界统计场景中测试了 SAFESTATS。其中一个突出的例子是卡方检验，这是一种常用于观察两件事是否相关的常用方法（例如，穿红衣服是否会影响你的运气）。
当他们尝试使用旧的通用型工具来运行此项测试时，过程既缓慢又频繁通信。但当他们使用 SAFESTATS 时，结果令人印象深刻：测试运行速度提高了 1.5 倍，且双方需要交换的数据量减少了 4.2 倍。

论文并不仅仅是提出了这些结论；他们实际上构建了该系统并运行了数据。他们表明，通过专注于统计分析的特定需求——而不是试图做一个“万能型”工具——他们可以创造出一种更高效的方式，在获取所需答案的同时保持数据的私密性。这提醒我们，有时解决问题最好的方式不是造一把更大的锤子，而是发明一把更好的螺丝刀。

技术摘要：SAFESTATS

问题陈述

对敏感数据集（如医疗记录、金融交易）进行统计分析对于决策至关重要，但这也引发了显著的隐私担忧。虽然安全双方计算（2PC）在低层原语（加法、乘法）和机器学习应用方面已取得了显著进展，但在特定统计函数方面仍然效率低下。现有的方法通常试图通过直接组合通用的 2PC 原语来重现统计操作（例如中位数、秩、众数）。这种“天真”的组合会导致极高的开销；例如，即使使用最先进的协议，计算 $2^{12}$ 个元素的秩（Rank）函数也可能耗时超过 18 分钟。主要的瓶颈在于对昂贵的安全相等性测试、安全比较以及无法很好扩展到涉及具有小且可枚举特征域的大规模数据集的顺序电路深度的依赖。

方法论

作者提出了 SAFESTATS，一个专为 2PC 统计分析定制的安全工具包。开发过程通过分析 Microsoft Excel 的统计库，发现大多数统计操作依赖于三个核心构建模块：频率计数、排序和非线性数学函数。SAFESTATS 为这些模块引入了专门且高效的 2PC 协议，尽可能避免使用通用原语。

1. 安全频率计数（基于移位的策略）

传统方法通过对每个输入元素执行 $m$ 次相等性测试来计算频率，导致产生 $O(m\ell)$ 次不经意传输（OT）调用。

创新点： SAFESTATs 观察到，检查输入 $x$ 是否等于任何值 $v \in [0, m-1]$ 的结果构成了一个布尔单位向量 $\vec{e}_x$ 。该协议不再通过 $m$ 次相等性测试来构建此向量，而是将 $\vec{e}_x$ 视为基础单位向量 $\vec{e}_0$ 经过偏移量 $x$ 右移后的版本。
机制： 该协议利用一种基于移位的安全策略，即随机向量不经意移位评估（ $F_{RVOSE}$ ）。它用单个向量移位操作取代了 $m$ 次相等性测试。
优化： 对于众数频率超过 $n/2$ 的情况，作者引入了基于**中国剩余定理（CRT）**的优化。该方法将大的特征域分解为较小的互质子域，从而允许构建更短的频率向量并实现模式（mode）的局部重建。

2. 安全排序（基于计数的带区间指示器方法）

通用的安全排序（例如基于安全比较的排序）受限于高电路深度和通信轮数，其成本主要由安全比较决定。

创新点： SAFESTATS 提出了一种基于计数的安全排序，消除了对安全比较的需求。
机制： 该协议由频率向量构建（使用上述方法）和元素插入组成。对于插入过程，它引入了一个安全区间指示器协议。该协议生成一个在特定区间 $[a, b]$ 上为 1 且在其他地方为 0 的秘密共享向量。
效率： 通过使用区间指示器，所有具有相同值的元素可以通过一次逐元素乘法插入到输出向量中，从而在插入阶段实现了常数级（ $O(1)$ ）的电路深度。这使 OT 复杂度从 $O(n \log n \log(nm))$ 降低到 $O(n(m + \log m))$ 。
特例（百分位数）： 意识到百分位数不需要完整的排序，作者将问题重新定义为一个区间测试问题。通过检查频率前缀和向量中包含目标秩 $k$ 的区间，他们避免了完整排序，从而进一步优化了性能，特别是在特征域较小时。

3. 安全非线性数学函数（基于二分的范围缩减）

非线性函数（如对数、平方根）的安全评估通常遵循“先缩减范围再近似”的范式，其中最主要的成本是范围缩减（识别最高有效非零位，MSNZ）。

创新点： 现有协议通过线性、顺序扫描数字位来识别 MSNZ 位，这需要 $O(d)$ 轮通信。
机制： SAFESTATS 引入了一种基于二分的范围缩减协议。该协议不再进行顺序扫描，而是递归地划分输入并在每一步选择非零的一半。
效率： 这将 MSNZ 识别的通信轮数从 $O(d)$ 降低到 $O(\log d)$ ，显著降低了非线性函数评估的延迟。

核心贡献

安全计数函数： 一种基于移位的频率计数协议，将 OT 调用次数从 $O(m\ell)$ 降低到 $O(\log m)$ ，并具有用于众数计算的 CRT 变体。
安全排序函数： 一种基于计数的排序协议，利用安全区间指示器机制实现常数级通信轮数并避免安全比较，此外还包括针对百分位数的区间测试方法。
安全非线性函数： 一种基于二分的 MSNZ 识别协议，将通信轮数从 $O(n)$ 降低到 $O(\log n)$ ，并结合了区间压缩的多项式近似范围分析。
实现与评估： 一个完整的 SAFESTATS 实现，针对 14 种常见统计情况（包括众数、中位数、秩、卡方检验等）进行了基准测试，并与通用 2PC 库（如 EzPC）进行了对比。

结果

作者实现了 SAFESTATS 并对其 14 种统计分析案例进行了测试。结果表明，与直接使用通用 2PC 原语的基准方案相比，其表现出持续的改进：

卡方检验： 实现了 1.5 $\times$ 的运行时间加速和 4.2 $\times$ 的通信量减少。
频率计数： 与基于相等性的方法相比，实现了 4.0–7.9 $\times$ 的运行时间提升和 3.1–8.6 $\times$ 的通信量提升。
安全排序： 在场景 $m \le \log_2 n$ 时，与之前的基于比较的排序方法相比，实现了 3.4–20.5 $\times$ 的运行时间加速和 1.3–7.6 $\times$ 的通信量减少。
非线性函数： 与当前工作相比，实现了 1.2–1.7 $\times$ 的运行时间减少和 1.15–1.16 $\times$ 的通信量减少。

意义

本文声称 SAFESTATS 提供了一个实用且高效的隐私保护统计分析工具包，解决了现有 2PC 解决方案在处理实际统计应用时速度过慢的问题。通过将统计操作分解为三个核心函数并为每个函数设计专门的协议，SAFESTATS 显著降低了与安全统计分析相关的计算和通信开销。该工作在通用可组合性（UC）框架下被证明对于半诚实对手是安全的。作者强调，他们的方法使得涉及具有小特征域的大规模数据集（例如分析收入水平与受教育程度之间的关系）的安全统计分析变得可行。