保姆级教程：用Python模拟实现算术秘密分享的加法和乘法（附完整代码）
从零实现算术秘密分享：Python实战加法和Beaver Triple乘法
在隐私计算领域，算术秘密分享(Arithmetic Secret Sharing)是安全多方计算(MPC)的基石技术。但很多初学者面对抽象的理论公式时，常常感到无从下手。本文将用Python代码完整演示算术秘密分享的核心操作——加法和基于Beaver Triple的乘法实现过程，让你通过运行代码直观理解其工作原理。
1. 环境准备与基础类设计
首先我们需要搭建一个模拟两方计算的Python环境。这个环境不需要真实网络通信，而是通过对象模拟两个参与方（P0和P1）的交互过程。
import random from typing import Tuple class Participant: def __init__(self, id: int): self.id = id # 参与者ID，0或1 self.share = None # 保存的秘密分享值 self.received = None # 接收到的数据 def send(self, value, to: 'Participant'): to.receive(value) def receive(self, value): self.received = value这个基础的Participant类定义了参与者的基本行为：每个参与者有一个ID标识，可以保存自己的分享值(share)，并能通过send/receive方法模拟网络通信。
2. 秘密分享的生成与重构
算术秘密分享的核心是将一个数值x拆分为两个随机数之和，分别由两个参与者持有。
2.1 分享算法实现
def share_secret(x: int, p0: Participant, p1: Participant, bit_length=32): """ 将秘密x分享给p0和p1 :param x: 要分享的秘密值 :param p0: 参与者0 :param p1: 参与者1 :param bit_length: 数值的位宽 """ modulus = 2 ** bit_length r = random.randint(0, modulus - 1) # 生成随机数 # P0获得x-r，P1获得r p0.share = (x - r) % modulus p1.share = r # 模拟通信过程：P0将r发送给P1（实际中P1已经持有r） p0.send(r, p1)2.2 重构算法实现
def reconstruct(p0: Participant, p1: Participant, bit_length=32) -> int: """ 从两个参与者的分享中重构原始秘密 :param p0: 参与者0 :param p1: 参与者1 :param bit_length: 数值的位宽 :return: 重构的秘密值 """ modulus = 2 ** bit_length # 模拟通信：双方交换share p0.send(p0.share, p1) p1.send(p1.share, p0) # 计算总和 return (p0.received + p1.received) % modulus让我们测试一下这个基本的分享和重构过程：
# 测试代码 p0 = Participant(0) p1 = Participant(1) original_value = 12345 share_secret(original_value, p0, p1) reconstructed = reconstruct(p0, p1) print(f"原始值: {original_value}, 重构值: {reconstructed}") # 输出: 原始值: 12345, 重构值: 123453. 本地加法实现
算术秘密分享的一个美妙特性是加法可以在本地完成，无需双方通信。
def secret_add(a_p0: Participant, a_p1: Participant, b_p0: Participant, b_p1: Participant, bit_length=32) -> Tuple[Participant, Participant]: """ 秘密分享值的加法 返回新的分享对(P0的新share, P1的新share) """ # 创建新的参与者来保存结果 res_p0 = Participant(0) res_p1 = Participant(1) modulus = 2 ** bit_length # 各方本地计算share相加 res_p0.share = (a_p0.share + b_p0.share) % modulus res_p1.share = (a_p1.share + b_p1.share) % modulus return res_p0, res_p1测试加法操作：
# 创建参与者和分享值 p0_a, p1_a = Participant(0), Participant(1) p0_b, p1_b = Participant(0), Participant(1) share_secret(10, p0_a, p1_a) # 分享值a=10 share_secret(20, p0_b, p1_b) # 分享值b=20 # 执行加法 res_p0, res_p1 = secret_add(p0_a, p1_a, p0_b, p1_b) # 重构结果 result = reconstruct(res_p0, res_p1) print(f"加法结果: {result}") # 应该输出304. Beaver Triple乘法实现
相比于加法，乘法的实现要复杂得多，需要依赖预处理阶段生成的Beaver Triple（乘法三元组）。
4.1 Beaver Triple生成
首先我们需要实现Beaver Triple的生成。为简化演示，我们假设三元组已经预先生成好。
class BeaverTriple: def __init__(self, a: int, b: int, c: int, p0: Participant, p1: Participant, bit_length=32): """ 初始化Beaver Triple并分享给两方 :param a, b, c: 满足a*b = c的三元组 :param p0: 参与者0 :param p1: 参与者1 """ self.bit_length = bit_length self.modulus = 2 ** bit_length # 分享a, b, c share_secret(a, p0, p1, bit_length) self.a_p0, self.a_p1 = p0, p1 share_secret(b, p0, p1, bit_length) self.b_p0, self.b_p1 = p0, p1 share_secret(c, p0, p1, bit_length) self.c_p0, self.c_p1 = p0, p14.2 基于Beaver Triple的乘法
现在我们可以实现基于Beaver Triple的乘法协议：
def secret_multiply(x_p0: Participant, x_p1: Participant, y_p0: Participant, y_p1: Participant, triple: BeaverTriple, bit_length=32) -> Tuple[Participant, Participant]: """ 基于Beaver Triple的秘密分享乘法 """ modulus = 2 ** bit_length # 步骤1：各方本地计算e和f的share e_p0 = Participant(0) e_p1 = Participant(1) e_p0.share = (x_p0.share - triple.a_p0.share) % modulus e_p1.share = (x_p1.share - triple.a_p1.share) % modulus f_p0 = Participant(0) f_p1 = Participant(1) f_p0.share = (y_p0.share - triple.b_p0.share) % modulus f_p1.share = (y_p1.share - triple.b_p1.share) % modulus # 步骤2：重构e和f（实际应用中需要通信） e = reconstruct(e_p0, e_p1, bit_length) f = reconstruct(f_p0, f_p1, bit_length) # 步骤3：各方计算结果的share res_p0 = Participant(0) res_p1 = Participant(1) # P0的计算：f*a_i + e*b_i + c_i res_p0.share = (f * triple.a_p0.share + e * triple.b_p0.share + triple.c_p0.share) % modulus # P1的计算：e*f + f*a_i + e*b_i + c_i res_p1.share = (e * f + f * triple.a_p1.share + e * triple.b_p1.share + triple.c_p1.share) % modulus return res_p0, res_p14.3 完整乘法演示
让我们用一个完整例子演示乘法过程：
# 创建参与者和分享值 p0_x, p1_x = Participant(0), Participant(1) p0_y, p1_y = Participant(0), Participant(1) x = 15 # 第一个秘密值 y = 20 # 第二个秘密值 share_secret(x, p0_x, p1_x) share_secret(y, p0_y, p1_y) # 创建Beaver Triple (a=5, b=6, c=30) p0_triple = Participant(0) p1_triple = Participant(1) triple = BeaverTriple(5, 6, 30, p0_triple, p1_triple) # 执行乘法 res_p0, res_p1 = secret_multiply(p0_x, p1_x, p0_y, p1_y, triple) # 重构结果 result = reconstruct(res_p0, res_p1) print(f"乘法结果: {result} (期望值: {x * y})")5. 实战案例：联合计算多项式
现在让我们用一个更实际的例子来演示这些操作的综合应用：计算两个数的多项式组合。
假设我们需要安全地计算(x + y) * (x - y)，其中x和y分别由两个参与方秘密持有。
# 创建参与者和分享值 p0_x, p1_x = Participant(0), Participant(1) p0_y, p1_y = Participant(0), Participant(1) x = 10 # 第一个秘密值 y = 4 # 第二个秘密值 # 分享x和y share_secret(x, p0_x, p1_x) share_secret(y, p0_y, p1_y) # 创建Beaver Triple (a=3, b=2, c=6) p0_triple = Participant(0) p1_triple = Participant(1) triple = BeaverTriple(3, 2, 6, p0_triple, p1_triple) # 计算x + y (本地加法) sum_p0, sum_p1 = secret_add(p0_x, p1_x, p0_y, p1_y) # 计算x - y (需要先计算-y的分享) # 分享-1 p0_neg1, p1_neg1 = Participant(0), Participant(1) share_secret(-1, p0_neg1, p1_neg1) # 计算-y = -1 * y (需要另一个乘法三元组) p0_triple2 = Participant(0) p1_triple2 = Participant(1) triple2 = BeaverTriple(2, 3, 6, p0_triple2, p1_triple2) neg_y_p0, neg_y_p1 = secret_multiply(p0_neg1, p1_neg1, p0_y, p1_y, triple2) # 计算x - y = x + (-y) diff_p0, diff_p1 = secret_add(p0_x, p1_x, neg_y_p0, neg_y_p1) # 计算最终结果 (sum * diff) final_p0, final_p1 = secret_multiply(sum_p0, sum_p1, diff_p0, diff_p1, triple) # 重构结果 result = reconstruct(final_p0, final_p1) expected = (x + y) * (x - y) print(f"计算结果: {result} (期望值: {expected})")6. 性能优化与实用技巧
在实际应用中，我们需要考虑几个优化点：
批量处理：在实际MPC协议中，Beaver Triple通常是批量预生成的，这样可以分摊通信成本。
模数选择：根据应用场景选择合适的模数大小，平衡安全性和计算效率。
通信优化：重构步骤(e和f的公开)可以通过其他技术优化，减少通信轮数。
错误处理：在实际实现中需要添加各种错误检查和异常处理。
def batch_multiply(inputs: list, triples: list, bit_length=32): """ 批量乘法实现 :param inputs: 待乘的分享对列表 [(x0,y0), (x1,y1), ...] :param triples: Beaver Triple列表 [triple0, triple1, ...] :return: 乘积结果的分享列表 """ results = [] for (x_p0, x_p1, y_p0, y_p1), triple in zip(inputs, triples): res_p0, res_p1 = secret_multiply(x_p0, x_p1, y_p0, y_p1, triple, bit_length) results.append((res_p0, res_p1)) return results算术秘密分享是隐私计算的基础构建块，理解其原理和实现对于深入MPC领域至关重要。本文通过Python代码逐步演示了核心操作，希望为你后续探索更复杂的隐私保护计算协议打下坚实基础。