本文总结Paillier及其变种Paillier-DJN方案。

Paillier(original)

方案细节

懒得写方案，因为到处都能找到。直接看（知乎）Paillier半同态加密：原理、高效实现方法和应用。

Carmichael定理背后的数学原理

(2023.8) 之前写了一大段，不过因为跟COA_RSA那篇的内容重复，所以现在删掉了

见本博客的另一篇文章：NepCTF2022 - COA_RSA解读

方案的设计思路

待补充…

Paillier-DJN

以下方案与原论文有出入。我这里写的是 section 4.1中，$s=1$时的情况。

KeyGen

1. Choose two random safe primes $p$, $q$ such that $p,q\equiv 3 \pmod 4$ and $\text{gcd}(p-1, q-1) = 2$

2. Compute $n = pq \ , \ \lambda = \text{lcm}(p-1, q-1) = (p-1) (q-1) / 2$

3. Choose $g = n+1$

4. Choose random $x\leftarrow \mathbb{Z}_n^{*}$ , then compute $h = -x^{2}\ , \ h_s = h^{n} \mod {n^2}$
5. $pk = (n, h_s)\ , \ sk = \lambda$

Enc

Let $|n|$ denote the bit length of n.

1. Choose random $a\leftarrow \mathbb{Z}_{ 2^ \left \lceil |n|/2 \right \rceil }$.
2. Compute ciphertext $c = (1+mn)\cdot h_s^{a} \mod n^{2}$ //We can use CRT to calc $h_s^a \mod n^2$

Dec1

Note that here we assume $m \in \mathbb{Z}_{n}^{*}$ ( i.e. $m < n$)

1. Compute $m\lambda = L( c^{\lambda} \!\mod n^{2})$, where $L(x) = \frac{x-1}{n}$
2. Recover $m$ by compute $m = m\lambda \cdot \lambda^{-1} \mod n^{2}$

Dec2

Note that here we assume $m \in \mathbb{Z}_{n^2}^{}$ . *This is the case in the original paper, but it’s far more complicated then Dec1…

这种解密方案似乎没有在实际中应用，并且细节比较繁琐，这里就不写了。

Reference

1. （知乎）Paillier半同态加密：原理、高效实现方法和应用

2. A generalization of Paillier’s public-key system with applications to electronic voting