3
$\begingroup$

Paillier homomorphic encryption enables us to combine two messages such as

$D\left(E(m_1,r_1) \cdot E(m_2,r_2) \mod n^2\right) = m_1+m_2 \mod n$

My question is what are the specification of $m_1$ and $m_2$. Should they only be numbers (e.g., integers), or could they be textual information (e.g., "Hi")?

If it allows textual input for $m_1$ and $m_2$ how would the sum $m_1+m_2$ be retrieved for $m_1 =$ "hi" and $m_2 =$ "hello" for example.

$\endgroup$
  • 3
    $\begingroup$ You can encode strings as bytes and you can encode these as numbers. $\endgroup$ – SEJPM May 28 '17 at 21:29
  • $\begingroup$ but how the sum of $m1$ and $m2$ can be retrieved, it would be the sum of bytes. $\endgroup$ – Sari May 28 '17 at 21:31
  • 1
    $\begingroup$ Do you believe they are something besides bytes when you write a program or run machine code? $\endgroup$ – Thomas M. DuBuisson May 29 '17 at 2:49
3
$\begingroup$

Shot answer:

It can work over a set $\mathcal{M}$ of non-numeric data, but you have to find a map from elements of $\mathcal{M}$ to $\mathbb{Z}_n$ in a way that the operations between elements of those two sets are related.


In details:

The message space of Paillier cryptosystem is the ring $\mathbb{Z}_n$ and it guarantees some homomorphic properties over this ring.

Thus, if you want to work homomorphically over any other message space $\mathcal{M}$, you have to model $\mathcal{M}$ as a ring and find an isomorphism, say $\varphi$, between $\mathcal{M}$ and $\mathbb{Z}_n$.

Given two messages $x_0$ and $x_1$ of $\mathcal{M}$, you would apply the isomorphism $\varphi$ to get $m_0 = \varphi(x_0)$ and $m_1 = \varphi(x_1)$, then, encrypt those messages, getting $c_0 = Enc(m_0)$ and $c_1 = Enc(m_1)$. Now, if you add them, you get $c$ that decrypts to $ m = m_0 + m_1$. Therefore, after decryption, you would just need to use the isomorphism:

$$\varphi^{-1}(m) = \varphi^{-1}(m_0 + m_1) = \varphi^{-1}(m_0) + \varphi^{-1}(m_1) = x_0 + x_1$$

as expected.

About the the particular case you pointed out: using concatenation as addition will never yield a ring isomorphic to $\mathbb{Z}_n$, because addition in $\mathbb{Z}_n$ is commutative, while concatenation is not (e.g., "hi" + "hello" is different from "hello" + "hi").

$\endgroup$
  • $\begingroup$ Thank you for your answer. I added another question that is related to this. You help is appreciated. Thnx again. $\endgroup$ – Sari May 29 '17 at 19:07
2
$\begingroup$

Paillier momomorphic Encryption "works" only with numbers (more precisely, integers modulo $n$), in the sense that it looses its homomorphic property $D(E(m_1,r_1)\cdot E(m_2,r_2) \bmod n^2)\;=\;m_1+m_2\bmod n$ when applied to strings and $+$ is understood as a common string operator such as string concatenation.

Note: it is simple to make a cryptosystem (including asymmetric) with $D(E(m_1,r_1)+E(m_2,r_2))\;=\;m_1+m_2$ where $+$ is string concatenation. An example is: for encryption, encipher each character of the string individually using the Paillier cryptosystem (or RSA with secure random padding), convert each output into a big-endian decimal string with / prefix, then concatenate them. For decryption, split the ciphertext per the /, convert each block to integer and decipher it, then concatenate the resulting characters.

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