Paillier 加法同态

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

# 1. 概述

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

判定n阶剩余类难题（DCR）是一个在密码学和数论中重要的概念，它关注的是对于给定的模数 $n^{2}$ （其中 $n$ 是两个大素数 $p$ 和 $q$ 的乘积），和一个给定的整数 $z$ ，判断 $z$ 是否为模 $n^{2}$ 下的一个n阶剩余。这里的“n阶剩余”意味着存在另一个整数 $y$ ，使得 $y^{n} \equiv z \mod n^{2}$ 。

# 2. 原理

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

# 2.1 密钥生成

选择两个大素数 $p$ 和 $q$ : 这两个数越大，算法越安全。
计算 $n = p \times q$ : 这是公钥的一部分。
计算 λ: λ 是 Carmichael's totient 函数的输出，即最小公倍数 $lcm (p - 1, q - 1)$ 。
选择一个整数 g: g 的选取应满足 $g \in Z_{n^{2}}^{*}$ ，且 $gcd (L (g^{λ} \mod n^{2}), n) = 1$

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

# 2.2 加密

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

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

# 2.3 解密

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

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

# 3. Paillier 正确性验证

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

# 3.1 加密过程回顾

加密过程定义为：

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

# 3.2 解密过程

计算 $u$

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

$u = (g^{m} r^{n})^{λ} \mod n^{2}$
利用 Carmichael 函数的性质

由于 $λ = lcm (p - 1, q - 1)$ ，根据 Carmichael 函数的性质，对于任意 $a \in Z_{n}^{*}$ ：

$(p - 1) | λ, (q - 1) | λ$ -----》 $λ = k_{1} (p - 1) = k_{2} (q - 1)$

根据费马小定理： $a^{p - 1} \equiv 1 \mod p$ 。其中 $p$ 是素数

$a^{λ} = a^{k_{1} (p - 1)} \equiv 1 \mod p$

$a^{λ} = a^{k_{2} (q - 1)} \equiv 1 \mod q$

$a^{λ} \equiv 1 \mod n$

$a^{λ} \equiv 1 \mod n$

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

$(r^{n})^{λ} \equiv 1 \mod n^{2}$ （把 $r^{λ} = k n + 1$ 带入展开）
分析 $u$ 的表达式

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

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

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

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

$u = (k n + 1)^{m} \mod n^{2}$ （把 $g^{λ} = k n + 1$ 带入展开）
应用 $L$ 函数

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

$L (u) = L ((k n + 1)^{m} \mod n^{2}) = \frac{[(k n + 1)^{m} \mod n^{2}] - 1}{n} = \frac{(1 + m \cdot k n \mod n^{2}) - 1}{n} = k m \mod n^{2}$
计算模逆元素 $μ$

在 Paillier 加密算法中，模逆元素 $μ$ 是解密过程的关键部分。它是基于 $g$ 的一个特定幂的 $L$ 函数值的模逆元素。
- 计算 $L (g^{λ} \mod n^{2})$
  
  首先，我们计算 $g^{λ}$ 在 $\mod n^{2}$ 下的结果，然后应用 $L$ 函数。根据 $L$ 函数的定义（ $L (x) = \frac{x - 1}{n}$ ），我们有：
  
  $L (g^{λ} \mod n^{2}) = \frac{(g^{λ} \mod n^{2}) - 1}{n} = \frac{(1 + k n \mod n^{2}) - 1}{n}$
- 计算 $μ$
  
  接下来，我们计算 $L (g^{λ} \mod n^{2})$ 的模逆元素 $μ$ ：
  
  $μ = modinv (L (g^{λ} \mod n^{2}), n)$
  
  $μ = [\frac{(1 + k n \mod n^{2}) - 1}{n}]^{- 1} = (k \mod n^{2})^{- 1} \mod n$
现在，计算原始消息 $m$

$m = L (u) \times μ \mod n$

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

# 4. 同态特性

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

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

# 5.一些改进方案

# 5.1参数g优化

通过选择特定的公钥 $g$ 来简化加密运算。在Paillier加密算法中，通常选择 $g$ 为 $n + 1$ ，这是因为这样的选择可以显著简化加密计算。

当 $g = n + 1$ 时，我们可以利用二项式定理简化对 $g^{m}$ 的计算。具体来说，根据二项式定理，我们有：

(n + 1)^{m} = \sum_{k = 0}^{m} (\binom{m}{k}) n^{k}

