1
$\begingroup$

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

Encryption:

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?

|improve this question
$\endgroup$
  • $\begingroup$ Related to this question. $\endgroup$ – Hilder Vítor Lima Pereira Sep 3 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 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$ – abbasi_ahsan Sep 3 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 at 12:37
  • $\begingroup$ @poncho here i define my goal crypto.stackexchange.com/questions/73023/… $\endgroup$ – abbasi_ahsan Sep 3 at 19:46
2
$\begingroup$

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$).

|improve this answer
$\endgroup$
  • $\begingroup$ Is there material/ paper which can help me to implement this $\endgroup$ – abbasi_ahsan Sep 3 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$ – Geoffroy Couteau Sep 3 at 11:19
  • $\begingroup$ @Geoffory Thankyou $\endgroup$ – abbasi_ahsan Sep 3 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$ – Squeamish Ossifrage Sep 3 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.