保姆级教程：用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 # 参与者ID0或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_length32): 将秘密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-rP1获得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_length32) - 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_length32) - 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) # 分享值a10 share_secret(20, p0_b, p1_b) # 分享值b20 # 执行加法 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_length32): 初始化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_length32) - 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 (a5, b6, c30) 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 (a3, b2, c6) 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_length32): 批量乘法实现 :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代码逐步演示了核心操作希望为你后续探索更复杂的隐私保护计算协议打下坚实基础。