# Paillier encryption of small integers to 32-bit integers

I want to encrypt very small integers in the range 0-44 using the Paillier cryptosystem. Is there a way to select p, q (g=n+1 anyway) and mostly r in such a way that I can guarantee that the encrypted values are still 32-bit integers?

Also, I have trouble understanding how to select r. According to wikipedia, the random $$r \in \mathbb Z^{*}_{n}$$. How can I implement this in a programming language e.g. Java when I will have to select random values of r for more than 100,000 such integers?

No. There are $2^{32}$ ciphertexts that fit into 32 bits. They will decrypt to $2^{32}$ random plaintexts uniformly distributed in the range $\{0, 1, \ldots, 2^{|n|}\}$. Since $|n| \gg 32$ for practical Paillier moduli, the probability of any 32-bit ciphertext encoding a plaintext in $\{0, \ldots, 44\}$ is negligibly small.
Regardless whether input is small, $n$ must be large enough to avoid factorization. Next, $r$ must be sampled from a large space to avoid decryption by trial-and-error. Some crypto and big-numbers library (bouncycastle, openssl, crypto..) might be handy to implement such an algorithm. It would be safe to choose an implementation rather than write it from scratch.
• @VadymFedyukovych BigInteger and SecureRandom are already part of the Java SE. Bouncy simply reuses those. May 10, 2015 at 16:07
• Except the implementation part, this answer is correct. If you adapt $n$, s.t. ciphertexts fit into the range of 32 bits, the factorization of $n$ is trivial. If you say $n^2 \approx 2^{32}$ (ciphertext space is mod $n^2$), prime factors of $n$ are around 8 bits. Even if you say you pick a larger $n$, and just have to find $r$,s.t. the ciphertext falls into this range, you can't make that work.