1
$\begingroup$

I'm lacking quite some mathematical knowledge here, but could anyone please explain to me why the Paillier cryptosystem is still (additive/multiplicative) homomorphic despite introducing a random value?

$[\![w_1w_2]\!]_g$ = $[\![w_1]\!]_g + [\![w_2]\!]_g\ \bmod\ n$

Does it have to do with the value being sampled from $\mathbb{Z}^*_n$? Is the only requirement for the above statement to hold that $w_1, w_2 \in \mathbb{Z}^*_{n^2}$?

| improve this question | |
$\endgroup$
  • $\begingroup$ Welcome to crypto.SE! Note that in the question's equation, the product is modulo $n^2$, and the sum is modulo $n$. Another way to define the homomorphism in Paillier's cryptosystem is $\forall (m_1,m_2,r_1,r_2),\quad D(E(m_1,r_1)\cdot E(m_2,r_2) \bmod n^2)\;=\;m_1+m_2\bmod n$. where $m_i$ are the messages, and $r_i$ the randomness used in encryption. This is not an answer. $\endgroup$ – fgrieu Dec 16 '19 at 13:40
  • $\begingroup$ Thanks, in the paper only the sum contains a modulo though? $\endgroup$ – chibi03 Dec 16 '19 at 14:15
  • $\begingroup$ [updated] In this paper, ciphertexts are in $\Bbb Z_{n^2}^*$ (the subset of ,$\Bbb Z_{n^2}$ with elements are coprime with $n$), thus multiplication of ciphertexts implicitly reduce modulo $n^2$. Definitely, one can reduce modulo $n^2$ after multiplication of ciphertexts. That's a good idea since it reduces size, and a practical implementation could/should enforce ciphertext in $[0,n^2)$. Plus, in some protocols, the reduction could help prevent traceability. This is not an answer either. $\endgroup$ – fgrieu Dec 16 '19 at 22:11
1
$\begingroup$

The difficult part about understanding the Paillier cryptosystem is to understand what the $L$ function in the cryption actually does and why it works. The good news is: To understand the homomorphism, that detail can be put on hold.

The best way to understand homomorphism is to have a close look at the encryption function. Here it is: $$ E(m) = r^n g^m \mod n^2$$

If we take this apart, we can see:

  • The modulus is $n^2$. That means we operate on a multiplicative group with order $n \cdot \lambda$ (with $\lambda=lcm(p-1,q-1)$).
  • This means, there exist subgroups of order $p,q,n,pa, qa,$ and $na$, where $a$ is any proper divisor of $\lambda$.
  • The random number $r$ has an order equal to one of those subgroup orders. It could be divisible by $p,q$ (actually, it's overwhelmingly likely to be the order $n\lambda$). However, if we take that to the $n$-th potency, then the order of $r^n$ is not divisible by either $p$ or $q$, it can only be a divisor of $\lambda$. That is a property that can be used.

Now for the decryption, it is enough that somehow the decryption function can:

  • Remove any masking factor which is such an $r^n$, without knowing which $r$ it is.
  • Get $m$ back from the remaining number $g^m$, which is basically a discrete logarithm in this special kind of group.

Now for the homorphism, just encrypt two messages, build their product and do some very basic transoformations:

$$ E(m_1) = c_1 = g^{m_1}{r_1}^n$$ $$ E(m_2) = c_2 = g^{m_2}{r_2}^n$$ $$ c_1 c_2 = g^{m_1}{r_1}^n g^{m_2}{r_2}^n = g^{m_1+m_2} (r_1r_2)^n$$

Clearly, this is just the same as using the encryption method with the message $m_1+m_2$ and the random number $(r_1r_2)$. And for that the decryption works just like for a single ciphertext.

| improve this answer | |
$\endgroup$

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.