Paillier 加法同态加密算法详细介绍

1. 概述

Paillier 同态加密算法是一种非对称加密算法，由 Pascal Paillier 在 1999 年提出。它的独特之处在于其同态特性，即能在加密数据上直接进行运算而无需解密。这使得它在数据隐私保护、安全多方计算等领域有着广泛的应用。

2. 原理

Paillier 加密算法主要包括三个部分：密钥生成、加密和解密。

2.1 密钥生成

1. 选择两个大素数$p$ 和$q$: 这两个数越大，算法越安全。
2. 计算$n=p\times q$: 这是公钥的一部分。
3. 计算 λ: λ 是 Carmichael’s totient 函数的输出，即 最小公倍数$\text{lcm}(p-1,q-1)$。
4. 选择一个整数 g: g 的选取应满足$g\in {\mathbb{Z}}_{n^2}^{\ast }$。

公钥为$(n,g)$，私钥为$\lambda$。

2.2 加密

对于一个明文消息$m$，加密过程如下：

1. 选择一个随机数$r$:$r$ 是一个随机数，满足$r\in {\mathbb{Z}}_n^{\ast }$。
2. 计算密文$c$: 使用公钥$(n,g)$ 计算$c=g^m\times r^n\mathrm{mod}{n}^2$。

2.3 解密

对于一个密文$c$，解密过程如下：

1. 计算$u=c^{\lambda }\mathrm{mod}{n}^2$。
2. 计算$L(u)$: 其中$L$ 是一个特定的函数，定义为$L(x)=\frac{x-1}{n}$。
3. 计算原始消息$m$: 使用私钥$\lambda$ 和预先计算的$L(g^{\lambda }\mathrm{mod}{n}^2)$ 的模逆元素，计算$m=L(u)\times \text{modinv}(L(g^{\lambda }\mathrm{mod}{n}^2),n)\mathrm{mod}n$。

3. Paillier 加密算法的解密过程

假设我们有密文$c$，公钥$(n,g)$ 和私钥$\lambda$。明文消息为$m$，随机数$r$ 用于加密过程。

3.1 加密过程回顾

加密过程定义为：

$c=g^m\cdot r^n\mathrm{mod}{n}^2$

3.2 解密步骤

1. 计算$u$

   首先计算$u=c^{\lambda }\mathrm{mod}{n}^2$。由于$c=g^m{r}^n$，我们有：

   $u=(g^m{r}^n{)}^{\lambda }\mathrm{mod}{n}^2$

2. 利用 Carmichael 函数的性质

   由于$\lambda =\text{lcm}(p-1,q-1)$，根据 Carmichael 函数的性质，对于任意$a\in {\mathbb{Z}}_n^{\ast }$：

   $a^{\lambda }\equiv 1\mathrm{mod}n$

   这意味着对于$r^n$，有：

   $(r^n{)}^{\lambda }\equiv 1\mathrm{mod}{n}^2$（把$r^{\lambda }=kn+1$带入展开）

3. 分析$u$ 的表达式

   通过将$g^m$ 和$r^n$ 分开，我们可以重写$u$ 如下：

   $u=(g^m{)}^{\lambda }\cdot (r^n{)}^{\lambda }\mathrm{mod}{n}^2$

   我们可以将$u$ 简化为：

   $u=(g^m{)}^{\lambda }\cdot 1\mathrm{mod}{n}^2$

   $u=(kn+1{)}^m\mathrm{mod}{n}^2$

4. 应用$L$ 函数

   接下来，我们应用$L$ 函数到$u$ 上。定义$L(x)=\frac{x-1}{n}$，我们得到：

   $L(u)=L((kn+1{)}^m\mathrm{mod}{n}^2)=\frac{[(kn+1{)}^m\mathrm{mod}{n}^2]-1}{n}=\frac{(1+m\cdot kn\mathrm{mod}{n}^2)-1}{n}=km\mathrm{mod}{n}^2$

