Paillier方案推广

Question

Paillier的方案假定消息和密文空间等于$\mathbb{Z}_N$和$N=pq$，即$N$是两个不同素数的乘积。

是否有一种方法可以将其推广到$N$，它是许多($>2$)不同素数的产物？

Answer 1

是，Pailler加密可以推广到两个以上素数的乘积，就像在多素数rsa中一样。我们只有$N=\prod p_i$和$i\ne j\隐含p_i\ne p_j$。每个$p_i$都必须是秘密的，并且在某个大区间内是一致随机的。我们希望使用$g=N+1$作为生成器(这是常见的)，而不对其顺序进行显式检查，它仍然足以确保$2\min(p_i)>\max(p_i)$。对于$n$素数，在$(2^{1024-1/n},2^{1024})$中选择$p_i$作为随机素数，可以确保这一点，并且$N$正好是$1024\，n$位，并且可以通过使所有素数标准大小来简化代码，使用最后一节的加速比。对于一个工作的随机素数发生器和合理的$n$，命中两个相同的因素或启用费马分解的几率仍然可以忽略不计。

对于密钥生成和解密的其他步骤，正确计算$\varphi(N)$或/和$\lambda(N)$就足够了：

• $\varphi(N)$是所有$(p_i-1)$的乘积。
• $\lambda(N)$是所有$(p_i-1)$的最小公共倍数。

在加密方面有一些特殊之处；事实上，如果$N$是两个或多个大素数的乘积，则无法从公钥中识别。

如果我们想在解密时加速，我们可以选择计算$c^{\lambda(N)}\bmod N^2$ (这是大部分计算工作量的地方)，方法是分别计算每个$p_i$的$c^{λ(N)}\bmod{p_i}^2$，并使用中国剩余定理获得最终结果。它像那里一样工作，除了

• 对于模块$r_i$，我们使用${p_i}^2$
• 对于它们的约化指数$d_i$，我们使用了$\lambda(N)\bmod\lambda({p_i}^2)$，即$\begin{align} d_i&=\lambda(N)\bmod(p_i(p_i-1))\ &=\left(\frac\lambda(N)}{p_i-1}bmod p_i\right)(p_i-1) \end{align}$。

使用CRT获得的加速比约为n^2/2$(经典的代价与比特数平方成正比的多个算法)；这大约是多素数RSA的加速比的一半，因为在Pailler中，指数$\lambda(N)$的比特数约为模数$N^2$的一半，而在RSA中，指数$d$的比特数约为模数$N$的一半。