ElGamal 和 Paillier 中的短隨機性

在 Paillier 密碼系統中， $ m \in \mathbb{Z}_N $ 具有隨機性 $ r \in \mathbb{Z}_n^* $ 是 $ c = g^m r^n \bmod{n^2} $ .

我的問題是，如果短怎麼辦（例如 512 位） $ r $ 用來？Elgamal 加密也存在類似的問題。

有很多與 ElGamal 和 Paillier 相關的主題，但我搜尋並沒有找到任何與此相關的主題。

當且僅當“零密文”子組中的某個低熵分佈在計算上與隨機無法區分時，該設置中的語義安全性降低為標準方案的語義安全性。

• 在 ElGamal 的情況下，假設是 $ (g^r, h^r) $ 對於隨機小 $ r $ 在計算上與標準 DH 對無法區分，即 $ (g^r, h^r) $ 制服 $ r $ . Kurosawa 和 Koshiba 在PKC 2004 論文中對此進行了研究，他們表明，如果計算短指數離散對數問題很困難，則該假設成立。對於密碼相關組，對短指數離散對數的最佳攻擊通常是 Pollard 的 lambda 或與非短離散對數相同，所以如果 $ r $ 足夠大（至少是安全參數的兩倍），這被認為是可以的。然而，這對 $ r $ 如果您正確設置參數，則無論如何都與全尺寸指數的界限相同，因此在大多數設置中這樣做是沒有用的。
• 在 Paillier 的情況下，假設是 $ r^n $ 對於小 $ r $ 在順序子群中與隨機數在計算上無法區分 $ \varphi(n) $ 的 $ \mathbb{Z}/n^2\mathbb{Z} $ . 我不知道對這個特定問題有任何攻擊，如果 $ r $ 不是太小，雖然我不知道它可能與什麼更標準的假設有關。然而，無論如何，使用較小的 $ r $ 在計算中 $ r^n \bmod n^2 $ 應該可以忽略不計（事實上，如果你使用快速算術，應該根本沒有加速），所以我也不確定這個變體的意義。

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