Paillier 方案中回收隨機盲法的形式安全性
這個問題是對上一個問題的後續/變體。
假設我們正在嘗試生成給定明文的大量（無法區分的）密文，並希望避免標準重新加密的昂貴取冪：
$ c \gets c \cdot r^n \mod n^2 $ （帶有[r∈Zn數學處理錯誤]隨機） $ r \in \mathbb{Z}_n $
我們可以預先計算大量的指數值 $ r_i^n, i=1…p $ ，然後對於每次重新加密，取最後一次重新加密的密文並乘以隨機選擇的[k數學處理誤差] $ k $ $ r^n_{\sigma(1)}, …, r^n_{\sigma(k)} $ .
這種方法的安全性（實踐和理論）是什麼？
可管理的高值的[(pk)數學處理錯誤]的大小（例如 $ {p}\choose{k} $ $ p = 1000 $ 和 $ k = 20 $ ) 產生兩個致盲隨機變數的機率 $ R = \Pi_{i=1..k} r_{\sigma(i)} $ 相等，通常可以忽略不計（如果我們只考慮連續成對的此類值，則更是如此）。
攻擊者可能會通過比較結果密文的所有可能產品來提高他們發現衝突的機會，但即使假設他們可用的所有密文確實都是通過這種方法生成的，並且拋開非常大的計算成本，任何兩個的機會相同的產品似乎仍然低得可以忽略不計。
我是否遺漏了任何其他可能的攻擊媒介？正式的安全證明似乎可以實現嗎？
**編輯：**可能的證明大綱
估計（相對較小）之間發生意外碰撞的機會 $ R^{(i)}(c) $ 和 $ R^{(j)}(c’) $ ， 分別[Math Processing Error] $ i^{th} $ 和[Math Processing Error] $ j^{th} $ 重新加密密碼[Math Processing Error] $ c $ 和[Math Processing Error] $ c’ $ （也許分開處理案件 $ c = c’ $ 和 $ c = c’ $ ).
估計任意兩個產品之間發生意外碰撞的機率 $ R^{(i)} $ : $ \Pi_{i = 1…m} R^{(a_i)} $ 和 $ \Pi_{j = 1…n} R^{(b_j)} $ ，這需要：
- $ {a_i}_i \cap {b_j}_j = 0 $ （任何不正確的情況都可以簡化為前一種情況）
- $ \Sigma_i a_i = \Sigma_j b_j $
因此，主要部分是計算[Math Processing Error] $ a_i $ 和[Math Processing Error] $ b_j $ 驗證條件 1 和 2，給定最大重新加密次數[Math Processing Error] $ s $ 明文的最大總數[Math Processing Error] $ t $ . 這似乎是可以實現的。
然而，這似乎是一個充分的證據嗎？
**編輯2：**實際上，上面的條件2可以變得更強。如果我們注意到 $ r^(i)_1, \dots, r^(i)_k $ ， 這 $ k $ 隨機選擇的值[Math Processing Error] $ i^{th} $ 重新加密，為了比兩個隨機值之間更容易發生衝突，我們必須有：
$ {r^{(a_1)}_1,\dots,r^{(a_1)}_k,r^{(a_2)}_1,\dots,r^{(a_2)}_k,\dots,r^{(a_n)}_k} = {r^{(b_1)}_1,\dots,r^{(b_1)}_k,r^{(b_2)}_1,\dots,r^{(b_2)}_k,\dots,r^{(b_m)}_k} $
荒謬的證明：如果只有一個值[Math Processing Error] $ r^{(i)}_j $ 在一個集合中而不是另一個集合中，則該集合中的值的乘積是 $ C * r^{(i)}_j $ ， 和 $ r^{(i)}_j $ 在統計上獨立於另一組，並且出於所有目的，這兩組在統計上是獨立的。
編輯 3 ：在上述所有內容中，使用替換的平局可能會使計算更容易（因此考慮[Math Processing Error] $ n^k $ 組合而不是[Math Processing Error] $ n\choose k $ ).
您不僅要擔心一對致盲值是否相等，還要擔心它們之間更複雜的關係。因此，為這種方法找到安全證明對我來說並非易事。
讓我詳細說明。認為[Math Processing Error] $ R_j $ 是個[Math Processing Error] $ j $ 您使用的致盲變數。如果 $ R_i = R_j $ ，這是一個問題，但正如你所說，這不太可能發生。然而，這並不是唯一的潛在問題。如果存在索引 $ a,b,c,d $ 這樣 $ R_a R_b = R_c R_d $ ，那麼你可能也有問題，這發生在更高的問題上。至少，這對於安全證明來說將是一個困難，因為這種關係可以被對手檢測到並且允許某些類型的區分攻擊。如果你做[Math Processing Error] $ k $ 和[Math Processing Error] $ n $ 足夠大，你甚至可以排除這種乘法關係，但你可能仍然需要擔心高階乘法關係，而且我並不完全清楚你將如何應對這一挑戰。
也許你可以以某種方式處理這個問題，並通過一些額外的見解來證明一些事情，但我認為上述現象將是一個不平凡的並發症。
您隨後修改了問題以提出證明策略。您修改後的證明策略將不起作用。它要求證明產品之間不太可能發生衝突[Math Processing Error] $ R $ 的。但是，您將無法證明這一點，因為事實並非如此：如果您考慮尺寸非常大的產品，則極有可能確實存在某些此類碰撞。您無法通過選擇來避免這種情況[Math Processing Error] $ k $ 和[Math Processing Error] $ n $ 要更大。因此，您在修訂後的問題中建議的證明策略不起作用。這比你可能意識到的更微妙，我不清楚如何證明你的想法是安全的（或者證明是否可能）。
假設對手可以收集所有[Math Processing Error] $ k $ 為一些未知的明文創建的密文。很明顯，所有的產品[Math Processing Error] $ r_i $ 是任何排列下的不變數。所以這個對手會增加收集到的密文，通過重複減少到上一個問題[Math Processing Error] $ r $ . 為了避免這種攻擊，需要對對手的能力進行非標准假設。