1. 基于Paillier同态加密的隐私求和协议实现

Paillier 同态加密的数学基础

Paillier 加密是一种加法同态公钥密码体制，其安全性基于判定性合数剩余假设（DCR）。协议涉及三个核心操作：密钥生成、加密、同态加法。

• 密钥生成：选取两个大素数 p、q，令 n = p·q，λ = lcm(p−1, q−1)。公钥为 (n, g)，其中 g = n+1；私钥为 λ。
• 加密：对明文 m ∈ ℤ_n，选随机数 r ∈ ℤ_n^*，密文 c = g^m · rⁿ mod n²。
• 同态加法：Dec(c₁ · c₂ mod n²) = m₁ + m₂ mod n。这是隐私求和协议的核心性质。

协议实现与验证

下面给出一个可直接运行的 Python 实现。为便于教学演示，使用小素数生成密钥；实际部署应使用 2048 位以上安全参数。

import random
from math import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

def gen_keypair(bits=16):
    """生成 Paillier 密钥对（教学用小素数）"""
    p = gen_prime(bits)
    q = gen_prime(bits)
    while p == q:
        q = gen_prime(bits)
    n = p * q
    lam = lcm(p - 1, q - 1)
    g = n + 1
    mu = pow(lam, -1, n)  # λ⁻¹ mod n
    return (n, g), (lam, mu)

def gen_prime(bits):
    """生成指定位数的素数（教学用）"""
    while True:
        num = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime(num):
            return num

def is_prime(n, k=20):
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29,31,37]:
        if n % p == 0: return n == p
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2; r += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, 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

def encrypt(pub, m):
    """加密：c = g^m · r^n mod n²"""
    n, g = pub
    n2 = n * n
    r = random.randrange(1, n)
    while gcd(r, n) != 1:
        r = random.randrange(1, n)
    return (pow(g, m, n2) * pow(r, n, n2)) % n2

def decrypt(priv, pub, c):
    """解密：m = L(c^λ mod n²) · μ mod n"""
    n, g = pub
    lam, mu = priv
    n2 = n * n
    u = pow(c, lam, n2)
    l = (u - 1) // n
    return (l * mu) % n

def homomorphic_add(pub, c1, c2):
    """同态加法：密文相乘"""
    n, _ = pub
    return (c1 * c2) % (n * n)

# ===== 协议执行 =====
pub, priv = gen_keypair(bits=16)
x, y = 42, 58

c_x = encrypt(pub, x)
c_y = encrypt(pub, y)
c_sum = homomorphic_add(pub, c_x, c_y)
result = decrypt(priv, pub, c_sum)

print(f"参与方A明文: {x}")
print(f"参与方B明文: {y}")
print(f"密文 c_A: {c_x}")
print(f"密文 c_B: {c_y}")
print(f"密文和 c_sum: {c_sum}")
print(f"解密结果: {result}")
print(f"验证: {x} + {y} = {result} -> {'通过' if result == x + y else '失败'}")

计算开销分析

Paillier 的主要开销集中在模幂运算。下表以 1024 位模数为例，给出各阶段的理论复杂度与实测参考量级。

正确性验证与边界条件

验证协议正确性时，需覆盖以下场景：

1. 基本求和：x=42, y=58，解密结果应为 100。
2. 零值参与：x=0, y=77，解密结果应为 77。Paillier 支持明文 0 的加密。
3. 大数求和：x=9999, y=8888，解密结果应为 18887。需确保 x+y < n，否则会发生模 n 回绕。
4. 多次累加：对同一密文自乘 k 次，解密结果应为 k·m mod n。