从零开始构建多方计算：每个人都能做到！
引言：想象一下，你和你的朋友都是百万富翁，你们想知道谁更富有，但又不愿透露自己的真实资产。如何才能做到既比较财富又保护隐私？这就是多方计算（MPC）的用武之地。MPC允许多个参与者在不暴露自身私有信息的情况下，共同计算函数。本文将带你从零开始构建一个简单的 MPC 实现，让你亲身体验这门技术的魅力。
从素数生成开始： 为了实现 MPC，我们需要非对称加密，而 RSA 是最简单的非对称加密算法之一。为了使用 RSA，我们需要生成素数。我们可以通过猜测和验证来生成素数，但首先需要一种快速判断一个数是否为素数的方法。Rabin-Miller 素性测试是一种基于初等数论的简单测试，易于实现：
python
defrabin_miller(n, k=40):
if n == 2: return True
if n % 2 == 0: return False
r, s = 0, n - 1
while s % 2 == 0:
r +=1
s //= 2
for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1: continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1: break
else:
return False
return True
这个算法是概率性的，参数 k 决定了测试的可靠性。因为我们选择的随机基数a 可能存在少量的误判率。值得注意的是，如果基数 a 可以提前预测，那么可以伪造通过测试但实际上是合数的伪素数。不过，我们这里不用担心，因为我们的素数候选是随机生成的。在实践中，对于 RSA 大小的数字，k=40 已经足够了。该算法在多对数时间内运行，因此我们可以快速生成素数。
RSA 加密： 拥有素数生成器后，我们可以构建 RSA 加密算法。RSA 的核心是使用两个素数 p 和 q 生成公钥和私钥。公钥用于加密信息，私钥用于解密。
python
def generate_keys(bits):
p = generate_prime(bits // 2)
q = generate_prime(bits // 2)
n = p * q
phi = (p - 1)* (q - 1)
e = 65537
d = pow(e, -1, phi)
return (n, e), (n, d)
其中，generate_prime 函数使用 Rabin-Miller 测试生成素数。公钥是(n, e)，私钥是 (n, d)。
秘密共享： 为了实现 MPC，我们需要一种方法来将秘密信息分成多个部分，每个部分由不同的参与者持有，只有所有部分组合在一起才能恢复原始秘密。一种常用的方法是 Shamir 秘密共享：
python
def share_secret(secret, threshold, num_shares):
# 生成随机系数
coefficients = [random.randint(0, 2**128) for _ in range(threshold - 1)]
# 生成共享份额
shares = []
for i in range(1, num_shares + 1):
share = secret
for j in range(threshold - 1):
share += coefficients[j] * i ** (j + 1)
shares.append((i, share))
return shares
这个函数将秘密secret 分成 num_shares 个份额，其中至少需要 threshold 个份额才能恢复原始秘密。
混淆电路： Yao 的混淆电路协议是 MPC 中最常用的协议之一。它将计算过程表示成一个逻辑电路，然后对电路进行混淆，使得参与者可以在不暴露自身输入的情况下进行计算。
python
def garble_circuit(circuit):
# 生成随机密钥
keys = {}
for gate in circuit:
for input in gate['inputs']:
if input not in keys:
keys[input] = random.randint(0, 2**128)
# 混淆电路
garbled_circuit = []
for gate in circuit:
# 混淆门
garbled_gate = []
for i in range(2):
for j in range(2):
# 计算输出密钥
output_key = keys[gate['output']] ^ (keys[gate['inputs'][0]] if i == 1 else 0) ^ (keys[gate['inputs'][1]] if j == 1 else 0)
# 生成混淆的输入和输出
garbled_gate.append((keys[gate['inputs'][0]] if i == 1 else 0, keys[gate['inputs'][1]] if j == 1 else 0, output_key))
garbled_circuit.append(garbled_gate)
return garbled_circuit, keys
这个函数将电路混淆，并将混淆后的电路和密钥返回。
结论： 本文从零开始构建了一个简单的 MPC 实现，展示了 MPC 的基本原理和实现方法。通过使用素数生成、RSA 加密、秘密共享和混淆电路等技术，我们可以实现安全的计算，保护参与者的隐私。MPC 具有广泛的应用场景，例如隐私保护数据分析、安全投票、电子拍卖等。随着技术的不断发展，MPC 将在未来发挥越来越重要的作用。
参考文献：
关于作者： Luna Tong 是一位密码学研究员，致力于研究 MPC 和隐私保护技术。
Views: 0