Score:0

How to know the exact result in Paillier cheaper-constant multiplication

de flag

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

fgrieu avatar
ng flag
Hint: 42×15 ≥ 77
de flag
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?
fgrieu avatar
ng flag
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.
de flag
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.
kelalaka avatar
in flag
Could you write your example and close this question?
Score:1
ng flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.