037_密码学实战：安全多方计算MPC技术深度解析——从秘密共享到隐私保护计算的完整指南

输入 → 加密转换 → 多方协作计算 → 安全输出 → 结果验证

import random
from functools import reduce

def generate_shamir_shares(secret, threshold, num_shares, prime=None):
    """
    生成Shamir阈值秘密共享的份额
    
    参数:
    secret: 要共享的秘密（整数）
    threshold: 恢复秘密所需的最小份额数
    num_shares: 要生成的总份额数
    prime: 使用的素数，默认为None时自动选择
    
    返回:
    list: 份额列表，每个份额为(i, s_i)的元组
    """
    # 如果没有提供素数，选择一个足够大的素数
    if prime is None:
        # 简单选择一个大素数，实际应用中应选择安全的素数
        prime = 2**256 - 2**32 - 977  # 一个大素数
    
    # 确保秘密小于素数
    if secret >= prime:
        raise ValueError("秘密必须小于选择的素数")
    
    # 确保阈值小于或等于份额数
    if threshold > num_shares:
        raise ValueError("阈值不能大于份额数")
    
    # 随机选择多项式系数
    coefficients = [secret] + [random.randint(0, prime-1) for _ in range(threshold-1)]
    
    # 生成份额
    shares = []
    for i in range(1, num_shares+1):
        # 计算f(i) mod prime
        share_value = 0
        for j, coeff in enumerate(coefficients):
            share_value = (share_value + coeff * (i**j)) % prime
        shares.append((i, share_value))
    
    return shares

def reconstruct_secret(shares, prime=None):
    """
    从份额中恢复秘密
    
    参数:
    shares: 份额列表，每个份额为(i, s_i)的元组
    prime: 使用的素数，默认为None时自动选择
    
    返回:
    int: 恢复的秘密
    """
    # 如果没有提供素数，选择一个足够大的素数
    if prime is None:
        prime = 2**256 - 2**32 - 977  # 一个大素数
    
    def lagrange_interpolation(x, x_values, y_values, prime):
        """使用拉格朗日插值法计算多项式在x处的值"""
        def product(values):
            """计算列表中所有值的乘积"""
            return reduce(lambda a, b: a * b % prime, values, 1)
        
        result = 0
        n = len(x_values)
        
        for i in range(n):
            xi, yi = x_values[i], y_values[i]
            # 计算拉格朗日基多项式
            numerator = product([(x - xj) for j, xj in enumerate(x_values) if j != i])
            denominator = product([(xi - xj) for j, xj in enumerate(x_values) if j != i])
            
            # 计算分母的模逆元
            denominator_inverse = pow(denominator, -1, prime) if denominator != 0 else 0
            
            # 累加当前项
            term = yi * numerator * denominator_inverse % prime
            result = (result + term) % prime
        
        return result
    
    # 提取x和y值
    x_values = [share[0] for share in shares]
    y_values = [share[1] for share in shares]
    
    # 计算f(0)，即原始秘密
    return lagrange_interpolation(0, x_values, y_values, prime)

# 示例使用
def main():
    # 设置参数
    secret = 42  # 要共享的秘密
    threshold = 3  # 恢复秘密需要的最小份额数
    num_shares = 5  # 生成的总份额数
    
    # 生成份额
    shares = generate_shamir_shares(secret, threshold, num_shares)
    print(f"生成的份额: {shares}")
    
    # 从阈值数量的份额中恢复秘密
    recovered_secret = reconstruct_secret(shares[:threshold])
    print(f"恢复的秘密: {recovered_secret}")
    print(f"恢复是否成功: {recovered_secret == secret}")
    
    # 尝试用少于阈值的份额恢复（理论上应该失败，但在这个简单实现中可能得到错误结果）
    partial_secret = reconstruct_secret(shares[:threshold-1])
    print(f"使用{threshold-1}个份额恢复的'秘密': {partial_secret}")
    print(f"恢复是否成功: {partial_secret == secret}")

if __name__ == "__main__":
    main()

import random

def generate_additive_shares(secret, num_shares, prime=None):
    """
    生成加法秘密共享的份额
    
    参数:
    secret: 要共享的秘密（整数）
    num_shares: 要生成的总份额数
    prime: 使用的素数，默认为None时自动选择
    
    返回:
    list: 份额列表
    """
    # 如果没有提供素数，选择一个足够大的素数
    if prime is None:
        # 简单选择一个大素数，实际应用中应选择安全的素数
        prime = 2**256 - 2**32 - 977  # 一个大素数
    
    # 确保秘密小于素数
    if secret >= prime:
        raise ValueError("秘密必须小于选择的素数")
    
    # 随机选择前n-1个份额
    shares = [random.randint(0, prime-1) for _ in range(num_shares-1)]
    
    # 计算最后一个份额，使得所有份额的和等于秘密
    last_share = (secret - sum(shares)) % prime
    shares.append(last_share)
    
    return shares

