Short randomness in ElGamal and Paillier

Semantic security in that setting reduces to semantic security for the standard scheme if and only if a certain low-entropy distribution in the “zero ciphertext” subgroup is computationally indistinguishable from random.

• In the case of ElGamal, the assumption is that $(g^r, h^r)$ for random small $r$ is computationally indistinguishable from a standard DH pair, namely $(g^r, h^r)$ for uniform $r$. This was studied by Kurosawa and Koshiba in a PKC 2004 paper, and they showed that the assumption holds if the computational short exponent discrete log problem is hard. For groups of cryptographic relevance, the best attack on short exponent discrete log is usually either Pollard's lambda or the same as for non-short discrete logs, so if $r$ is large enough (at least twice the security parameter), this is considered ok. However, this bound on $r$ is the same as the bound on a full-size exponent anyway if you set parameters correctly, so doing this is useless in most settings.

• In the case of Paillier, the assumption is that $r^n$ for small $r$ is computationally indistinguishable from random in the subgroup of order $\varphi(n)$ of $\mathbb{Z}/n^2\mathbb{Z}$. I'm not aware of any attack on this specific problem and it looks somewhat plausible if $r$ is not too small, although I don't know what more standard assumption it could be related to. Regardless, however, the speedup from using a smaller $r$ in the computation of $r^n \bmod n^2$ should be negligible (in fact, there should be no speedup at all if you use fast arithmetic), so I'm not sure to see the point of this variant either.