在模 $n^{2}$ 的情况下，所有包含 $n^{2}$ 的项都会消失，因此只剩下 $m n + 1$ 。这里的关键点在于，所有 $n^{k}$ （对于 $k \geq 2$ ）的项都是 $n^{2}$ 的倍数，会被模运算消掉。最终我们得到：

(n + 1)^{m} \equiv m n + 1 \mod n^{2}

这种优化使得加密过程只需要一次乘法和一次加法，大大减少了计算量，特别是当处理大规模数据时。此外，这种简化还保留了Paillier算法的同态性质，即保留了对加法的同态操作能力，使得算法在应用中更为高效和实用。这种方法是在不牺牲安全性的前提下简化了加密过程，非常适合需要处理大量数据的场景，如云计算和大数据加密应用。

# 5.2高阶幂运算优化

Ivan Damgård, Mads Jurik, 和 Jesper Buus Nielsen 在 2010 年提出了一个对 Paillier 加密中 $r^{n}$ 高阶幂运算的优化方案。这种优化主要是为了减少计算密文时对大数的幂运算需求，因为这通常是整个加密过程中最耗时的部分。下面我将解释他们的优化方法及其安全性。

在你提供的加密流程中，通过特定的优化方法减轻了加密操作中对高阶幂函数的计算负担。这个方法的核心在于改变密钥生成和加密流程，以提高效率同时保持算法的安全性。我将分别解释这些步骤和优化点：

# 5.2.1密钥生成

选择素数 $p$ 和 $q$ ：
- 这里要求 $p \equiv q \equiv 3 (\mod 4)$ ，这通常与某些数论属性（如生成具有良好密码属性的大素数）相关。
- 确保 $gcd (p - 1, q - 1) = 2$ ，这有助于简化后续的 $λ$ 计算。
计算 $λ$ ：
- $λ = \frac{(p - 1) (q - 1)}{2}$ ，这是系统的一个关键参数，用于加密和解密过程。
选择随机数 $x$ 并计算 $h$ ：
- $x$ 从 $Z_{n}^{*}$ 中随机选取， $h = - x^{2} \mod n$ 。这里的 $h$ 为后续加密提供了基础。
选择自然数 $s$ 并计算 $h_{s}$ ：
- 在原版Paillier中， $s$ 通常设置为1，但在优化版本中， $s$ 可以设为其他值以改进性能。
- $h_{s} = h^{n s} \mod n^{2} + 1$ ，这里 $h_{s}$ 成为公钥的一部分。

# 5.2.2加密

生成随机数 $α$ ：
- $α$ 的取值远小于 $n$ ， $a \in Z_{2^{⌈ k / 2 ⌉}}$ 其中k是密钥长度，这有助于优化加密计算的效率。
加密公式：
- $c = (n \times m + 1) h_{s}^{α} \mod n^{2} + 1$ 。这种方法利用预计算的 $h_{s}$ 和较小的 $α$ 来替代传统Paillier中复杂的 $r^{n}$ 计算，显著提升性能。

# 5.2.3优化效果和安全性

这种优化减少了对大数幂运算的依赖，尤其是在选择较小的 $α$ 时，大大简化了计算过程。由于 $α$ 远小于 $n$ ，计算 $h_{s}^{α}$ 相对于计算 $r^{n}$ 更为高效。
通过合理选择和管理 $x$ 、 $h_{s}$ 和 $α$ ，该方法可以在不牺牲安全性的前提下提高计算效率。

总的来说，这种方法通过减少在加密过程中需要的大数幂运算来优化性能，使得加密操作更快、更高效，特别适用于处理大量数据或在资源受限的环境中使用。在实施这种优化方案时，应确保所有随机数的选取和管理遵循安全的密码学标准，以维持系统的整体安全性。

# 5.3中国剩余定理加速模指数

中国剩余定理（Chinese Remainder Theorem, CRT）是一个古老而强大的数学定理，它提供了一种在模运算系统中解决一系列同余方程的方法。在现代密码学中，CRT可以用来加速大数的模幂运算，特别是在使用如RSA这样的公钥加密算法中。通过应用CRT，可以将一个在大模数下的复杂运算转换为几个在较小模数下的简单运算，这些简单运算可以并行处理，并且计算速度更快。

# 5.3.1基本原理

假设有两个互质的整数 $p$ 和 $q$ ，对于一个整数 $x$ ，如果我们知道了 $x \mod p$ 和 $x \mod q$ 的值，中国剩余定理允许我们唯一地确定 $x \mod p q$ 的值。具体来说，如果：

$x \equiv a (\mod p)$
$x \equiv b (\mod q)$

