作为长期做隐私计算相关项目的工程师，我一直觉得“多方安全计算”这个名字吓退了很多人——听着像纯学术圈的自娱自乐，但实际落地时候最常被问到的一个需求却是出奇地朴素：“能不能让两方各自输入一个数，比个大小，还互相不告诉对方自己的数？”这个需求的技术内核，就是MPC里最经典、也最容易被拿出来当“示意”讲的比较算法。

市面上的教程大多直接甩一堆密码学公式，看完就忘了。今天这篇我换个讲法：把比较算法的几种主流思路按“最可能被工程采用”的方式拆开，用能手算验证的小例子走完整流程，再聊一些不跑实际项目根本碰不到的坑。适合刚接触MPC、想搞懂比较算法原理的同学；也适合已经看了一堆概念、但不太清楚选型和量级的开发者。

1. 从百万富翁问题说起——安全比较到底难在哪

1.1 什么叫“安全”的比较

这个问题的源头很老：两个富翁在街上碰到，想比比谁更有钱，但谁都不愿意说出自己到底有多少资产。翻译成技术语言就是：A方持有数值x，B方持有数值y，双方想得到“x > y”这个布尔结果，同时不能有任何一方从交互过程中获知对方的明文x或y。

听起来像是个不可能任务——要比大小，总得比较两边的数吧？但密码学里确实有办法。核心思路是：双方交互的永远只是经过“加掩码”“拆碎片”“重随机化”等信息学变换后的中间结果，这些中间结果要么是随机分布、要么被数学难题保护，单独看和明文没有任何关联。

需要提醒的是，这里讨论的是“结果公开”的模型：比较结果的布尔值双方都能看到（甚至可以说，输出本身就是连乘的产物）。在工程里还有一种“结果私密”的场景，一方拿到结果另一方什么都不拿到，那需要额外设计输出分发协议，今天先不展开。

1.2 安全的威胁模型：半诚实与恶意

在动手看算法之前，必须先把安全假设说清楚，因为它直接决定算法复杂度和你在工程里的选型。

• 半诚实模型：假设参与方都“老老实实”执行协议流程，不会篡改输入、不会中途恶意发送错误数据，但会从协议产生的所有中间消息里尝试推导对方明文。这是入门和多数论文默认场景，也是下面所有示意的基础。
• 恶意模型：参与方可以任意偏离协议、篡改输入、发送垃圾信息、中途退出。要在这种环境下保障正确性和隐私性，通常需要增加大量一致性校验、零知识证明等额外机制，通信量可能暴涨几个数量级。

现实互联网场景里，参与方往往互不信任，理论上应该上恶意模型；但落地时很多团队会评估风险，先上半诚实版本跑通业务，再逐步加固。我自己做过的项目里，有一大半停留在半诚实模型，不是不重视安全，而是成本和需求要匹配。

2. 秘密共享路线的比较算法示意

先讲我认为最容易理解、也最常见的一条技术路线：基于秘密共享（Secret Sharing）的比较算法。这类算法的通用思想是，把一个秘密数值拆成多份随机碎片分发给各方，各方对碎片做运算，最后再合作还原结果。

2.1 预处理：把数值拆成比特级碎片

最常见的是加法秘密共享。假设A的私密输入是x，那么它会被拆成两片：

• A自己持有xₐ = x + r (mod 2ⁿ)，其中r是一个随机数
• B持有x_b = -r (mod 2ⁿ)

两片相加就能还原出x。单看任意一片，完全就是随机数，看不出任何关于x的信息。同理，B将自己的输入y拆成yₐ、y_b两片，把yₐ给A，留下y_b。到这里，A手里是(xₐ, yₐ)，B手里是(x_b, y_b)。

如果要比较x和y的大小，一个直观的思路是：计算差值d = x - y，然后判断d的最高位（符号位）是0还是1。可问题来了——x和y此刻都以“随机数碎片”的形式散在两个人手里，谁都不能直接做减法得到d。

