# How to know the exact result in Paillier chiper-costant multiplication

The encryption function $$E_{k^+}: Z_n \rightarrow Z_{n^2}$$.
The decryption function $$D_{k^-}: Z_{n^2} \rightarrow Z_n$$.
$$m_1 = 42, k = 15, n=77$$.
After encryption, exponentiation and decryption, I get: $$D_{k^-}((E_{k^+}(m_1))^k) \equiv 14 \bmod 77$$ The class of residue of $$14$$ is of the form: $$\langle 14 \rangle = \{\alpha \in Z: 14 + \alpha*77\}$$ And one of these values is $$630 = 14 + 8*77 \equiv 630 \bmod 5929 \equiv 42*15 \bmod 77$$
So, the question is after I decrypt and get $$14$$ how can I, from this value, deduce that the real value of $$\alpha$$ I am searching for is $$8$$, and from that deduce $$630$$, the real value of the product?
Cause, as far as I know, all possible numbers modulo $$5929$$ in $$\langle 14 \rangle$$ could be valid products if I don't know $$m_1$$ and $$k$$.

• Hint: 42×15 ≥ 77
– fgrieu
Jun 8 at 14:45
• Yeah, I know. You trying to say that if the product is greater than the modulo then I can't get the true result in anyway? Jun 8 at 14:57
• Yes. Pailler computes modulo $n$ even if the cryptograms are in $[0,n^2)$. Not coincidentally, $42\times15\equiv14\pmod{77}$. For Pailler to be secure, you need $n$ of several hundred digits, so that's not necessarily an issue.
– fgrieu
Jun 8 at 15:03
• Ah yeah I have lost myself in the examples and totally forgot that I have to think them with a very big modulo. Thank you very much. Jun 8 at 15:12
• Could you write your example and close this question? Jun 8 at 19:04

Yes. Pailler computes modulo $$n$$ even if the cryptograms are in $$[0,n^2)$$. Not coincidentally, $$42\times15\equiv14\pmod{77}$$. For Pailler to be secure, one needs $$n$$ of several hundred digits, so that's not necessarily an issue.