那么可以找到一个唯一的 $x$ （模 $p q$ ），使得上述两个同余式同时成立。

# 5.3.2利用CRT加速Paillier系统

在如RSA算法中，私钥操作通常是计算 $m^{d} \mod n$ ，其中 $n = p q$ （ $p$ 和 $q$ 是大质数），而 $d$ 是私钥。计算 $m^{d} \mod n$ 直接进行可能非常缓慢，尤其是当 $n$ 非常大时。使用CRT可以有效地加速这个过程，方法如下：

计算模 $p$ 和模 $q$ 的结果：
- 计算 $m_{p} = m \mod p$
- 计算 $m_{q} = m \mod q$
- 计算 $c_{p} = m_{p}^{d} \mod p$
- 计算 $c_{q} = m_{q}^{d} \mod q$
应用中国剩余定理合并结果：
- 找到 $c$ 使得：
  - $c \equiv c_{p} (\mod p)$
  - $c \equiv c_{q} (\mod q)$
- 这可以通过解线性同余方程来完成，通常使用扩展欧几里得算法来找到解。

Paillier中的主要开销在于 $Z_{n^{2}}$ 上的模指数运算，在拥有私钥的情况下，可以利用CRT将 $Z_{n^{2}}$ 分解到 $Z_{p^{2}}$ 和 $Z_{q^{2}}$ 上计算，提高加解密速度若需要此方法加速，则计算方必须知道模数 $n^{2}$ 的分解，也即需要知道 $(p^{2}, q^{2})$ ，这两个是私钥，因此可以直接用于解密过程

使用中国剩余定理优化解密算法的步骤如下：

定义分解因子 $p$ 和 $q$ 对应的函数 $L_{p} (x) = \frac{x - 1}{p}, L_{q} (x) = \frac{x - 1}{q}$
计算 $h_{p} \equiv (p - 1) \cdot q (\mod p), h_{q} \equiv (q - 1) \cdot p (\mod q)$
计算 $m_{p} = L_{p} (c^{p} - 1 \mod p^{2}) \cdot h_{p} \mod p, m_{q} = L_{q} (c^{q} - 1 \mod q^{2}) \cdot h_{q} \mod q$
计算 $m = C R T (m_{p}, m_{q}) \mod n, m$ 即为使用中国剩余定理优化的解密后的明文

当加密方拥有私钥时，我们可以使用CRT将模数 $n^{2}$ 分解为其素因子 $p^{2}$ 和 $q^{2}$ 。然后，我们可以并行地在每个素因子上执行加密操作，最后使用CRT将结果组合起来。

下面是加速加密算法：

计算 $c_{p} = g_{p}^{m} \cdot r_{p}^{p} \mod p^{2}$ ，其中 $g_{p} = g \mod p^{2}$ 和 $r_{p} = r \mod p^{2}$ 。
计算 $c_{q} = g_{q}^{m} \cdot r_{q}^{q} \mod q^{2}$ ，其中 $g_{q} = g \mod q^{2}$ 和 $r_{q} = r \mod q^{2}$ 。
使用CRT将 $c_{p}$ 和 $c_{q}$ 组合成最终的密文 $c$ ： $c = C R T (c_{p}, c_{q}) \mod n^{2}$ 。

通过这种方法，我们可以加速Paillier加密过程，因为我们可以并行地执行加密操作在每个素因子上。

# 5.4 批处理打包技术

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

然而，如果我们想对这些打包的密文执行加法，必须考虑到这一点，以设置初始批次的维度，以避免溢出。设 $n b_{add}$ 为我们想要在这些打包的消息上执行的加法的数量。必须添加到每个插槽的填充（即零位数）等于 $n b_{add}$ 。因此，必须加密 $E n c (m_{1} \underset{{nb}_{add}}{\underset{⏟}{0. . .0}} | m_{2} \underset{{nb}_{add}}{\underset{⏟}{0. . .0}} | . . . | m_{b} \underset{{nb}_{add}}{\underset{⏟}{0. . .0}})$ 。然后，批处理的大小最多应为 $: b = ⌊ \frac{l o g_{2} (N_{E})}{t + n b_{a d d}} ⌋$ 。

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

⌈ \log_{2} (U \times 10^{4}) ⌉ = ⌈ \log_{2} (100 \times 10^{4}) ⌉ = ⌈ \log_{2} (10^{6}) ⌉ = ⌈ 20 ⌉ = 20

# 6. 安全性保障

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

# 7. 结论

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

编辑

上次更新: 2025/04/01, 01:48:12

← RSA乘法同态可验证Paillier同态加密→