这时候需要引入一个关键工具：比特级秘密共享。我们把xₐ、x_b、yₐ、y_b拆成二进制比特串，然后利用带进位传播的比特运算，在两个碎片上协同构造出“x - y”的每一位。这听着复杂，但密码学里已经有一堆成熟的子协议，比如：

• 把加法共享转成比特共享：双方各自把碎片做二进制展开，再通过一个“逐比特进位消除”交互得到每个比特的共享碎片。
• 比特级比较：从最高位（MSB）开始逐位比较，一旦发现某一位两边不同，该位的值就决定了整个数的大小关系——类似于手写十进制比大小，先看百位再看十位再看个位。

2.2 逐位比较的核心流程（无借位减法示意）

工程上我更常用一种“无借位减法”思路，本质是把“比较大小”转换成“逐位检查差值是否借位”。假设我们把x和y都表示成n比特整数，并且约定采用补码表示负数。定义：

• aᵢ = x的第i位（从低位0到高位n-1）
• bᵢ = y的第i位
• 用一个递推公式来计算“是否存在借位链”：

借位标志eᵢ的更新规则是：

• 如果aᵢ = 1且bᵢ = 0，说明这一位上x大于y，不需要向高位借位，eᵢ = 0
• 如果aᵢ = 0且bᵢ = 1，说明这一位上x小于y，必然向高位借一位，eᵢ = 1
• 如果aᵢ = bᵢ，说明这一位相等，借位状态保持不变（eᵢ = eᵢ₋₁）

从最高位向下扫描，最终借位标志e如果为1，则说明x < y；如果为0，则说明x ≥ y。整个过程只需要对比特做“与、或、非、相等判断”，不需要真正做溢出传播的复杂进位加法器。这种逐位比较法在秘密共享里特别好使，因为每一位上的(aᵢ, bᵢ)都是以碎片形式分布，但比较aᵢ和bᵢ是否相等、谁大谁小，可以只用少数几轮交互完成。

2.3 一个小例子走完全流程

为了直观，我用小规模整数来做示意。假设A的x = 5（二进制101），B的y = 3（二进制011），双方用4比特表示。

第一步：拆碎片。A生成随机数r = 9（二进制1001），则A持有的xₐ = 5 + 9 mod 16 = 14（1110），B持有的x_b = -9 mod 16 = 7（0111）。A和B拿到的是两个看上去乱七八糟的数。y的拆分同理，比如B生成随机数s = 5，则yₐ = 3 + 5 mod 16 = 8（1000）给A，y_b = -5 mod 16 = 11（1011）自己留着。

第二步：逐位比较的加密等价。在这个例子里，双方并不能直接看到对方的比特位，但他们可以在本地把自己的两个碎片合起来做“掩码运算”，生成一个只包含比较信息的中间结果。实际协议会用随机比特掩盖每一位的真实值，但掩盖后的结果仍然保留了“是否借位”的语义。

为了在这里给你一个可手算的示意，我们可以走一遍明文版的逐位扫描逻辑，感受借位链的形状：

• 第0位：x = 1，y = 1，相等，借位状态保持为0
• 第1位：x = 0，y = 1，说明y这一位更大，需要向高位借位，借位状态变为1
• 第2位：x = 1，y = 0，本应抵消一次借位，但因为我们是从低位向上的无借位减法，规则里“aᵢ=1, bᵢ=0”会清除借位状态，于是归0
• 第3位：x = 0，y = 0，相等，状态保持0

最终借位状态e = 0，所以x ≥ y。由于x = 5确实大于y = 3，判断正确。在真实MPC协议里，这个“借位状态”的每一位都被分解成两个随机碎片，双方各自操作自己的碎片，通过一轮又一轮的秘密共享布尔运算逐步更新，每个中间状态单独看都是完全随机的，不会泄露任何有效信息。

到这里你可能已经感觉到了：秘密共享路线的比较算法，本质上就是在“掩码后的碎片世界”里，复刻一套传统的逐位比较电路。每比较一个比特位，大约需要常数轮交互，但通讯量并不大。这也是它能在实际框架（比如一些主流隐私计算平台）里被广泛采用的原因。