5. 计算模逆元素$\mu$

   在 Paillier 加密算法中，模逆元素$\mu$是解密过程的关键部分。它是基于$g$的一个特定幂的$L$函数值的模逆元素。

   • 计算$L(g^{\lambda }\mathrm{mod}{n}^2)$

     首先，我们计算$g^{\lambda }$在$\mathrm{mod}{n}^2$下的结果，然后应用$L$函数。根据$L$函数的定义（$L(x)=\frac{x-1}{n}$），我们有：

     $L(g^{\lambda }\mathrm{mod}{n}^2)=\frac{(g^{\lambda }\mathrm{mod}{n}^2)-1}{n}=\frac{(1+kn\mathrm{mod}{n}^2)-1}{n}$

   • 计算$\mu$

     接下来，我们计算$L(g^{\lambda }\mathrm{mod}{n}^2)$的模逆元素$\mu$：

     $\mu =\text{modinv}(L(g^{\lambda }\mathrm{mod}{n}^2),n)$

     $\mu =[\frac{(1+kn\mathrm{mod}{n}^2)-1}{n}{]}^{-1}=(k\mathrm{mod}{n}^2{)}^{-1}\mathrm{mod}n$

   现在，计算原始消息$m$

   $m=L(u)\times \mu \mathrm{mod}n$

   因此，通过计算$L(u)\times \mu \mathrm{mod}n$，我们可以从加密后的$c$中恢复出原始的明文消息$m$。

4. 同态特性

Paillier 算法的主要特性是它的同态性质。具体来说，它支持同态加法和数乘操作：

• 同态加法: 对于两个密文$c_1$ 和$c_2$，其解密结果等同于它们对应明文的和的加密，即$D(E(m_1)\times E(m_2)\mathrm{mod}{n}^2)=m_1+m_2$。
• 同态加法（加密消息与明文整数）: 加密一个消息$m$，然后将这个加密的结果与$g^k\mathrm{mod}{n}^2$（其中$g$ 是公钥的一部分）相乘。解密这个乘积将得到$m$ 与$k$ 的和,即$\text{D}(E(m)\times g^k\mathrm{mod}{n}^2)=m+k\mathrm{mod}n$
• 同态数乘: 对于一个密文$c$ 和一个明文数$k$，其解密结果等同于密文对应明文的$k$ 倍的加密，即$D(E(m{)}^k\mathrm{mod}{n}^2)=k\times m$。

5.批处理

我们可以将多个明文消息 $m_i$ 批处理到同一个Paillier密文中，其中每个消息用 $t$ 位表示。设 $b$ 为批处理的大小，即我们可以在同一个Paillier密文中加密的正消息的最大数量为 $c_p=g^{m_1+m_2+...+m_b}\cdot r^{N_E}\mathrm{mod}{N}_E^2$，或者用不同的写法表示为 $Enc(m_1|m_2|...|m_b)$。为了正确解密 $c_p$，需要满足 $|m_1+m_2+...+m_b|\le N_E$ 和 $b\le \log (N_E)/t$（即对于2048位的模数和消息位数 $t=64$ 位，最多可以将32条消息打包在一起）。

然而，如果我们想对这些打包的密文执行加法，必须考虑到这一点，以设置初始批次的维度，以避免溢出。设 $n{b}_{\text{add}}$ 为我们想要在这些打包的消息上执行的加法的数量。必须添加到每个插槽的填充（即零位数）等于 $n{b}_{\text{add}}$。因此，必须加密 $Enc(m_1\underset{{\text{nb}}_{\text{add}}}{\underbrace{\mathrm{0...0}}}|m_2\underset{{\text{nb}}_{\text{add}}}{\underbrace{\mathrm{0...0}}}|...|m_b\underset{{\text{nb}}_{\text{add}}}{\underbrace{\mathrm{0...0}}})$。然后，批处理的大小最多应为 $:b=\lfloor \frac{lo{g}_2(N_E)}{t+n{b}_{add}}\rfloor$。

让我们举一个简短的例子。假设我们要加密的每条消息是介于0和U之间的实际正数，其中U = 100，且 $m_i$ 在小数点后有4位有效数字。因此，为了表示这些消息，必须至少有 $\lceil{log_{2}}(U*10^{4})\rceil $，即20位。对于这种类型的消息，对密文执行两次加法（每次加法需要填充1位），对于2048位的模数，可以将93条消息打包在单个密文中。对于相同格式的密文执行100次加法，每个密文最多可以有17个插槽。
$$\lceil {\log }_2(U\times 10^4)\rceil =\lceil {\log }_2(100\times 10^4)\rceil =\lceil {\log }_2(10^6)\rceil =\lceil 20\rceil =20$$

5. 安全性保障

Paillier 算法的安全性主要依赖于大数分解的困难性。当选择的素数$p$ 和$q$ 足够大时，要破解该算法需要解决一个非常困难的数学问题——大数分解问题。因此，在实际应用中，应确保$p$ 和$q$ 的选取足够安全。

6. 结论

Paillier 加密算法由于其同态特性，在多方安全计算、数据隐私保护、云计算安全等领域有着重要应用。例如，在电子投票系统中，可以保证投票的隐私性和可验证性；在数据分析中，可以对加密数据进行处理而无需暴露原始数据。

