I want to use the Paillier cryptosystem for encryption and decryption purposes in my research work. But i haven't found a way to encrypt big input messages; As i want to encrypt the message i,e m :

m = 0xa56f89d6aa234776b22347293429ff074928ab3749cc2837c492b874ebfaba78364ba0912efe862f628347982478b

Key Gen:

p =887, q = 907 , n =804509 ,n² = 647234731081;
g = n+1 = 804510;
λ = LCM(p-1,q-1) = 401358;
μ = L(g^λ mod n²)^(-1) mod n = 637146


Let random r = 1987
 c = ((g^m) * (r^n)) (mod n^2)

How can calculate g^m for such big input m?

If encrypted, then how can decryption work for big messages i,e m?

  • $\begingroup$ Related to this question. $\endgroup$ Sep 3 '19 at 11:29
  • $\begingroup$ The entire reason Pallier is interesting is because of the partial homomorphic properties; that is, given $E(a)$ and $E(b)$, someone with only the public key can compute $E(a + b \bmod n)$. What are your homomorphic goals if $a > n$? If "none at all", then standard hybrid crypto (use Pallier to encrypt a symmetric key, and then use the symmetric key to encrypt the actual message) is your answer. $\endgroup$
    – poncho
    Sep 3 '19 at 12:19
  • $\begingroup$ No i don't want to use Pallier to encrypt only symmetric key, i want to encrypt some big data(hexadecimal values) $\endgroup$ Sep 3 '19 at 12:26
  • $\begingroup$ But what is your goal? What problem are you trying to solve? "Using Pallier to encrypt a large amount of data" is a solution, not a goal. $\endgroup$
    – poncho
    Sep 3 '19 at 12:37
  • $\begingroup$ @poncho here i define my goal crypto.stackexchange.com/questions/73023/… $\endgroup$ Sep 3 '19 at 19:46

The Paillier cryptosystem allows to encrypt integers modulo $n$. Therefore, if $m$ is bigger than $n$, encrypting it will lose most of the message - only $m \bmod n$ is retrieved through decryption.

To encrypt a message bigger than $n$, you must break it into blocks, which you encrypt separately. You can for example write $m$ in base $n$, as $m = \sum_i m_i n^{i}$, and encrypt the $m_i$'s separately with Paillier.

Also, regarding how to calculate $g^m \bmod n^2$: note that $g = n+1$, hence

$g^m = (1+n)^m = 1 + n\cdot m \bmod n^2$

(if you develop $(1+n)^m$, you get $1 + nm + n^2\cdot \mathsf{something}$, and the $\mathsf{something}$ disappears modulo $n^2$).

  • $\begingroup$ Is there material/ paper which can help me to implement this $\endgroup$ Sep 3 '19 at 11:07
  • $\begingroup$ There are probably plenty of resources online about implementations of the Paillier cryptosystem in all major languages. I do not know much about that, since I never implemented it myself. $\endgroup$ Sep 3 '19 at 11:19
  • $\begingroup$ @Geoffory Thankyou $\endgroup$ Sep 3 '19 at 11:28
  • $\begingroup$ This does not give an IND-CCA2/NM-CCA2 public-key encryption scheme as one usually expects from the term ‘public-key encryption’. $\endgroup$ Sep 3 '19 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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