基于 Paillier 同态加密的投票系统

密码学课程作业，虽然并不是密码学领域的，浅浅学习一下，了解了一下最简单的 Paillier 算法。

1、密钥生成

1.1 生成公钥

系统首先选择两个独立的大素数 $p$ 和 $q$，计算其乘积 $n=p \times q$ 。

• 大素数：十进制下长度达到数百位的素数 。在数学上，把两个大素数相乘极其容易，但想要把公开的 $n$ 重新拆解回 $p$ 和 $q$（也就是大数分解难题），在目前的计算能力下是几乎不可能完成的 。

同时选择基数 $g$（通常取 $g=n+1$），$(n, g)$ 将被用于对选票进行加密 。

1.2 生成私钥

利用 $p$ 和 $q$，计算卡迈克尔函数 $\lambda(n)=\text{lcm}(p-1, q-1)$，计算辅助变量 $\mu=(L(g^\lambda \bmod n^2))^{-1} \bmod n$ 。

• 生成的 $(\lambda, \mu)$ 将被用于最终结果解密 。

• 卡迈克尔函数 $\lambda(n)$ 是一个最小公倍数，在加密时使用随机数 $r$ 使选票变成了乱码 。当拿到最终的密文后，只要把密文求 $\lambda$ 次方，根据卡迈克尔定理，那个复杂的随机数干扰项就会变成 1 从而被消除 。

2 加密过程

2.1 引入随机数

在区间 $(0, n)$ 内生成一个随机大整数 $r$，并且保证 $r$ 与 $n$ 互斥 。

即使相同的明文选票 $m$，由于每次生成的随机数 $r$ 不同，计算出的密文也截然不同，这确保了系统无法进行重放攻击 。

2.2 模幂计算

生成随机大整数 $r$ 后，执行加密公式，在模 $n^2$ 域下计算密文 $c$ ：

\[c \equiv g^m \cdot r^n \bmod n^2\]

根据上述流程，最终收集到的选票呈现为巨大的数字乱码 。

3 同态聚合

3.1 在不解密的前提下统计

Paillier 算法具有加法同态特性 。

在代码中，对所有密文 $c$ 执行大整数乘法运算：

\[c_{total} = c_1 \cdot c_2 \cdot \dots \cdot c_k \bmod n^2\]

在新生成的密文 $c_{total}$ 中，已经包含了所有选票相加的结果 。

3.2 数学证明

假设存在两张选票： $c_1=g^{m_1} \cdot r_1^n \bmod n^2$ 和 $c_2=g^{m_2} \cdot r_2^n \bmod n^2$。

• 模 $n^2$ 下相乘：

\[c_1 \cdot c_2 = g^{m_1} \cdot r_1^n \cdot g^{m_2} \cdot r_2^n \bmod n^2\]

• 重组后可得：

\[c_1 \cdot c_2 = g^{m_1+m_2} \cdot (r_1 \cdot r_2)^n \bmod n^2\]

可以看出，$c_1 \cdot c_2$ 正好对应明文 $(m_1+m_2)$，并使用随机数 $(r_1 \cdot r_2)$ 进行了一次加密 。

4 解密过程

公布票数的时候，对聚合密文 $c_{total}$，动用私钥 $(\lambda, \mu)$ 。

使用函数 $L(x)=\frac{x-1}{n}$ 进行解密 ：

\[m_{total} = L(c^\lambda \bmod n^2) \cdot \mu \bmod n\]

解密后，就可以直接还原出明文总和 。

5 简单用例验证

为了更好地解释整个过程，假设我们的系统中有 2 位候选人（Alice 和 Bob），有 3 位选民（张三、李四、王五）。

第一步：明文编码

一次同态计算能同时统计两位候选人的票数，需要在系统中设计一个大整数明文 $m$ 的结构 ：

• 规定百位代表 Alice 的票数，个位代表 Bob 的票数 。

• 如果投给 Alice，明文 $m=100$；如果投给 Bob，明文 $m=1$ 。

第二步：投票加密

三个选民开始在客户端投票。系统公钥为 $(n, g)$ 。

• 张三投给了 Alice，明文 $m_1=100$。系统生成随机数 $r_1$，进行加密 $c_1=g^{100} \cdot r_1^n \bmod n^2$ 。

• 李四投给了 Bob，明文 $m_2=1$。系统生成随机数 $r_2$，进行加密 $c_2=g^1 \cdot r_2^n \bmod n^2$ 。

• 王五投给了 Alice，明文 $m_3=100$。系统生成随机数 $r_3$，进行加密 $c_3=g^{100} \cdot r_3^n \bmod n^2$ 。

第三步：同态聚合

现在收到了三张加密选票 $c_1, c_2, c_3$。可以执行密文相乘来统计总票数 。

• 计算总密文 $C_{total} = c_1 \times c_2 \times c_3$ ：

\[C_{total} = g^{100} \cdot r_1^n \times g^1 \cdot r_2^n \times g^{100} \cdot r_3^n \bmod n^2\]

• 把这个巨大的乘法式子重新组合 ：

\[C_{total} = g^{100+1+100} \cdot (r_1 \cdot r_2 \cdot r_3)^n \bmod n^2\] \[C_{total} = g^{201} \cdot R_{total}^n \bmod n^2\]

明文指数被完美地相加了（变成了 201） 。

第四步：解密公布

拿到 $C_{total}$ 后，第一件事就是求它的 $\lambda$（私钥）次方 。

• 根据卡迈克尔定理，任何数的 $n \cdot \lambda$ 次方在 $\bmod n^2$ 下都等于 1，干扰项消失，式子清爽地变成了 $g^{M \cdot \lambda}$ 。

• 通常会把底数 $g$ 设置为 $n+1$。现在要处理的是 $(n+1)^{M \cdot \lambda}$ 。二项式展开后：

\[1 + M \cdot \lambda \cdot n + k \cdot n^2 + \dots\]

$\bmod n^2$ 会使得后面包含 $n^2$ 的项全部消失，最终整个式子只剩下了：$1 + M \cdot \lambda \cdot n$ 。

• 使用解密函数 $L(x) = \frac{x-1}{n}$。先减 1 再除以 $n$ ：

\[\frac{1 + M \cdot \lambda \cdot n - 1}{n} = M \cdot \lambda\]

• 私钥里的另一个参数 $\mu$ 被设定为 $\lambda$ 在模 $n$ 下的“乘法逆元” 。只需把刚才的结果乘以 $\mu$：

\[M \cdot \lambda \cdot \mu \equiv M \cdot 1 \equiv M \bmod n\]

$\lambda$ 被完美抵消，真正的总票数明文 $M$ 成功剥离 。

• $M=201$，201 拆开看百位是 2，个位是 1 。

结论：Alice 得了 2 票，Bob 得了 1 票 。