安全多方计算和点积协议

安全多方计算（MPC）

安全多方计算（Secure Multi-Party Computation，简称MPC，也称SMC或SMPC）最早由图灵奖获得者姚期智教授于1982年通过著名的“百万富翁问题”提出。

正式定义：有n个参与者\(P₁, P₂, …, P_n\)，各自拥有保密的输入信息\(X₁, X₂, …, X_n\)，他们希望共同计算一个函数 \(f(X₁, X₂, …, Xn) = (Y₁, Y₂, …, Y_n)\)。计算结束时，每个参与者\(P_i\)只能了解自己的输出\(Y_i\)，而不能获知其他任何参与方的输入信息或输出信息。

通俗理解：安全多方计算允许多个数据所有者在互不信任、没有可信第三方的情况下进行协同计算，输出计算结果，同时保证任何一方都无法得到除应得计算结果之外的任何其他信息。简言之，MPC技术可以实现数据“可用不可见”——获取数据的使用价值，却不泄露原始数据内容。

核心特性包括：

• 输入隐私性：计算过程中不泄露任何参与方的本地数据
• 计算正确性：各方最终得到正确的计算结果
• 去中心化：各参与方地位平等，不存在有特权的第三方

点积协议（Dot Product Protocol）

点积协议是安全多方计算中最基础、最常用的协议之一。

问题场景：两个参与方Alice和Bob各拥有一个向量，例如Alice拥有向量 A = (a₁, a₂, …, aₙ)，Bob拥有向量 B = (b₁, b₂, …, bₙ)。他们希望计算两个向量的点积 A·B = a₁b₁ + a₂b₂ + … + aₙbₙ，但双方都不希望对方知道自己向量的具体数值。

实现思路：点积协议通常基于同态加密等密码学技术实现。以基于Paillier同态加密体制的方案为例：Alice用同态加密公钥加密自己的向量各分量后发送给Bob；Bob在密文上直接计算点积（利用同态加密的加法同态性质），将结果返回给Alice；Alice用私钥解密得到最终的点积结果。整个过程中，Bob从未看到Alice的明文向量，Alice也从未看到Bob的向量。

应用场景：点积协议广泛用于安全计算几何、保密统计分析、保密数据挖掘等领域，是许多复杂安全多方计算协议的基础组件。

考试内容：
一个简单的解决方法是使用不经意传输协议具体步骤如下

1. A产生t-1个伪向量，一起发给B
2. B计算着t个伪向量和向量Y的点积
3. A与B使用t选一的不经意传输，得到X*Y

这个协议存在的问题：

• B有\(1/t\)的概率猜到A的结果
• 这些向量需要线性无关，负责A能得到Y的信息
• 找到t-1个有意义伪向量是很困难的

百万富翁协议（Millionaires' Protocol）

百万富翁问题是安全多方计算的起源，由姚期智于1982年提出。

问题场景：两个百万富翁Alice和Bob在街头相遇，他们都想知道谁更富有，但谁也不愿向对方透露自己财富的具体数额。更一般地，这个问题是要在双方各自保密输入的前提下比较两个数的大小。

密码学家晚餐问题（Dining Cryptographers Problem）

密码学家晚餐问题由David Chaum于1988年提出，主要用于研究匿名通信问题。

问题场景：三位密码学家Alice、Bob和Carol在一家三星级餐厅共进晚餐。侍者告诉他们：晚餐已经有人付过账了——要么是三位密码学家中的某一位，要么是美国国家安全局（NSA）付的。密码学家们想知道是不是NSA付的账，但如果是他们中的某一位付的，他们希望保护这位付款者的匿名身份。

协议解决方案：

1. 第一阶段：每对相邻的密码学家之间抛掷一枚公平硬币，硬币结果只有这两人知道，由此在每对之间建立一个随机的1比特共享秘密
2. 第二阶段：每位密码学家公开宣布一个比特。如果他没有付账，则宣布他已知的两个共享比特的异或（XOR）结果；如果他正是付账者，则宣布相反的结果
3. 判定规则：将所有公开宣布的比特进行异或——如果结果为0，说明是NSA付的账；如果结果为1，说明三位密码学家中的某一位付了账

这个协议的精妙之处在于：如果结果是1，旁观者（或NSA）只知道三位中有一人付了账，却无法确定具体是谁；而三位密码学家彼此之间也无法精确定位付款者。

该协议可以推广到任意数量的参与者围坐成一圈的情形，其思想被应用于匿名消息广播等场景，实现了无条件的发送方和接收方不可追踪性。

总结

协议	核心问题	意义
点积协议	安全计算向量点积	MPC基础组件，广泛应用于数据挖掘、统计分析
百万富翁协议	安全比较两数大小	MPC的起源，引出混淆电路等通用技术
密码学家晚餐问题	匿名性判定	匿名通信协议的基础，实现发送方不可追踪