如何在 Paillier 密碼系統中證明正確的解密

Bob 將Paillier 加密得到的密文發送給 Alice。

愛麗絲擁有私鑰。她解密密文並將明文返回給 Bob。

Alice 如何讓 Bob 相信明文對這個密文是正確的？Bob 只有加密後的明文和本次加密的公鑰。

這可以通過使用零知識證明來證明 Paillier 密文是零加密來完成。具體來說，讓 $ c $ 為原始密文，令 $ m $ 是 Alice 發回給 Bob 的解密。然後，Alice 和 Bob 都可以在本地使用同態屬性來計算密文 $ c’ $ 這是對加密值的加密 $ c $ 減 $ m $ . 請注意，如果 $ c $ 是一種加密 $ m $ ， 然後 $ c’ $ 是零加密。

因此，愛麗絲所需要的只是用零知識證明 $ c’ $ 是零的加密（等效地，即 $ c’ $ 是一個 $ n^2 $ ’d 權力）。這可以通過 Damgard 和 Jurik的A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting的 5.2 節中描述的方法非常有效地完成。

根據不同答案中的評論，如果沒有公鑰，證明者可以計算給定公鑰的隨機性。具體來說，讓 $ c=r^N \bmod N^2 $ （這是零加密）。然後，計算 $ M= N^{-1} \bmod \phi(N) $ 和 $ r = c^M \bmod N $ . 這工作以來 $ c^M = r^{N\cdot M} = r^{1+k\cdot \phi(N)} = r \bmod N $ .

這是另一種更簡單的方法。

修正符號。讓 $ N = pq $ 對於兩個大素數 $ p $ 和 $ q $ . Alice 的公鑰是 $ N $ 而她的私鑰是 $ \lambda = \operatorname{lcm}(p-1,q-1) $ .

消息空間是 $ \mathcal{M} = \mathbb{Z}_N $ . 消息的加密 $ m \in \mathcal{M} $ 是（誰）給的 $ C = (1+mN)r^N \bmod N^2 $ 對於一些隨機整數 $ r \in [1, N) $ .

---

獲取密文的解密 $ C $ Bob 以可驗證的方式與 Alice 進行以下協議：

1. Bob 計算 $ R = C \bmod N $ 並發送 $ R $ 給愛麗絲；
2. 愛麗絲使用她的私鑰計算 $ r’ = R^{N^{-1} \bmod \lambda} \bmod N $ 並發送 $ r’ $ 給鮑勃；
3. 鮑勃檢查 $ (r’)^N \equiv R \pmod N $ . 如果是，Bob 恢復明文 $ m $ 作為 $ m= \frac{C\cdot (r’)^{-N} -1 \bmod N^2}{N} $ . 否則，愛麗絲作弊了。

這提供了明文的進一步優勢 $ m $ 愛麗絲不知道。此外，頻寬要求極低：Alice 和 Bob 只交換 $ 2\log_2 N $ 位 ( $ R $ 和 $ r’ $ ).

計算可以稍微加快。這是一個變體。Alice 將她的私鑰定義為 $ d = -N^{-1} \bmod \lambda $ .

1. Bob 計算 $ R = C \bmod N $ 並發送 $ R $ 給愛麗絲；
2. 愛麗絲使用她的私鑰計算 $ r’’ = R^d\bmod N $ 並發送 $ r’’ $ 給鮑勃；
3. Bob 計算 $ S = (r’’)^N \bmod N^2 $ 並檢查 $ S \cdot R\equiv 1 \pmod N $ . 如果是，Bob 恢復明文 $ m $ 作為 $ m= \frac{C\cdot S -1 \bmod N^2}{N} $ . 否則，愛麗絲作弊了。

---

正確性來自下一個命題。

**主張。**對於任何 $ r \in \mathbb{Z}_{N^2} $ , 一個有 $ r^N \equiv (r\bmod N)^N \pmod {N^2} $ .

證明。 寫 $ r = r_0+ r_1N $ 在哪裡 $ r_0 = r \bmod N $ 和 $ r_1 = \lfloor r/N\rfloor $ . 二項式公式產生

$$ r^N=(r_0 + r_1N)^N \begin{array}[t]{l}= \displaystyle\sum_{k=0}^N {N \choose k} r_0^{N-k} (r_1N)^k\ = r_0^N + Nr_0^{N-1}(r_1N) + N(N-1)r_0^{N-2}(r_1N)^2 + \dots\end{array} $$ 因此，減少模 $ N^2 $ ， 我們獲得 $ r^N \equiv r_0^N \equiv (r\bmod N)^N\pmod {N^2} $ .

引用自：https://crypto.stackexchange.com/questions/46736