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: 


If a probabilistic encryption algorithm is used, how does decryption return the correct message?
Partially Homomorphic Cryptographic Schemes - Deterministic vs Probabilistic
Homomorphic &amp; Functional encryption: Mapping unencrypted outputs to encrypted outputs using existing data


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?
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&lt;n$ into $$E(m)=g^m\,r^n\bmod n^2\quad=c$$ where $r$ is a fresh random with $0&lt;r&lt;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&amp;=g^{m_0}\,{r_0}^n&amp;g^{m_1}\,{r_1}^n&amp;\bmod n^2\\
&amp;=g^{m_0+m_1}&amp;{(r_0\,r_1)}^n&amp;\bmod n^2\\
&amp;=g^{(m_0+m_1\bmod n)+w\,n}&amp;((r_0\,r_1\bmod n)+x\,n)^n&amp;\bmod n^2\\
&amp;=g^{m_0+m_1\bmod n}\,{(g^n)}^w&amp;{(r_0\,r_1\bmod n)}^n&amp;\bmod n^2\\
&amp;=g^{m_0+m_1\bmod n}&amp;{(r_0\,r_1\bmod n)}^n&amp;\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&lt;n$ , $0&lt;r&lt;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&lt;n/2$ and $0\le m_1&lt;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.