# Does Paillier Homomorphic Encryption Work only with numbers?

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.

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

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").

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

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.