ElGamal和Paillier中的短随机性

Question

在Paillier密码体制中，具有随机性的m \in \mathbb{Z}_N的加密r \in \mathbb{Z}_n^*是c = g^m r^n \bmod{n^2}。

我的问题是，如果使用短(例如512位) r怎么办？Elgamal加密也存在类似的问题。

有很多与ElGamal和Paillier相关的主题，但我搜索了，但没有找到任何有关这方面的主题。

Answer 1

当“零密文”子群中的某个低熵分布在计算上与随机不可区分时，该设置下的语义安全性降为标准方案的语义安全性。

• 在ElGamal的情况下，假设随机小r的(g^r, h^r)与标准DH对(即均匀r的(g^r, h^r) )在计算上是不可区分的。Kurosawa和Koshiba在PKC 2004论文中的研究表明，当计算短指数离散对数问题很难时，这一假设成立。对于密码相关组，对短指数离散日志的最佳攻击通常是Pollard的lambda或与非短离散日志相同的攻击，因此如果r足够大(至少是安全参数的两倍)，这是可以的。但是，如果您正确设置参数，那么r上的这个界与全尺寸指数上的界是一样的，所以在大多数设置中这样做都是无用的。
• 在Paillier的情况下，假设小r的D12在计算上与\mathbb{Z}/n^2\mathbb{Z}的阶\varphi(n)子群中的随机不可区分。我不知道有任何针对这个特定问题的攻击，而且如果r不是太小的话，它看上去有些似是而非，尽管我不知道它可能与什么更标准的假设有关。然而，无论如何，在计算r时使用较小的r^n \bmod n^2的加速比应该可以忽略不计(事实上，如果使用快速算术，就根本不应该加速比)，所以我也不确定这个变体有什么意义。