3. 混淆电路路线：另一种比较思路

3.1 比较电路如何搭建

除了秘密共享，还有一条非常经典的路线——混淆电路（Garbled Circuit）。它的思路更“电路化”：先把要计算的函数（比如比较函数x > y）编译成一个布尔电路，然后由一方（通常叫生成方）为电路的每条导线生成两张“乱码标签”，分别对应0和1；另一方（求值方）在不知道任何一位明文的情况下，金钥式地对电路逐门求值。

对于“比较”这个函数，最直接的电路实现是：

• 先计算d = x - y（用加法器电路实现，补码表示负数是最高位为1）
• 再取d的最高位作为输出

一个n比特的减法器电路，大约需要2～3n个与门和异或门。工程上还有一种更省门的比较电路，只输出标志位而不求完整差值，大概需要n个与门和n个异或门量级。对于32位整数，这个规模在密码学电路里算是非常小的。

3.2 不经意传输在电路求值中的角色

混淆电路能成立，有一个关键前提：求值方必须在“不知道对方选的是哪个标签”的情况下，拿到自己输入比特对应的乱码标签。这个需求正好由**不经意传输（Oblivious Transfer，简称OT）**解决——OT协议允许接收方从发送方的两个标签里选择性地拿一个，而发送方不知道被选中的是哪一个。

比较算法的电路流程就是：

1. 生成方A把自己的输入x的每一位对应的两个标签都发给求值方B，其中实际的比特用哪个，A自己清楚，但B收到的标签对B来说是毫无意义的随机字符串。
2. 求值方B通过OT协议，从A手里的y相关标签中挑出自己输入比特对应的那个。
3. B拿着标签，从电路输入层一路走向输出层，每个门都根据自己手中的标签和A发来的“门真值表”算出下一层的标签。
4. 最终B根据输出标签反推出比较结果（或者只有B知道，由B再告知A，取决于协议设计）。

整个过程里最关键的一点是：B在求值时不知道自己手里那串标签对应的真实比特值，只是机械地做查表和哈希运算。消息层面全是随机掩码和伪随机数，隐私就在这种“知其然而不知其所以然”的过程中被保护住了。

3.3 两种路线的直观对比

现在把秘密共享路线和混淆电路路线放到一起对比，你就会有比较清晰的选型直觉：

从我自己的实测经验看，如果只是单纯比大小，秘密共享路线的性能通常更理想；如果整个业务本身就是长相复杂的条件逻辑（例如“如果x大于y就做A否则做B”），那把它编译进统一混淆电路里反而更自然，可以减少跨协议组合的麻烦。

4. 性能、通信量与工程选型

4.1 复杂度拆解：为什么比特长度决定开销

无论走哪条路线，比较算法的开销都跟比特长度n高度相关。秘密共享路线每次逐位比较大约需要O(n)次秘密共享布尔运算，每轮通信量大多是“每个碎片一个模数元素”。举个例子，在一个两方半诚实场景下比较32位整数，实际传输量通常只有几百字节到几KB——这点量级在局域网里来回一次不过几毫秒。

混淆电路路线则要看成百上千个与门、异或门。每个门求值时，求值方要从生成方那里拿到4条密文组成的真值表（有些优化到2条），再加上OT的通信，整体量级通常在几十KB。看起来也不大，但“每个门都要做一次哈希”的计算开销会养出一批CPU占用。

所以选型的第一条经验法则是：别按“什么方案最先进”选，按“你到底要比较多少个数、多频繁”来选。

4.2 实测量级与选型建议

我们团队曾经在一个模拟项目X里对比过两种实现，场景是两方各自持有100万条用户特征，需要按阈值做安全过滤，即局部比较后再决定是否参与后续统计：

• 基于秘密共享的比较：每百万次比较在2方机器（8核16G）上耗时约30～60秒，通信约几百MB。
• 基于混淆电路包装的完整过滤电路：整体耗时翻倍，但胜在实现逻辑简单，不需要手工拆多个协议模块。

