0
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Hint: 42×15 ≥ 77 $\endgroup$
    – fgrieu
    Jun 8 at 14:45
  • $\begingroup$ 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? $\endgroup$
    – Giulio
    Jun 8 at 14:57
  • 3
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Jun 8 at 15:03
  • $\begingroup$ 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. $\endgroup$
    – Giulio
    Jun 8 at 15:12
  • 1
    $\begingroup$ Could you write your example and close this question? $\endgroup$
    – kelalaka
    Jun 8 at 19:04
0
$\begingroup$

Are you trying to say that if the product is greater than the modulo then I can't get the true result in anyway?

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.

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