作为长期做隐私计算相关项目的工程师我一直觉得“多方安全计算”这个名字吓退了很多人——听着像纯学术圈的自娱自乐但实际落地时候最常被问到的一个需求却是出奇地朴素“能不能让两方各自输入一个数比个大小还互相不告诉对方自己的数”这个需求的技术内核就是MPC里最经典、也最容易被拿出来当“示意”讲的比较算法。市面上的教程大多直接甩一堆密码学公式看完就忘了。今天这篇我换个讲法把比较算法的几种主流思路按“最可能被工程采用”的方式拆开用能手算验证的小例子走完整流程再聊一些不跑实际项目根本碰不到的坑。适合刚接触MPC、想搞懂比较算法原理的同学也适合已经看了一堆概念、但不太清楚选型和量级的开发者。1. 从百万富翁问题说起——安全比较到底难在哪1.1 什么叫“安全”的比较这个问题的源头很老两个富翁在街上碰到想比比谁更有钱但谁都不愿意说出自己到底有多少资产。翻译成技术语言就是A方持有数值xB方持有数值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-1bᵢ 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二进制101B的y 3二进制011双方用4比特表示。第一步拆碎片。A生成随机数r 9二进制1001则A持有的xₐ 5 9 mod 16 141110B持有的x_b -9 mod 16 70111。A和B拿到的是两个看上去乱七八糟的数。y的拆分同理比如B生成随机数s 5则yₐ 3 5 mod 16 81000给Ay_b -5 mod 16 111011自己留着。第二步逐位比较的加密等价。在这个例子里双方并不能直接看到对方的比特位但他们可以在本地把自己的两个碎片合起来做“掩码运算”生成一个只包含比较信息的中间结果。实际协议会用随机比特掩盖每一位的真实值但掩盖后的结果仍然保留了“是否借位”的语义。为了在这里给你一个可手算的示意我们可以走一遍明文版的逐位扫描逻辑感受借位链的形状第0位x 1y 1相等借位状态保持为0第1位x 0y 1说明y这一位更大需要向高位借位借位状态变为1第2位x 1y 0本应抵消一次借位但因为我们是从低位向上的无借位减法规则里“aᵢ1, bᵢ0”会清除借位状态于是归0第3位x 0y 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比特的减法器电路大约需要23n个与门和异或门。工程上还有一种更省门的比较电路只输出标志位而不求完整差值大概需要n个与门和n个异或门量级。对于32位整数这个规模在密码学电路里算是非常小的。3.2 不经意传输在电路求值中的角色混淆电路能成立有一个关键前提求值方必须在“不知道对方选的是哪个标签”的情况下拿到自己输入比特对应的乱码标签。这个需求正好由**不经意传输Oblivious Transfer简称OT**解决——OT协议允许接收方从发送方的两个标签里选择性地拿一个而发送方不知道被选中的是哪一个。比较算法的电路流程就是生成方A把自己的输入x的每一位对应的两个标签都发给求值方B其中实际的比特用哪个A自己清楚但B收到的标签对B来说是毫无意义的随机字符串。求值方B通过OT协议从A手里的y相关标签中挑出自己输入比特对应的那个。B拿着标签从电路输入层一路走向输出层每个门都根据自己手中的标签和A发来的“门真值表”算出下一层的标签。最终B根据输出标签反推出比较结果或者只有B知道由B再告知A取决于协议设计。整个过程里最关键的一点是B在求值时不知道自己手里那串标签对应的真实比特值只是机械地做查表和哈希运算。消息层面全是随机掩码和伪随机数隐私就在这种“知其然而不知其所以然”的过程中被保护住了。3.3 两种路线的直观对比现在把秘密共享路线和混淆电路路线放到一起对比你就会有比较清晰的选型直觉维度秘密共享比较混淆电路比较核心工具随机碎片、逐位借位链乱码标签、OT协议通信轮数随比特长度线性通常较小与电路深度成正比比较电路深度较小通信量每比特多位掩码但整体较小每个门都要传输真值表门越多量越大计算开销大量模加、异或开销低大量哈希或对称加密运算适合场景两方/三方做比较、求最值复杂函数整体电路的比较子模块从我自己的实测经验看如果只是单纯比大小秘密共享路线的性能通常更理想如果整个业务本身就是长相复杂的条件逻辑例如“如果x大于y就做A否则做B”那把它编译进统一混淆电路里反而更自然可以减少跨协议组合的麻烦。4. 性能、通信量与工程选型4.1 复杂度拆解为什么比特长度决定开销无论走哪条路线比较算法的开销都跟比特长度n高度相关。秘密共享路线每次逐位比较大约需要O(n)次秘密共享布尔运算每轮通信量大多是“每个碎片一个模数元素”。举个例子在一个两方半诚实场景下比较32位整数实际传输量通常只有几百字节到几KB——这点量级在局域网里来回一次不过几毫秒。混淆电路路线则要看成百上千个与门、异或门。每个门求值时求值方要从生成方那里拿到4条密文组成的真值表有些优化到2条再加上OT的通信整体量级通常在几十KB。看起来也不大但“每个门都要做一次哈希”的计算开销会养出一批CPU占用。所以选型的第一条经验法则是别按“什么方案最先进”选按“你到底要比较多少个数、多频繁”来选。4.2 实测量级与选型建议我们团队曾经在一个模拟项目X里对比过两种实现场景是两方各自持有100万条用户特征需要按阈值做安全过滤即局部比较后再决定是否参与后续统计基于秘密共享的比较每百万次比较在2方机器8核16G上耗时约3060秒通信约几百MB。基于混淆电路包装的完整过滤电路整体耗时翻倍但胜在实现逻辑简单不需要手工拆多个协议模块。结论很朴素单纯比大小秘密共享更快如果你要做的其实是“比较后续计算”一整套聚合流程就不要为了省一点点通信硬拆成两个协议直接上统一电路反而省心。还有一点容易忽略让参与方做同样的计算会直接放大性能差距。如果有10方每方都要跟其他9方各跑一遍两两比较通信量和时延会呈平方增长。这种场景的优化思路通常是把多方比较改成“分层次比较”先分小组出局部极值再让组长之间比较把O(n²)降下来。4.3 恶意安全下的额外开销如果业务要求恶意安全比如银行间对账这种不能信任合作伙伴的场景事情就变复杂了。普通的逐位比较协议没法防御“故意传一个错误碎片导致结果错误”的攻击常见的加固手段包括给每个碎片加上承诺Commitment任何一方篡改内容都能被事后发现用零知识证明验证每方的输入确实是合法范围内的数而不是临时构造的恶意值在比较电路的关键路径上增加一致性检查门任何输入不一致都会导致输出无法通过校验这些加固会让通信量和计算量暴涨好几倍甚至一个数量级。实际项目里的做法往往是“先半诚实跑通再给关键路径加校验”。我的体会是恶意安全不是非黑即白的选项很多时候可以按“可信级别”混搭——核心数据比较上恶意协议非核心的聚合计算上半诚实协议整体性能与安全的平衡会好很多。5. 落地过程中我踩过的坑聊几个我在真实项目里踩过、但很少在论文里看到明说的坑。5.1 符号数和无符号数的地狱你以为比较的就是“整数”但协议内部默认是按无符号二进制处理的。如果业务数值可能是负数你必须在输入阶段就把符号位融入电路或碎片编码否则-2在补码表示下会变成一个大正数比较结果整个反掉。最安全的做法是统一约定用补码表示并且在比较协议里直接比较“最高位的翻转结果”。我自己就犯过这个错——在模拟项目X里对齐双方数据时一端传的是无符号数另一端传的是有符号数结果跑了几天数据才被业务方发现异常。5.2 比特长度不是“刚好够用”很多入门教程喜欢用8位、16位展示流程但真实数值域的宽度直接影响安全性和性能。比特长度越短被暴力枚举出明文的风险越高比特长度越长通信开销线性上涨。工程上最少也要给业务数值留足余量比如可能出现的最大值是1000那至少要上1112位不要刚好用10位。另外固定端序也很重要建议从第一天就强制所有参与方用大端序或小端序中的一种否则在逐位比较时“最高位”会变成“最低位”。5.3 比较结果泄露也要小心就算算法本身没泄露双方明文最终比较结果的分布也可能泄露额外信息。比如反复比较同一个x与很多个不同的y对方可以从“大于/小于”结果的分布里反推出x的大致范围。这在隐私计算里叫“输出推断攻击”。如果你的场景存在这种反复比较建议在输出端做扰动了——例如最终结果带概率性噪声或者增加一次安全聚合层防止单一比较结果被大量采集。5.4 把随机数的质量当回事秘密共享的安全性完全建立在随机数的不可预测性上。我见过有框架为了“优化性能”直接用了可预测的伪随机生成器种子结果碎片之间的相关性被对方利用隐私瞬间崩溃。工程上请务必使用密码学安全的随机数生成器CSPRNG并且定期轮换种子。别信“我的业务数据不值钱”这种话——一旦习惯不好值钱的数据迟早出问题。回头再看整条技术脉络秘密共享比较算法像在“拆开的数字世界”里手工完成逐位借位清晰且高效混淆电路比较算法像给电路上一层密码学釉彩适合嵌入复杂逻辑流。两者都为同一个“跨信任域比大小”的问题提供了可计算、可验证的答案。至于选哪条我个人的经验是先画清你的数据流转图再决定协议族而不是反过来被某个框架的API牵着走。