Paillier 同态加密算法提供了一种在加密状态下进行计算的能力，对于保护数据隐私和安全性有着重要意义。尽管其计算过程相对复杂，但它的安全性和独特的同态特性使其在现代加密应用中占有一席之地。

7.代码附录

import random
from sympy import isprime, mod_inverse
import gmpy2
def generate_prime_candidate(length):
    """ 随机生成一个指定长度的奇数 """
    p = random.getrandbits(length)  # 获取一个指定长度的随机位
    p |= (1 << length - 1) | 1  # 确保最高位和最低位为1，从而生成一个奇数
    return p


def generate_large_prime(length):
    """ 生成一个指定长度的大素数 """
    p = 4  # 初始化一个非素数
    while not isprime(p):  # 循环直到找到一个素数
        p = generate_prime_candidate(length)  # 生成一个候选素数
    return p


def lcm(x, y):
    """ 计算两个数的最小公倍数 """
    greater = max(x, y)  # 找到x和y中的较大值
    while True:  # 循环直到找到最小公倍数
        if greater % x == 0 and greater % y == 0:  # 检查是否是公倍数
            return greater
        greater += 1


def generate_keypair(bit_length):
    """ 生成Paillier公钥和私钥 """
    p = generate_large_prime(bit_length)
    q = generate_large_prime(bit_length)
    n = p * q  # 计算n，Paillier算法的核心参数
    g = n + 1  # 简单选择g为n + 1
    lambda_val = gmpy2.lcm(p - 1, q - 1)  # 计算lambda，使用最小公倍数
    return (n, g), lambda_val

def encrypt(pk, m):
    """ 使用公钥pk加密消息m, m < n """
    n, g = pk
    r = random.randint(1, n)  # 随机选择一个数r
    c = pow(g, m, n ** 2) * pow(r, n, n ** 2) % n ** 2

    return c

def decrypt(pk, sk, c):
    """ 使用私钥sk解密密文c """
    n, g = pk
    lambda_val = sk

    # 计算 u = c^lambda mod n^2
    u = pow(c, lambda_val, n ** 2)

    # 计算 L(u)
    L_u = (u - 1) // n

    # 预先计算 L(g^lambda mod n^2) 的模逆元素
    L_g_lambda_inv = mod_inverse((pow(g, lambda_val, n ** 2) - 1) // n, n)

    # 还原原始消息
    return (L_u * L_g_lambda_inv) % n


def paillier_homomorphic_addition(pk, c1, c2):
    """
    实现Paillier同态加法
    :param c1: 加密的数字m1的密文
    :param c2: 加密的数字m2的密文
    :param n: 公钥的一部分
    :return: 同态加法的结果，即加密的m1+m2
    """
    n, g = pk
    return c1 * c2 % (n ** 2)


def batch_encrypt(public_key, messages, t, nb_add):
    """ 批处理加密多个消息 """
    e, n = public_key
    # 将消息拼接成一个大整数
    big_int = 0
    for message in messages:
        big_int = (big_int << (t + nb_add)) + message
    # 加密这个大整数
    ciphertext = encrypt(public_key, big_int)
    return ciphertext


def batch_decrypt(public_key, private_key, ciphertext, message_count, t, nb_add):
    """ 批处理解密 """
    # 解密得到大整数
    decrypted_int = decrypt(public_key, private_key, ciphertext)
    messages = []
    # 分离出各个消息
    mask = (1 << t + nb_add) - 1
    for _ in range(message_count):
        messages.insert(0, decrypted_int & mask)
        decrypted_int >>= (t + nb_add)
    return messages

# 设置参数
t = 20  # 消息位数
nb_add = 1  # 需要添加的填充位数
message_count = 3  # 消息数量

# 生成密钥
public_key, private_key = generate_keypair(1024)  # 此处为16位，仅作演示；实际应用中应使用1024位或2048位

# 准备批处理消息
messages1 = [512, 200, 108]  # 消息列表
messages2 = [223, 212, 122]  # 消息列表
# 批处理加密消息
ciphertext1 = batch_encrypt(public_key, messages1, t, nb_add)
print('批处理密文1:', ciphertext1)
ciphertext2 = batch_encrypt(public_key, messages2, t, nb_add)
print('批处理密文2:', ciphertext2)
ciphertext3 = paillier_homomorphic_addition(public_key, ciphertext1, ciphertext2)
decrypted_messages = batch_decrypt(public_key,private_key, ciphertext3, message_count, t, nb_add)
print('批处理解密消息:', decrypted_messages)