Paillier密码体制-同态

Question

我在这里缺乏相当多的数学知识，但是谁能解释一下为什么尽管引入了随机值，Paillier密码系统仍然是(加性/乘性的)同态？

[\![w_1w_2]\!]_g = [\![w_1]\!]_g + [\![w_2]\!]_g\ \bmod\ n

它是否与从\mathbb{Z}^*_n中取样的值有关？是上述语句持有该w_1, w_2 \in \mathbb{Z}^*_{n^2}的唯一要求吗？

Answer 1

理解Paillier密码系统的难点在于了解密码中的L函数的实际作用以及它的工作原理。好消息是:要理解同态，这个细节可以搁置。

理解同态的最好方法是仔细查看加密函数。下面是：

E(m) = r^n g^m \mod n^2

如果我们把它拆开，我们可以看到：

• 模数为n^2。这意味着我们对一个具有序n \cdot \lambda (与\lambda=lcm(p-1,q-1))相乘的群进行运算。
• 这意味着，存在阶p,q,n,pa, qa,和na的子群，其中a是\lambda的任意适当因子。
• 随机数r的阶数等于其中一个子群序。它可以被p,q整除(实际上，它很可能是order n\lambda)。但是，如果我们考虑n-th势，那么r^n的顺序不能被p或q整除，它只能是\lambda的除数。这是一个可以使用的属性。

现在，对于解密，解密函数可以：

• 删除任何掩蔽因子，这是这样一个r^n，而不知道它是哪个r。
• 将m从剩余的g^m数中取回来，这基本上是这个特殊组中的离散对数。

对于同态，只需加密两条消息，构建它们的产品，并进行一些非常基本的转换：

E(m_1) = c_1 = g^{m_1}{r_1}^n

E(m_2) = c_2 = g^{m_2}{r_2}^n

c_1 c_2 = g^{m_1}{r_1}^n g^{m_2}{r_2}^n = g^{m_1+m_2} (r_1r_2)^n

显然，这与使用带有消息m_1+m_2和随机数(r_1r_2)的加密方法是一样的。因此，解密就像一个密文一样有效。