def reconstruct_secret(shares, prime=None):
    """
    从加法秘密共享的份额中恢复秘密
    
    参数:
    shares: 份额列表
    prime: 使用的素数，默认为None时自动选择
    
    返回:
    int: 恢复的秘密
    """
    # 如果没有提供素数，选择一个足够大的素数
    if prime is None:
        prime = 2**256 - 2**32 - 977  # 一个大素数
    
    # 对于标准加法共享，需要所有份额才能恢复
    # 但如果只使用部分份额，可以获得部分信息（这是加法共享的局限性）
    return sum(shares) % prime

# 示例使用
def main():
    # 设置参数
    secret = 42  # 要共享的秘密
    num_shares = 3  # 生成的总份额数
    
    # 生成份额
    shares = generate_additive_shares(secret, num_shares)
    print(f"生成的份额: {shares}")
    print(f"份额和: {sum(shares)}")
    
    # 从所有份额中恢复秘密
    recovered_secret = reconstruct_secret(shares)
    print(f"恢复的秘密: {recovered_secret}")
    print(f"恢复是否成功: {recovered_secret == secret}")
    
    # 尝试用部分份额（这会得到部分信息，不同于Shamir方案）
    partial_sum = reconstruct_secret(shares[:2])
    print(f"使用2个份额的部分和: {partial_sum}")
    print(f"离原始秘密还差: {(secret - partial_sum) % num_shares}")

if __name__ == "__main__":
    main()

import random

def generate_additive_shares(secret, num_parties, prime):
    """
    生成加法秘密共享的份额
    """
    shares = [random.randint(0, prime-1) for _ in range(num_parties-1)]
    last_share = (secret - sum(shares)) % prime
    shares.append(last_share)
    return shares

def generate_beaver_triplet(prime):
    """
    生成Beaver乘法三元组(a,b,c)，其中c = a*b mod prime
    在实际MPC中，这通常由多方共同生成或由可信第三方提供
    """
    a = random.randint(0, prime-1)
    b = random.randint(0, prime-1)
    c = (a * b) % prime
    return a, b, c

def secure_multiplication(x_shares, y_shares, num_parties, prime):
    """
    基于Beaver三元组的安全乘法协议
    
    参数:
    x_shares: 第一个秘密的加法份额
    y_shares: 第二个秘密的加法份额
    num_parties: 参与方数量
    prime: 模数
    
    返回:
    list: 乘积的加法份额
    """
    # 1. 生成乘法三元组
    a, b, c = generate_beaver_triplet(prime)
    
    # 2. 将三元组分成份额
    a_shares = generate_additive_shares(a, num_parties, prime)
    b_shares = generate_additive_shares(b, num_parties, prime)
    c_shares = generate_additive_shares(c, num_parties, prime)
    
    # 3. 每个参与方计算d_i = x_i - a_i 和 e_i = y_i - b_i
    d_shares = [(x_share - a_share) % prime for x_share, a_share in zip(x_shares, a_shares)]
    e_shares = [(y_share - b_share) % prime for y_share, b_share in zip(y_shares, b_shares)]
    
    # 4. 所有参与方公开d_i和e_i，然后每个参与方计算全局的d和e
    d = sum(d_shares) % prime
    e = sum(e_shares) % prime
    
    # 5. 计算d*e，然后分成加法份额
    de = (d * e) % prime
    de_shares = generate_additive_shares(de, num_parties, prime)
    
    # 6. 计算d*b和e*a的份额
    d_b_shares = [(d * b_share) % prime for b_share in b_shares]
    e_a_shares = [(e * a_share) % prime for a_share in a_shares]
    
    # 7. 最终乘积的份额为 z_i = c_i + d*b_i + e*a_i + (d*e)_i
    z_shares = []
    for i in range(num_parties):
        z_i = (c_shares[i] + d_b_shares[i] + e_a_shares[i] + de_shares[i]) % prime
        z_shares.append(z_i)
    
    return z_shares

# 示例使用
def main():
    # 设置参数
    prime = 2**256 - 2**32 - 977  # 一个大素数
    num_parties = 3  # 参与方数量
    x = 15  # 第一个秘密
    y = 28  # 第二个秘密
    expected_product = (x * y) % prime  # 预期的乘积
    
    # 生成份额
    x_shares = generate_additive_shares(x, num_parties, prime)
    y_shares = generate_additive_shares(y, num_parties, prime)
    
    print(f"秘密x = {x}，份额: {x_shares}")
    print(f"秘密y = {y}，份额: {y_shares}")
    print(f"预期乘积: {expected_product}")
    
    # 执行安全乘法
    product_shares = secure_multiplication(x_shares, y_shares, num_parties, prime)
    print(f"乘积份额: {product_shares}")
    
    # 恢复乘积
    recovered_product = sum(product_shares) % prime
    print(f"恢复的乘积: {recovered_product}")
    print(f"乘法是否成功: {recovered_product == expected_product}")

if __name__ == "__main__":
    main()