0
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ As far as I know, bouncycastle has no Paillier implementation. And cryptopy does not either $\endgroup$
    – Alexandros
    May 9, 2015 at 14:41
  • 1
    $\begingroup$ bouncycastle has big numbers and random numbers to maybe implement Paillier algorithm with. $\endgroup$
    – Vadym Fedyukovych
    May 9, 2015 at 14:45
  • 1
    $\begingroup$ @VadymFedyukovych BigInteger and SecureRandom are already part of the Java SE. Bouncy simply reuses those. $\endgroup$
    – Maarten Bodewes ♦
    May 10, 2015 at 16:07
  • $\begingroup$ 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. $\endgroup$
    – tylo
    Jun 8, 2015 at 16:27

Your Answer

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

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