4. 基于秘密共享的隐私均值计算

问题定义与协议选择

三个参与方 P₁、P₂、P₃ 各自持有私密数值 x₁、x₂、x₃，希望共同计算均值 μ = (x₁+x₂+x₃)/3，但任何一方都不能向其他方泄露自己的原始数值。Shamir 秘密共享的加法同态特性正好满足这一需求：各方将秘密拆分为份额分发，各方对收到的份额求和，再对份额和进行重构，即可得到秘密和，最后除以参与方数量得到均值。

选择 (t, n) = (2, 3) 门限方案：任意 2 个份额即可重构秘密，单个份额不泄露任何信息。所有运算在有限域 GF(p) 上进行，取素数 p = 2³¹ − 1 = 2147483647，确保中间结果不溢出且除法可逆。

核心实现：份额生成与重构

以下 Python 代码完整实现了上述协议。所有运算在 GF(p) 上进行，使用 pow(a, -1, p) 求模逆元。随机系数 a₁、b₁、c₁ 由各方独立生成，不对外暴露。

import random

P = 2147483647  # 2^31 - 1，素数

def generate_shares(secret, n=3, t=2):
    """生成 n 个份额，门限为 t"""
    coeffs = [secret] + [random.randint(1, P - 1) for _ in range(t - 1)]
    shares = []
    for i in range(1, n + 1):
        val = 0
        for c in reversed(coeffs):
            val = (val * i + c) % P
        shares.append((i, val))
    return shares

def reconstruct_secret(shares):
    """拉格朗日插值重构秘密（在 x=0 处求值）"""
    total = 0
    for i, (xi, yi) in enumerate(shares):
        num, den = 1, 1
        for j, (xj, _) in enumerate(shares):
            if i != j:
                num = (num * (0 - xj)) % P
                den = (den * (xi - xj)) % P
        lagrange = (num * pow(den, -1, P)) % P
        total = (total + yi * lagrange) % P
    return total

# 各方私密数据
x1, x2, x3 = 100, 200, 300

# ① 各方生成份额
shares1 = generate_shares(x1)
shares2 = generate_shares(x2)
shares3 = generate_shares(x3)

# ② 分发：P_i 保留 shares_i[0]，将 shares_i[1] 给 P_{i+1}，shares_i[2] 给 P_{i+2}
# P1 收到: shares1[0], shares2[0], shares3[0]
# P2 收到: shares1[1], shares2[1], shares3[1]
# P3 收到: shares1[2], shares2[2], shares3[2]

# ③ 各方本地求和
S1 = (shares1[0][1] + shares2[0][1] + shares3[0][1]) % P
S2 = (shares1[1][1] + shares2[1][1] + shares3[1][1]) % P
S3 = (shares1[2][1] + shares2[2][1] + shares3[2][1]) % P

# ④ 任选 2 个份额和重构秘密和
secret_sum = reconstruct_secret([(1, S1), (2, S2)])
mean = (secret_sum * pow(3, -1, P)) % P

print(f"重构的秘密和: {secret_sum}")   # 应为 600
print(f"隐私均值: {mean}")             # 应为 200

验证与结果判读

运行上述代码，预期输出 重构的秘密和: 600 和 隐私均值: 200，与直接计算 (100+200+300)/3 = 200 一致。验证要点如下：

• 正确性：重构和等于三方原始数据之和，均值等于算术平均值。
• 隐私性：任意单方持有的份额和 Sᵢ 是随机值，无法反推任何原始数据。例如 P₁ 只知道 S₁ = s₁₁+s₂₁+s₃₁，其中每个 sᵢ₁ 都是随机多项式在 z=1 处的取值，不泄露 xᵢ。
• 门限性：任意 2 个份额和即可重构，单个份额和无法重构。可尝试仅用 S₁ 重构，结果将是随机值而非 600。
• 有限域一致性：所有中间结果均 mod p，最终均值也需 mod p 后映射回整数域。当真实均值小于 p 时，直接取模结果即为正确值。