How can homomorphic encryption be probabilistic while allowing for math to be conducted?

I've been playing with some homomorphic encryption libraries. It's given me a greater appreciation for probabilistic encryption. These two answers were instrumental in leading to this question, but don't contain an answer for this question by themselves:

For those who don't know, in probabilistic encryption:

• A piece of data is anonymized by appending a time-dependent random string to its beginning
• This means the same data (or "plaintext") can have a different value each time it's encrypted
• When a user with the key decrypts the data, they then remove this leading string to get back the original plaintext
• A single "bit" of data can be a very long string in the HE space. This means HE encrypted strings contain more 'information' than regular bits. What this information contains is a mystery to me.

As you can tell I (think I) understand probabilistic encryption. But I don't understand how you can possibly retain homomorphism within a probabilistic space.

If each piece of data has a different leading random string, how does the algorithm know which parts of the encrypted data contains the true value? How can you add and subtract two encrypted datas that have different leading strings?

Obviously, the person performing math on the encrypted data can't know the key used to decrypt it. So HE somehow uses different leading random strings to encrypt each data, but these datas can still be added and subtracted together? How can this possibly be true?

• I can't answer your question fully, but I can spot one problem: your assumption that probabilistic encryption prepends a random string to the ciphertext is too strong. Rather, probabilistic encryption must produce outputs that are larger than the inputs; prepending a random string is just a special case of that which applies to some of the basic examples of probabilistic encryption (e.g., CBC mode). Commented Jul 23, 2018 at 18:38

Probabilistic encryption is a necessity for ANY public-key encryption scheme. The reason is that in such schemes anybody can perform the encryption, thus if the encryption was deterministic, that would allow to check a guess of the plaintext. That would be a total disaster in a lot of applications: enciphering a coin toss, a name on the class roll, a price, a bulletin vote, a credit card number or SSN, a password..

There's a tantalizingly simple but somewhat oversimplified explanation to:

If a probabilistic encryption algorithm is used, how does decryption return the correct message?

That explanation says that encryption takes the message, combines it with randomness, then enciphers; and decryption deciphers, then remove randomness to get the original message. That's exactly how it is done in RSA encryption with random padding, where combines sometime is as simple as appending randomness and fixed bits to the message (see e.g. RSAES-PKCS1-V1_5).

However, that simple explanation falls short of the goals of homomorphic encryption, because (as noted in the question) it does not yield a method to perform arithmetic on the encrypted message without holding the decryption key. That's why RSA encryption with random padding is not homomorphic, when RSA without padding is (multiplicatively, modulo the public modulus).

Secure homomorphic encryptions schemes do combine the message and the randomness as in the oversimplified explanation, but that combination is not by concatenation. For homomorphic randomized encryption to work, the combination of randomness and message must be by a method precisely matching the rest of the scheme.

The Paillier cryptosystem is one of the simplest example of randomness combination giving both security and homomorphicity.

As for a normal public-key encryption system, encryption requires the public key of the entity that will ultimately decipher. But (as the name implies) that public key is not secret. In Pailler, it is $(n,g)$ with large $n$ difficult to factor (similar to RSA) and choice of $g$ with $g^n\bmod n^2=1$ (typically $g=n+1$). Pailler encrypts message $m$ with $0\le m<n$ into $$E(m)=g^m\,r^n\bmod n^2\quad=c$$ where $r$ is a fresh random with $0<r<n$ and $\gcd(r,n)=1$.

Efficient decryption is possible knowing the factorization of $n$, with $D(E(m))=m$ for all valid $m$ and $r$.

That way of combining message $m$, randomness $r$, and public key $(n,g)$ is such that we have a homomorphic property: $$\begin{array}{llll} E(m_0)E(m_1)\bmod n^2&=g^{m_0}\,{r_0}^n&g^{m_1}\,{r_1}^n&\bmod n^2\\ &=g^{m_0+m_1}&{(r_0\,r_1)}^n&\bmod n^2\\ &=g^{(m_0+m_1\bmod n)+w\,n}&((r_0\,r_1\bmod n)+x\,n)^n&\bmod n^2\\ &=g^{m_0+m_1\bmod n}\,{(g^n)}^w&{(r_0\,r_1\bmod n)}^n&\bmod n^2\\ &=g^{m_0+m_1\bmod n}&{(r_0\,r_1\bmod n)}^n&\bmod n^2 \end{array}$$ $w$ and $x$ are integers bound to exist, that disappear later in the calculation. On the left side, that's by choice of $g$. On the right side, that's because the polynomial in $x$ raised to the power $n$ has all non-constant terms multiple of $n^2$.

We see that $E(m_0)E(m_1)\bmod n^2$ is identical to what the encryption of $m=m_0+m_1\bmod n$ could have been for choice of randomness $r=r_0\,r_1\bmod n$ .
Notice that the requirements $0\le m<n$ , $0<r<n$ and $\gcd(r,n)=1$ are met.

For a working decryption, we must thus have $$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1\bmod n$$ or, for regular addition: if $0\le m_0<n/2$ and $0\le m_1<n/2$ then $$D(E(m_0)\,E(m_1)\bmod n^2)=m_0+m_1$$

To produce a cryptogram per that homomorphic property, one needs

• at least one ciphertext $c_0=E(m_0)$ for an unknown message $m_0$, typically prepared by someone else (otherwise why use homomorphic encryption?)
• either
• A second similar $c_1=E(m_1)$, so as to be able to compute the ordinary product $c_0\, c_1=c$
• A new $m_1$ to combine, and the public key, which allows to compute $c_1$ and be back to the previous option.
• Typically at least, the public key (specifically, it's component $n$), to allows reduction of $c_1\,c_2$ modulo $n$, for two reasons
• concealing if a particular $c_i$ was involved in preparation of the ciphertext (otherwise determinable by testing if $c_i$ divides $c$)
• the reduced $c\bmod n^2$ is shorter than $c$ by a factor about 2.
• Perhaps I misunderstood something, but isn't the reason why this 'probabilistic RSA' is not used mainly due to the fact that it offers no additional security compared to plain textbook RSA? It's not semantically secure at all (a semantically secure multiplicative variant of RSA would be a great result, imo). From $E(r), E(mr)$, anyone can homomorphically compute $E(m)$, so this added randomness is just useless here, it increases the size without any benefit. Commented Jul 24, 2018 at 7:47
• The core interest of 'probabilistic' homomorphic encryption is it's ability to be semantically secure and homomorphic at the same time - else, we can always make the encryption 'probabilistic' by appending a random string to the ciphertext, ignored at decryption. Commented Jul 24, 2018 at 7:48
• @Geoffroy Couteau: thanks for pointing that! Fixed.
– fgrieu
Commented Jul 24, 2018 at 17:35
• Thanks guys. I found the original example for RSA very clear, and it helped me understand this answer too. I think the RSA example could be included in this answer as well to make it extra clear. As a follow-up, do you need the key to perform homomorphic encryption? Or can you encrypt using only a "public n"? It appears you can use only the public key (n,g) to encrypt, am I reading that correctly? Commented Jul 26, 2018 at 18:20
• @nick carraway: I had been exposed to that RSA example in my first exposition to homomorphic encryption. It stuck in my head as something simple and impractical, but somewhat I missed the obvious: it is just as bad as textbook RSA on security. I don't want that error to repeat, that's why I removed it. Pailler is only marginally more difficult to grasp, is secure, and is practical since it supports addition of comfortably large messages. I tried to address the rest of your comment in an update of the answer.
– fgrieu
Commented Jul 26, 2018 at 18:59