结论很朴素：单纯比大小，秘密共享更快；如果你要做的其实是“比较+后续计算”一整套聚合流程，就不要为了省一点点通信硬拆成两个协议，直接上统一电路反而省心。

还有一点容易忽略：让参与方做同样的计算，会直接放大性能差距。如果有10方，每方都要跟其他9方各跑一遍两两比较，通信量和时延会呈平方增长。这种场景的优化思路通常是：把多方比较改成“分层次比较”，先分小组出局部极值，再让组长之间比较，把O(n²)降下来。

4.3 恶意安全下的额外开销

如果业务要求恶意安全，比如银行间对账这种不能信任合作伙伴的场景，事情就变复杂了。普通的逐位比较协议没法防御“故意传一个错误碎片导致结果错误”的攻击，常见的加固手段包括：

• 给每个碎片加上承诺（Commitment），任何一方篡改内容都能被事后发现
• 用零知识证明验证每方的输入确实是合法范围内的数，而不是临时构造的恶意值
• 在比较电路的关键路径上增加一致性检查门，任何输入不一致都会导致输出无法通过校验

这些加固会让通信量和计算量暴涨好几倍甚至一个数量级。实际项目里的做法往往是“先半诚实跑通，再给关键路径加校验”。我的体会是，恶意安全不是非黑即白的选项，很多时候可以按“可信级别”混搭——核心数据比较上恶意协议，非核心的聚合计算上半诚实协议，整体性能与安全的平衡会好很多。

5. 落地过程中我踩过的坑

聊几个我在真实项目里踩过、但很少在论文里看到明说的坑。

5.1 符号数和无符号数的地狱

你以为比较的就是“整数”，但协议内部默认是按无符号二进制处理的。如果业务数值可能是负数，你必须在输入阶段就把符号位融入电路或碎片编码，否则-2在补码表示下会变成一个大正数，比较结果整个反掉。最安全的做法是：统一约定用补码表示，并且在比较协议里直接比较“最高位的翻转结果”。我自己就犯过这个错——在模拟项目X里对齐双方数据时，一端传的是无符号数，另一端传的是有符号数，结果跑了几天数据才被业务方发现异常。

5.2 比特长度不是“刚好够用”

很多入门教程喜欢用8位、16位展示流程，但真实数值域的宽度直接影响安全性和性能。比特长度越短，被暴力枚举出明文的风险越高；比特长度越长，通信开销线性上涨。工程上最少也要给业务数值留足余量，比如可能出现的最大值是1000，那至少要上11～12位，不要刚好用10位。另外固定端序也很重要，建议从第一天就强制所有参与方用大端序或小端序中的一种，否则在逐位比较时“最高位”会变成“最低位”。

5.3 比较结果泄露也要小心

就算算法本身没泄露双方明文，最终比较结果的分布也可能泄露额外信息。比如反复比较同一个x与很多个不同的y，对方可以从“大于/小于”结果的分布里反推出x的大致范围。这在隐私计算里叫“输出推断攻击”。如果你的场景存在这种反复比较，建议在输出端做扰动了——例如最终结果带概率性噪声，或者增加一次安全聚合层，防止单一比较结果被大量采集。

5.4 把随机数的质量当回事

秘密共享的安全性完全建立在随机数的不可预测性上。我见过有框架为了“优化性能”直接用了可预测的伪随机生成器种子，结果碎片之间的相关性被对方利用，隐私瞬间崩溃。工程上请务必使用密码学安全的随机数生成器（CSPRNG），并且定期轮换种子。别信“我的业务数据不值钱”这种话——一旦习惯不好，值钱的数据迟早出问题。

回头再看整条技术脉络：秘密共享比较算法像在“拆开的数字世界”里手工完成逐位借位，清晰且高效；混淆电路比较算法像给电路上一层密码学釉彩，适合嵌入复杂逻辑流。两者都为同一个“跨信任域比大小”的问题提供了可计算、可验证的答案。至于选哪条，我个人的经验是：先画清你的数据流转图，再决定协议族，而不是反过来被某个框架的API牵着走。