1
$\begingroup$

In the Paillier cryptosystem the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$.

My question is, what if short (E.g. 512bits) $r$ is used? Similar question exists for Elgamal encryption.

There are lots of topics related to ElGamal and Paillier, but I searched and did not find any topics regarding this.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.