Paillier 同態加密計算均值

Paillier同態加密支持明文值的加法和乘法。

我可以使用這些屬性來計算**密文值的平均值嗎？**我嘗試使用以下步驟：

1. 乘以一組密文（得到明文值的總和）
2. 將 step1 中計算的密文提升到 的冪 $ \dfrac{1}{c} $ 在哪裡 $ c $ 是密文的數量）得到平均值

我遇到的問題是，paillier 是在整數域中定義的 $ \mathbb{Z} $ 因此 $ \dfrac{1}{c} $ 總是 $ 0 $ 所以最後的結果也是 $ 0 $ .

有什麼幫助或建議嗎？

整數的 Paillier 加密 $ x_i $ 是（誰）給的 $ c_i = (1+x_iN)r_i^N \bmod N^2 $ 對於一些隨機的 $ 0<r_i<N $ . 鑑於加密 $ x_1, \dots, x_k $ , 加密均值定義為

$$ [![\mu]!] = \left(\prod_{i=1}^k c_i\right)^{k^{-1}\bmod N} r^N\bmod N^2 $$ 對於一些隨機的 $ 0<r<N $ . 如果我們現在將 Paillier 解密程序應用於 $ [![\mu]!] $ ，我們得到

$$ \mu = \frac{\sum_{i=1}^k x_i}{k} \bmod N $$ 我們猜測 $ \sum_{i=1}^k x_i< \sqrt{N} $ . 現在應用拉格朗日-高斯格約簡算法產生 $ \mu $ 作為一個元素 $ \mathbb{Q} $ . 基於：$$ FSW02 $$Pierre-Alain Fouque、Jacques Stern 和 Jan-Geert Wackers。有理數的加密計算。在金融密碼學中，電腦科學講義第 2357 卷，第 136-146 頁。斯普林格，2002 年。

---

或者，我們可以採用擴展歐幾里得算法，而不是使用拉格朗日高斯算法：

[u1, u2] = [0, N]; [v1, v2] = [1, mu];
while (u2 > sqrt(N)) do
  Q = u2 div v2; [t1, t2] = [u1, u2] - [v1, v2]*Q;
  [u1, u2] = [v1, v2]; [v1, v2] = [t1, t2];
endwhile

return u2/u1

---

這是一個玩具範例 $ p = 739 $ , $ q = 839 $ ， 和 $ N = pq = 620021 $ . 認為 $ x_1 = 97 $ , $ x_2 = 74 $ 和 $ x_3 = 46 $ .

我們得到了它們各自的加密： $ c_1 = 206197787317 $ , $ c_2 = 267770082390 $ ， 和 $ c_3 = 49804921902 $ . 我們有 $ k=3 $ 和 $ k^{-1} \bmod N = 206674 $ . 我們隨機選擇 $ r<N $ ， 說 $ r = 559196 $ 併計算

$$ [![ \mu]!] = (c_1c_2c_3)^{k^{-1}\bmod N} , r^N \bmod N^2 = 127639014845 $$ 的解密 $ [![\mu]!] $ 產量 $ \mu = 206746 \pmod N $ . 然後拉格朗日高斯算法產生 $ 206746 \equiv \frac{217}3 \pmod N $ 因此 $ \mu = 217/3 = 72.33 $ .

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